На экзамене по английскому девяти школьникам был предложен тест, состоящий из нескольких вопросов. Известно, что любые шесть школьников ответили вместе на все вопросы (то есть на каждый вопрос хоть один из них дал правильный ответ), а любые пять — нет. При каком минимальном количестве вопросов это могло быть?

задан 15 Ноя '12 18:38

изменен 16 Ноя '12 20:50

Deleted's gravatar image


126

10|600 символов нужно символов осталось
4

Рассмотрим любую пятерку учеников. Существует хотя бы один вопрос, ответа на который не знает никто из них. Но этот ответ знает каждый из остальных четырех школьников (потому что он вместе с пятью знает все ответы). Итак, для каждой четверки учеников существует вопрос, который все они знают, причем у каждой четверки он разный. Значит, всего должно быть не менее $%C_9^4 = 126$% вопросов.
Это число достижимо. Пронумеруем все возможные четверки числами от 1 до 126. Будем считать, что каждый ученик знает те и только те вопросы, номера которых соответствуют тем четверкам, в которые он входит.

ссылка

отвечен 15 Ноя '12 21:25

Спасибо, все понятно

(16 Ноя '12 16:50) danny_leonov
1

А вот интересно, можно ли обобщить задачу на случай, когда разница между "знающими" и "незнающими" больше 1?

(17 Ноя '12 1:06) DocentI

Меня тоже заинтересовала эта задача -- я сегодня над ней подумал. Решение сейчас напишу в "основной" части, так как в комментарий оно вряд ли уместится.

(10 Фев '13 1:12) falcao

Я когда записал часть решения, то обнаружил, что полученная мной нижняя оценка в общем случае не оптимальна. Ситуация в целом оказалось несколько сложнее, чем я думал. Но за сегодня постараюсь "добить" это дело до конца. Задача вообще интересная получилась.

(12 Фев '13 9:15) falcao
10|600 символов нужно символов осталось
10

По поводу обобщения задачи. Пусть имеется $%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)$% (Туран), и формула тоже состоит из округлений и перемножений.

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

ссылка

отвечен 12 Фев '13 19:18

Какой Вы молодец, целое исследование провели! Очень интересно и познавательно.

(12 Фев '13 21:14) DocentI

Спасибо Вам и автору вопроса за "наводку" на интересную тему. Меня комбинаторные вещи привлекают в первую очередь. Вот ссылка на ту работу, которую я нашёл в Сети:

http://www.ccrwest.org/cover/cover.pdf

Насколько я понимаю, нижняя оценка получается совсем просто, при помощи прямого рассуждения. Интересно то, как получить оптимальные покрытия. Работа Турана там упоминается в разделе 6.3. Скорее всего, это та же статья, где была доказана его "экстремальная теорема" -- о том, сколько рёбер может содержать простой граф без треугольников, а также без полных подграфов с $%r$% вершинами.

(13 Фев '13 3:08) falcao

Бывает так, что явные конструкции построить трудно (как, например, в задачах рамсеевского типа), и иногда применяются интересные статистические соображения. Берётся "случайная" конструкция, а потом оценивается вероятность того, что она обладает нужными свойствами. Если удаётся доказать при помощи оценок, что вероятность ненулевая, то всё доказано -- без явного предъявления примера!

(13 Фев '13 3:10) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×291

задан
15 Ноя '12 18:38

показан
3527 раз

обновлен
13 Фев '13 3:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru