Question

Двадцать одна девочка и двадцать один мальчик принимали участие в математическом конкурсе. Каждый участник решил не более шести задач. Для любых девочки и мальчика найдётся хотя бы одна задача, решённая обоими. Докажите, что была задача, которую решили не менее трёх девочек и не менее трёх мальчиков.Срочно!!!!НЕ МОГУ РЕШИТЬ даю 10

Answer 1

Ответ:

Предположим, что нашлась задача, которую решили не более двух девочек или не более двух мальчиков. Будем считать задачу «красной» , если её решили не более двух девочек и «чёрной» в противоположном случае (тогда её решили не более двух мальчиков) . Представим шахматную доску с 21-й строкой, каждая из которых соответствует девочке, и 21-м столбцом, каждый из которых соответствует мальчику. Тогда каждая клетка соответствует паре «мальчик–девочка» . Каждую клетку покрасим в цвет какой-нибудь задачи, которую решили и мальчик-строка и девочка-столбец. По принципу Дирихле в каком-нибудь столбце найдётся 11 чёрных клеток, или в какой-нибудь строке найдутся 11 красных клеток (потому что иначе получится, что всего клеток не более чем 21 • 10 + 21 • 10 < 21²).

Рассмотрим, например, девочку-строку, содержащую хотя бы 11 чёрных клеток. Каждой из этих клеток соответствует задача, решённая максимум двумя мальчиками. Тогда мы можем указать не менее 6 различных задач, решённых этой девочкой. В силу первого условия никаких других задач девочка не решала, но тогда максимум 12 мальчиков имеют общие решённые задачи с этой девочкой, что противоречит второму условию.

Точно также разбирается случай, если в каком-нибудь столбце найдутся 11 красных клеток.

Answer 2

Давайте докажем это утверждение методом от противного (доказательство от противного).

Предположим, что нет ни одной задачи, которую решили бы не менее трёх девочек и не менее трёх мальчиков.

Это означает, что для каждой задачи решения девочек и мальчиков не пересекаются более, чем в двух случаях, так как если бы пересекались более чем в двух, то была бы задача, которую решили бы не менее трёх девочек и не менее трёх мальчиков.

Посчитаем общее количество случаев, в которых девочки и мальчики могут пересекаться в решении задач. У нас есть 21 девочка и 21 мальчик, и каждый из них может решить не более 6 задач. Поэтому максимальное количество пересечений для каждой задачи составляет 6 + 6 = 12 случаев (максимум 6 девочек и 6 мальчиков могут решить одну задачу).

Теперь предположим, что каждая задача имеет не более 2 пересечений между девочками и мальчиками. Так как всего задач 42 (21 девочка и 21 мальчик), то максимальное количество пересечений для всех задач составляет 42 * 2 = 84 случая.

Но мы знаем, что общее количество пересечений не может быть больше 12 * 42 = 504 случаев (по 12 пересечений для каждой из 42 задач). Это означает, что общее количество пересечений (84) меньше, чем максимально возможное количество пересечений (504).

Это противоречие. Мы не можем иметь меньше пересечений, чем максимально возможное количество пересечений, при условии, что каждая задача имеет не более 2 пересечений между девочками и мальчиками. Следовательно, наше изначальное предположение было неверным.

Таким образом, должна существовать хотя бы одна задача, которую решили не менее трёх девочек и не менее трёх мальчиков. Доказательство завершено.