Several blue and green rectangular napkins (perhaps of different sizes) with vertical and horizontal sides were placed on the plane. It turned out that any two napkins of different colors can be crossed by a vertical or horizontal line (perhaps along the border). Prove that it is possible to choose a color, two horizontal lines and one vertical line, so that each napkin of the chosen color is intersected by at least one of the chosen lines.
Problem
Source: IZHO 2023 P6
Tags: combinatorics
squareman
20.02.2023 18:37
Call a set of napkins good if it can be cut with a horizontal line. Take the rightmost vertical line $l$ so that the green napkins strictly to the left of $l$ are good, and the blue napkins strictly to the left of $l$ are good too. This means there are two same color napkins (not strictly) to the left of $l$ that have not intersecting projections onto the vertical axis (by Helly's theorem). If either the green napkins or the blue napkins strictly to the right of $l$ are good, we are done. Otherwise, we have two same color napkins $L_1, L_2$ (not strictly) to the left of $l$ that have not intersecting projections onto the vertical axis, AND two napkins $R_1, R_2$ of the opposite color strictly to the right of $l$ that have not intersecting projections onto the vertical axis. Suppose $L_1$ above $L_2,$ $R_1$ above $R_2.$ Let $l_1$ be bottom $y$ coordinate of $L_1,$ $l_2$ be upper $y$ coordinate of $L_2.$ Similarly define $r_1, r_2.$ So $l_1 > l_2, r_1 > r_2.$ Since $L_2$ and $R_1$ can be cut by a horizontal line, $l_2 \ge r_1$, similarly $r_2 \ge l_1.$ But now $l_2 \ge r_1 > r_2 \ge l_1,$ contradiction. $\blacksquare$
Phorphyrion
25.02.2023 14:56
I think this is different than the one above:
Call a set of napkins "good" if it can be cut with a horizontal line, and "bad" otherwise. Note that "bad" sets are precisely the ones that contain two napkins, which can be divided by a horizontal line.
Each vertical line $\ell$ splits the set of blue napkins into 3 subsets: the napkins to the left, the napkins to the right, and the napkins intersecting the line. If both the left set and the right set are "good", we win.
If they are both bad, take two rectangles $R_1, R_2$ in the right set and $L_1, L_2$ in the left set, so that some horizontal line $\ell_R$ divides between $R_1, R_2$ and some horizontal line $\ell_L$ divides between $L_1, L_2$. Each green napkin must intersect one of $\ell, \ell_R, \ell_L$ so we win.
To finish, we show that there must exist $\ell$ so that the resulting left and right sets are in the same "state". Indeed, the condition that the left set is "bad" is open on $\ell$, and so is the condition that the right set is "bad". Thus this follows from the connectedness of $\mathbb{R}$.