19-я Международная Жаутыковская олимпиада по математике, 2023 год

На плоскость положили несколько синих и зелёных прямоугольных салфеток (возможно, разного размера) с вертикальными и горизонтальными сторонами. Оказалось, что любые две салфетки разного цвета можно пересечь вертикальной или горизонтальной прямой (возможно, по границе). Докажите, что можно выбрать цвет, две горизонтальных прямых и одну вертикальную прямую так, что каждую салфетку выбранного цвета пересекает хотя бы одна из выбранных прямых. ( Г. Челноков )

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

https://izho.kz/wp-content/uploads/2023/02/Day_2_sol_2023.pdf

Все все

Назовите набор салфеток «хорошим», если его можно разрезать горизонтальной линией, и «плохим» в противном случае. Обратите внимание, что «плохие» наборы — это именно те, которые содержат две салфетки, которые можно разделить горизонтальной линией.

Каждая вертикальная линия $\ell$ делит набор синих салфеток на 3 подмножества: салфетки слева, салфетки справа и салфетки, пересекающие линию. Если и левый, и правый сет «хорошие», мы выигрываем.

Если они оба плохие, возьмем два прямоугольника $R_1, R_2$ в правом наборе и $L_1, L_2$ в левом наборе так, чтобы некоторая горизонтальная линия $\ell_R$ разделяла $R_1, R_2$ и некоторую горизонтальную линию $. \ell_L$ делит между $L_1, L_2$. Каждая зеленая салфетка должна пересечь один из $\ell, \ell_R, \ell_L$, чтобы мы выиграли.В завершение мы покажем, что должен существовать $\ell$, чтобы результирующие левое и правое множества находились в одном и том же «состоянии». Действительно, условие «плохого» левого множества открыто на $\ell$, как и условие «плохого» правого множества. Таким образом, это следует из связности $\mathbb{R}$