Question

11 студентов написали тест.Учитель проверил работы и заметил, что для любых двух во теста, найдутся хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух во Докажите, что в тексте было не более 12 во

Answer 1

Представим себе двудольный граф: слева вершины, обозначающие студентов, справа — вопросы. Если студент ответил на вопрос, то между этим студентом и этим вопросом проведем ребро.

Рассмотрим первую пару вопросов ($a_{1},a_{2}$). Для них по условию найдется хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух вопросов. Пусть это множество из хотя бы 6 студентов называется $A_{1}$. Тогда остальных студентов (тех, что не удовлетворяют описанному требованию) не больше 5 — это множество $B_{1}$. Рассмотрим следующую пару вопросов ($a_{3},a_{4}$,попарно отличных от предыдущих). Тогда $A_{2}$ имеет с $A_{1}$ хотя бы одно пересечение. Поэтому для пары $a_{2},a_{3}$ будет хотя бы одно ребро из множества $B_{1}$. Рассматривая далее пары $a_{5},a_{6}$ и соответственно пары $a_{2},a_{4}$ "берем" еще один элемент из $B_{1}$. Так можно продолжать до тех пор, пока все элементы из $B_{1}$, коих не больше пяти, не будут взяты. То есть всего можно добавить 2*5=10 вопросов дополнительно к $a_{1}, a_{2}$. То есть всего не более 12.

Примечание: множество $A_{1}$ делится на два множества, из каждого идут ребра к вопросам $a_{1},a_{2}$, но из каждого к ровно одному. Для того, чтобы мы могли всегда изымать элементы из $B_{1}$ надо всего лишь без ограничения общности потребовать, чтобы ребро из $a_{2}$ шло в наибольшее из множеств, на которое делится $A_{1}$. Тогда наименьшее из этих множеств деления не превосходит 5.

Answer 2

Добрый день!

Для решения данной задачи сначала составим таблицу, где каждая строка будет соответствовать студенту, а каждый столбец будет соответствовать вопросу:

Вопрос 1 Вопрос 2 ... Вопрос n
Студент 1 Да Да ...
Студент 2 Да Нет ...
...
Студент 11 Да Да ...

Так как для любых двух вопросов найдутся хотя бы 6 студентов, каждый из которых правильно ответил ровно на один из них, то можно сделать следующее наблюдение. Возьмем два любых вопроса (назовем их вопрос A и вопрос B). Пусть есть 6 студентов, которые правильно ответили на вопрос A и 6 студентов, которые правильно ответили на вопрос B. Обозначим этих студентов как A1, A2, ..., A6 (ответили правильно на вопрос A) и B1, B2, ..., B6 (ответили правильно на вопрос B).

Теперь рассмотрим студентов C1, C2, ..., C11, которые не входят в группу A или B. Рассмотрим их ответы на вопросы A и B. По условию задачи, каждый из них должен иметь хотя бы один правильный ответ из пары A, B. Но таких студентов 11 - 6 - 6 = -1, что невозможно. То есть, не существует 11 студентов, которые были бы не в группе A или B, и каждый бы имел хотя бы один правильный ответ из пары A, B.

Значит, для любых двух вопросов A и B найдутся множества из 6 студентов, каждый из которых правильно ответил ровно на один из них. Таких пар вопросов всего C(n, 2) = n! / (2!(n-2)!), где n - общее число вопросов.

Теперь рассмотрим количество пар вопросов, для которых существуют такие группы из 6 студентов. В каждой группе A или B может быть только 6 студентов, каждый из которых правильно ответил на один из вопросов. Так как для каждого вопроса максимум 6 студентов могут быть в группе, всего возможных пар "групп А и В" не может быть больше C(6, 2) = 15.

Таким образом, количество возможных пар вопросов, для которых выполняется условие задачи, не может быть больше 15. Но в условии сказано, что было не более 12 пар вопросов. Значит, количество возможных пар вопросов равно или 12, или меньше.

Таким образом, мы доказали, что в тексте было не более 12 пар вопросов.

Надеюсь, что объяснение и решение задачи будут понятны школьнику. Если у него возникнут вопросы или нужно что-то прояснить, пожалуйста, дайте знать!