Let $x_1$ and $x_2$ be positive integers. On a straight line, $y_1$ white segments and $y_2$ black segments are given, with $y_1 \ge x_1$ and $y_2 \ge x_2$. Suppose that no two segments of the same colour intersect (and do not have common ends). Moreover, suppose that for any choice of $x_1$ white segments and $x_2$ black segments, some pair of selected segments will intersect. Prove that $(y_1-x_1)(y_2-x_2)<x_1x_2$. Proposed by G. Chelnokov
Problem
Source: All-Russian MO 2024 10.7
Tags: combinatorics, combinatorics proposed
29.04.2024 16:37
I've been thinking about this for so long, but I couldn't find any solution better than this . Hope to see more creative ideas. Consider the segments as the vertices of a graph $G$ with the same color, two vertices are adjacent iff two corresponding segments intersect. Then, the degree of every vertex in $G$ is not more than $2$. Moreover, $G$ does not consist of any cycles, hence, it is the disjoint union of path graphs. Among these, denote $u,v,w$ as the number of white subgraphs (where two endpoints are white), black subgraphs (where two endpoints are black), and multicolor subgraphs (where two endpoints have different colors), respectively. Besides, let $\left(a,b\right) =\left(x_1, y_2 - x_2\right)$. Observe that no independent set contains $a$ white vertices and $y_2 - b$ black vertices, hence, for every choice of $a$ white vertices, there exist $b+1$ black ones adjacent to at least one of them. We need to prove $$\frac{a}{b}>\frac{y_1}{y_2}\text{ }(1)$$Now, place the subgraphs on the parallel lines, and we will consider the vertices from left to right. Case 1. $u$ white subgraphs have at least $a$ white vertices. Then starting from the smallest white subgraphs, we choose the white vertices from left to right. When choosing all the vertices in one subgraph, we continue the process in the 2nd smallest, 3rd smallest, etc until we have chosen $a$ white vertices. Let $\lambda$ be the number of white subgraphs where all of their vertices are chosen. Then, there are $a - \lambda$ black vertices adjacent to at least one of them $\Rightarrow b\leq a - \lambda - 1$. Moreover, we easily see that $y_2 \geq y_1 - u$. Hence, we only need to prove $$\frac{a}{a - \lambda - 1} > \frac{y_1}{y_1 - u}$$$\Leftrightarrow y_1 > \frac{au}{\lambda + 1}$, which is true since the $\lambda + 1$ subgraphs where $a$ white chosen vertices are located are the smallest among $u$ white subgraphs. Case 2. $u$ white subgraphs and $w$ multicolor subgraphs have at least $a$ white vertices, but $u$ white subgraphs do not. Then $b+1\leq a - u$. Moreover, $y_2 \geq y_1 - u$. Hence, $\frac{y_1}{y_2} \leq \frac{y_1}{y_1 -u} \leq \frac{a}{a-u}< \frac{a}{b}$. Case 3. $u$ white subgraphs and $w$ multicolor subgraphs have less than $a$ white vertices. Choose all the white vertices in these subgraphs. Then starting from the biggest black subgraphs, we choose the white vertices from left to right. When choosing all the vertices in one subgraph, we continue the process in the 2nd biggest, 3rd biggest, etc until we have chosen $a$ white vertices. Let $\theta$ be the number of black subgraphs where we choose the white graphs. Then we have $b+1\leq a - u + \theta$, and $y_2 = y_1 - u + v$. If $u\geq \theta$, then $\frac{y_1}{y_2} \leq \frac{y_1}{y_1 - u + \theta} \leq \frac{a}{a - u + \theta} < \frac{a}{b}$. If $u < \theta$, we have $\frac{y_1}{y_1 - u + v} <\frac{a}{a - u + \theta - 1}\Leftrightarrow y_1\left(\theta - u-1\right) < a\left(v - u\right)$. Let $S$ be the number of white vertices in the white and multicolor subgraphs, by maximality of black subgraphs, we have $\frac{y_1 - S}{v} < \frac{a - S}{\theta - 1}\Rightarrow \frac{y_1}{v} < \frac{a}{\theta - 1}\Rightarrow y_1\left(\theta - u -1\right) < a\left(v - u\right)$. $(1)$ has been proven. We finish our proof here.
29.07.2024 22:41
Number the white segments $1,\ldots,y_1$ from left to right and do the same for the black ones. Construct a grid with $y_1$ rows and $y_2$ columns, and mark $(i,j)$ if white segment $i$ and black segment $j$ intersect. The conditions imply that if $(i_1,j_1)$ and $(i_2,j_2)$ are marked then we can't have $i_1>i_2$ and $j_1<j_2$ or $i_1<i_2$ and $j_1>j_2$, i.e. marked cells must progress (nonstrictly) towards the "bottom right". The problem condition means that every intersection of $x_1$ rows and $x_2$ columns must have at least one marked cell, which equivalently means for any $x_1$ rows there must be at least $y_2-x_2+1$ columns containing a marked cell in one of these rows. We now mark some additional cells as follows: write down marked cells $(i,j)$ in increasing order of $i+j$, adding $(1,1)$ and $(y_1,y_2)$ if not already present; note the conditions imply all $i+j$ values are distinct. Then for any two consecutive marked cells $(i_1,j_1)$ and $(i_2,j_2)$, additionally mark $(i_1+1,j_1),\ldots,(i_2,j_1),(i_2,j_1+1),\ldots,(i_2,j_2-1)$. When this is done, the marked cells form a single connected "down-right" path from $(1,1)$ to $(y_i,y_j)$. Obviously the problem condition still holds here. Now let $a_i$ denote the number of marked cells in row $i$ for each $i$, so we have $a_1+\cdots+a_{y_1}=y_1+y_2-1$. Consider the number of columns containing a marked cell also in some set of $t$ consecutive rows $k,\ldots,k+t-1$. This quantity will clearly equal $a_k+\cdots+a_{k+t-1}$, minus the number of times some two rows $i,i+1$ have a marked cell in the same column (note that when this happens there's exactly one such column), but since marked cells form a path this latter quantity is just $k-1$. In particular, for any $x_1$ consecutive rows $k,\ldots,k+x_1-1$ there will be $a_k+\cdots+a_{k+x_1-1}-(x_1-1)$ such columns. Furthermore, for any $x_1$ "consecutive wraparound rows" $y_1-t+1,\ldots,y_1,1,\ldots,t$ there will be at most $a_{y_1-t+1}+\cdots+a_{y_1}+a_1+\cdots+a_{t-1}-(x_1-2)$ such columns. All of these quantities should be at least $y_2-x_2+1$, so by summing we have $$x_1(a_1+\cdots+a_{y_1})-y_1(x_1-1)+(x_1-1) \geq y_1(y_2-x_2+1) \iff x_1y_1+x_1y_2-x_1-x_1y_1+y_1+x_1-1 \geq y_1y_2-y_1x_2+y_1 \iff x_1y_2+y_1x_2 \geq y_1y_2+1,$$which is equivalent to $x_1x_2 \geq (y_1-x_1)(y_2-x_2)+1$ as desired. $\blacksquare$