Andriyko has rectangle desk and a lot of stripes that lie parallel to sides of the desk. For every pair of stripes we can say that first of them is under second one. In desired configuration for every four stripes such that two of them are parallel to one side of the desk and two others are parallel to other side, one of them is under two other stripes that lie perpendicular to it. Prove that Andriyko can put stripes one by one such way that every next stripe lie upper than previous and get desired configuration. Proposed by Denys Smirnov
Problem
Source: Ukraine TST 2017
Tags: combinatorics, rectangle
Pathological
12.05.2019 03:09
Let's create a digraph $G$ where the vertices correspond to the stripes, and vertex $v$ points to vertex $w$ if the stripe corresponding to $v$ is on top of the stripe corresponding to $w$. Notice that $G$ is a complete bipartite graph (with sets corresponding to the horizontal and vertical stripes). Notice that we only need to show that $G$ contains no cycles, since this is well-known to imply the existence of an ordering like the one desired (basically repeatedly select a vertex with outdegree $0$ and remove it). Assume, for contradiction, that $G$ had a cycle. Consider the cycle $v_1 \Rightarrow v_2 \Rightarrow v_3 \Rightarrow \cdots \Rightarrow v_{2k} \Rightarrow v_1$ of minimum length, where we know that it has even length because $G$ is bipartite. We claim that it has length exactly $4$. Clearly, it must have length greater than $2$. If it had length greater than $4$, then casework on whether $v_1 \Rightarrow v_4$ or $v_4 \Rightarrow v_1$ allows us to split it, contradicting the minimality of the cycle. Therefore, we can conclude that there exists a cycle of length $4$, contradiction to the condition of the problem (consider applying the condition on these four stripes). $\square$
math90
14.05.2019 12:34
Do stripes mean segments?
Pathological
18.05.2019 21:03
@above Interestingly, when I read this problem I was reminded of an apple pie (see attached image). I think that stripes have nonzero but negligible width and can overlap each other however they want, as specified by the problem.
Attachments:
