логика - Экзамен по английскому языку

По поводу обобщения задачи. Пусть имеется $%n$% участников теста. Через $%m+1$% удобно обозначить такое количество участников, при котором для любого вопроса среди них всегда найдётся тот, кто дал верный ответ. Далее, $%k$% -- такое число, что среди любых $%k$% участников на какой-то из вопросов теста никто не ответил. Нужно найти величину $%N=N(n,m,k)$% -- минимальное число вопросов в тесте, при котором это возможно.

В решении исходной задаче было $%n=9$%, $%m=k=5$%; ответ при этом получается $%N=C_n^m$%.

Удобно слегка переформулировать задачу. С каждым вопросом теста свяжем множество всех тех, кто на него не ответил. Каждое такое множество, согласно условию, не более чем $%m$%-элементно, причём его можно дополнить до $%m$%-элементного. И если взять семейство таких $%m$%-элементных подмножеств, то нас интересует случай, когда каждое $%k$%-элементное подмножество содержится в некотором множестве семейства.

Короче говоря, случай $%N(n,m,k)$% означает, что мы хотим минимальным числом $%m$%-элементных подмножеств покрыть все $%k$%-элементные. Понятно, что при $%m=k$% это приводит к полученному выше ответу.

При $%k=1$% ответ очевиден: $%N(n,m,1)=\lceil n/m\rceil$%. Но уже при $%k=2$% всё не так просто. Например, если брать случай $%N(n,3,2)$%, то есть наименьшим числом троек пытаться покрыть все пары, то при малых значениях $%n$% от $%3$% до $%7$% получаются значения $%1,3,4,6,7$%, что проверяется вручную. Очевидна также оценка снизу $%N\ge C_n^2/3$%, поскольку нам надо покрыть $%C_n^2$% пар, а тройка покрывает три пары. Но эта оценка, вообще говоря, не является оптимальной.

Анализ случая $%n=7$% приводит к "экстремальному" примеру, когда $%7$% троек, а именно $%126,234,135,147,257,367,456$%, где каждая пара задействована ровно один раз. Это не что иное как конечная проективная плоскость. Что наводит на мысль о нетривиальности уже этого случая. То есть, тут приблизительное значение $%N$% известно, но от значения числа $%n$% зависит, как происходят округления.

В итоге я посмотрел в Сети известную Энциклопедию конечных последовательностей, и нашёл то, что соответствует случаю $%N(n,3,2)$%. Там содержалась информация относительно самой этой проблемы. Ключевые слова -- "covering numbers". Далее я в Гугле посмотрел, что по этому поводу известно. На эту тему есть сотни работ. Когда-то была получена нижняя оценка, которая, вообще говоря, точной не является. Но для случая $%k=2$% было доказано, что она точна. А уже при $%k=3$% толком ничего не известно.

Для $%N(n,3,2)$% ответ имеет такой вид: $$\left\lceil\frac{n}3\left\lceil\frac{n-1}2\right\rceil\right\rceil.$$ То есть это примерно равно округлению числа $%C_n^2/3$% в сторону увеличения, а при нечётных $%n$% выполнено равенство. Решён также общий случай $%N(n,m,2)$% (Туран), и формула тоже состоит из округлений и перемножений.

А в общем случае задача, судя по всему, является весьма глубокой.