42-я Международная Математическая OлимпиадаСоединённые Штаты Америки, Вашингтон, 2001 год

В математической олимпиаде приняли участие 21 мальчик и 21 девочка. Известно, что:
— каждый из них решил не более шести задач;
— для каждого мальчика и каждой девочки найдется по крайней мере одна задача, которая была решена ими обоими.
Докажите, что найдется задача, которую решили хотя бы 3 мальчика и 3 девочки.

Комментарий/решение

Мы покажем противоположное. То есть предположим, что

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

• Предположим, что каждую проблему решают в основном девочки (максимум два мальчика) или преимущественно мальчики (максимум две девочки).

Затем мы докажем, что тогда какой-то участник решил более шести задач.

Создайте сетку 21 × 21, в которой мальчики будут столбцами, а девочки — строками, и в каждой ячейке напишите название задачи, которую решила пара. Раскрасьте ячейку в зеленый цвет, если эту задачу решили не более двух девочек, и в синий цвет, если эту задачу решили не более двух мальчиков. (G — девочка, B

для мальчика. Возможно, для какой-то ячейки используются оба цвета.)

WLOG, зеленых ячеек больше, чем синих, поэтому (по ячейке) возьми столбик (мальчик)

с этим свойством. Это означает, что в столбце мальчика есть как минимум 11 зеленых квадратов. По гипотезе это соответствует как минимум 6 решенным различным задачам. Теперь есть два случая:

• Если есть квадраты только синего цвета, то этот квадрат означает седьмую отдельную проблему.

• Если весь столбец зеленый, то среди 21 зеленого квадрата в этом столбце решено как минимум 11 различных задач.

Замечание. Число 21 уменьшить нельзя. Вот пример 20 мальчиков и 20 девочек, которые решают задачи с именами A-J и 0-9, что с самого начала мотивирует их решение. Замечание. Это заняло у меня пугающе много времени, но, похоже, частью работы над проблемой был поиск правильной «структуры данных», чтобы закрепиться. Я считаю, что сетка хороша тем, что мы хотим заполнить каждое пересечение, а затем рассматриваем для каждой ячейки задачу, которую нужно поставить.

Изначально я хотел получить полные данные, записывая в каждую зеленую ячейку индекс строки другой девушки, которая ее решила, и то же самое для синих ячеек. (Это естественным образом привело к цветам: было два типа ячеек.) Это действительно помогло найти приведенный выше случай равенства, но как только я осознал случай равенства, я также понял, что могу отбросить лишнюю информацию и запомнить только цвета.