Двадцать одна девочка и двадцать один мальчик принимали участие в конкурсе. каждый участник решил не более шести . для любых девочки и мальчика найдётся хотя бы одна , решённая обоими. докажите, что была , которую решили не менее трёх девочек и не менее трёх мальчиков.
ответ:
предположим, что нашлась , которую решили не более двух девочек или не более двух мальчиков.
будем считать «красной», если её решили не более двух девочек и «чёрной» в противоположном случае (тогда её решили не более двух мальчиков).
представим шахматную доску с 21-й строкой, каждая из которых соответствует девочке, и 21-м столбцом, каждый из которых соответствует мальчику.
тогда каждая клетка соответствует паре «мальчик–девочка». каждую клетку покрасим в цвет какой-нибудь , которую решили и мальчик-строка и девочка-столбец.
по принципу дирихле в каком-нибудь столбце найдётся 11 чёрных клеток, или в какой-нибудь строке найдутся 11 красных клеток (потому что иначе получится, что всего клеток не более чем 21 • 10 + 21 • 10 < 21²).
рассмотрим, например, девочку-строку, содержащую хотя бы 11 чёрных клеток.
каждой из этих клеток соответствует , решённая максимум двумя мальчиками.
тогда мы можем указать не менее 6 различных , решённых этой девочкой. в силу первого условия никаких других девочка не решала, но тогда максимум 12 мальчиков имеют общие решённые с этой девочкой, что противоречит второму условию.
точно также разбирается случай, если в каком-нибудь столбце найдутся 11 красных клеток.
пошаговое объяснение:
ответ:
для любых девочки и мальчика найдётся хотя бы одна , решённая обоими это доказательство потому что они решают 6 одинаковых и 21 делится на 3 без остатка и получается 7
пошаговое объяснение: