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

ответ:

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

будем считать «красной», если её решили не более двух девочек и «чёрной» в противоположном случае (тогда её решили не более двух мальчиков).

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

тогда каждая клетка соответствует паре «мальчик–девочка». каждую клетку покрасим в цвет какой-нибудь , которую решили и мальчик-строка и девочка-столбец.

по принципу дирихле в каком-нибудь столбце найдётся 11 чёрных клеток, или в какой-нибудь строке найдутся 11 красных клеток (потому что иначе получится, что всего клеток не более чем 21 • 10 + 21 • 10 < 21²).

рассмотрим, например, девочку-строку, содержащую хотя бы 11 чёрных клеток.

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

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

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

пошаговое объяснение:

ответ:

для любых девочки и мальчика найдётся хотя бы одна , решённая обоими это доказательство потому что они решают 6 одинаковых и 21 делится на 3 без остатка и получается 7

пошаговое объяснение: