There are $n(n\ge 8)$ airports, some of which have one-way direct routes between them. For any two airports $a$ and $b$, there is at most one one-way direct route from $a$ to $b$ (there may be both one-way direct routes from $a$ to $b$ and from $b$ to $a$). For any set $A$ composed of airports $(1\le | A| \le n-1)$, there are at least $4\cdot \min \{|A|,n-|A| \}$ one-way direct routes from the airport in $A$ to the airport not in $A$. Prove that: For any airport $x$, we can start from $x$ and return to the airport by no more than $\sqrt{2n}$ one-way direct routes.
Problem
Source: China MO 2023 P6
Tags: combinatorics, directed graph, graph cycles
a22886
30.12.2022 09:46
Proving we can get to more than $\frac n2$ places in $\sqrt{\dfrac n2}$ steps suffices.
squareman
31.12.2022 18:41
Let $x$ be the given vertex. Let $a_{i}$ be the number of vertices distance $i$ away from $x$. So first $a_0 = 1$ ($x$ itself). As above states, we want to prove $a_0+ a_1 + \dots + a_{\lfloor \sqrt{n/2} \rfloor} > \frac{n}{2}.$ Suppose FTSOC $a_0+a_1+ \dots +a_{i} \le \frac{n}{2}$ for all $i \le \lfloor \sqrt{n/2} \rfloor,$ but now (take $A$ as all vertices distance $i-1$ or less of $x$) $$a_{i} \ge 4 \left(\frac{a_0+a_1+ \dots + a_{i-1}}{a_{i-1}} \right)$$ for all $i \le \lfloor \sqrt{n/2} \rfloor.$ We claim $a_0 + a_1 + \dots + a_{k} \ge (k+1)^2$ for all $0 \le k \le \lfloor \sqrt{n/2} \rfloor$ with induction which achieves contradiction. Base case trivial. Inductive step: suppose FTSOC $a_0 + a_1 + \dots + a_{k} < (k+1)^2$ and $a_0 + a_1 + \dots + a_{k-1} \ge k^2,$ but now $a_k < (k+1)^2 - k^2 = 2k+1 \implies a_k \le 2k.$ But also, $$k^2 + \frac{4k^2}{a_{k-1}} \le (a_0 + a_1 + \dots + a_{k-1}) + a_{k} < (k+1)^2$$so $1+\frac{4}{a_{k-1}} < \frac{(k+1)^2}{k^2} \implies a_{k-1} > \frac{4k^2}{2k+1} > 2k-1 \implies a_{k-1} \ge 2k \ge a_{k},$ contradiction. $\blacksquare$
AirCircles
10.01.2023 07:59
a22886 wrote: Proving we can get to more than $\frac n2$ places in $\sqrt{\dfrac n2}$ steps suffices. This doesn’t work at a particularly special case where $n=17$, two steps are only guaranteed to get to 8 different places. However, it works in any other cases, I suppose.
gghx
12.01.2023 16:10
squareman wrote: Let $x$ be the given vertex. Let $a_{i}$ be the number of vertices distance $i$ away from $x$. So first $a_0 = 1$ ($x$ itself). As above states, we want to prove $a_0+ a_1 + \dots + a_{\lfloor \sqrt{n/2} \rfloor} > \frac{n}{2}.$ Suppose FTSOC $a_0+a_1+ \dots +a_{i} \le \frac{n}{2}$ for all $i \le \lfloor \sqrt{n/2} \rfloor,$ but now (take $A$ as all vertices distance $i-1$ or less of $x$) $$a_{i} \ge 4 \left(\frac{a_0+a_1+ \dots + a_{i-1}}{a_{i-1}} \right)$$ for all $i \le \lfloor \sqrt{n/2} \rfloor.$ We claim $a_0 + a_1 + \dots + a_{k} \ge (k+1)^2$ for all $0 \le k \le \lfloor \sqrt{n/2} \rfloor$ with induction which achieves contradiction. Base case trivial. Inductive step: suppose FTSOC $a_0 + a_1 + \dots + a_{k} < (k+1)^2$ and $a_0 + a_1 + \dots + a_{k-1} \ge k^2,$ but now $a_k < (k+1)^2 - k^2 = 2k+1 \implies a_k \le 2k.$ But also, $$k^2 + \frac{4k^2}{a_{k-1}} \le (a_0 + a_1 + \dots + a_{k-1}) + a_{k} < (k+1)^2$$so $1+\frac{4}{a_{k-1}} < \frac{(k+1)^2}{k^2} \implies a_{k-1} > \frac{4k^2}{2k+1} > 2k-1 \implies a_{k-1} \ge 2k \ge a_{k},$ contradiction. $\blacksquare$ How is $a_{k-1}\ge a_k$ a contradiction?
Cali.Math
10.07.2023 18:45
We uploaded our solution https://calimath.org/pdf/CNO2022-6.pdf on youtube https://youtu.be/uhobo28S5IU.
gghx
27.11.2023 16:35
gghx wrote: How is $a_{k-1}\ge a_k$ a contradiction? Bump this because its time for CMO again! I had this exact solution in contest and it was flawed so unless i missed something this solution is wrong.
Phorphyrion
27.11.2023 17:02
Cali.Math wrote: We uploaded our solution https://calimath.org/pdf/CNO2022-6.pdf on youtube https://youtu.be/uhobo28S5IU. The solution in this video is correct. Here's a paraphrased version:
For a set $A$ of vertices, let $J^+(A)$ be the set of outgoing edges and $N^+(A)$ the set of destinations of the elements of $J^+(A)$. Let $M^+(A)=A\cup N^+(A)$. We first prove:
Lemma: If $0<|M^+(A)|\leq \frac{n}{2}$, then
\[|M^+(M^+(A))|\geq |A|+4\sqrt{|M^+(A)|}\]Proof: There exists a vertex in $N^+(A)$ with at least $\frac{|J^+(M^+(A))|}{|N^+(A)|}$ outgoing edges exiting $M^+(A)$. This vertex shows $|N^+(M^+(A))|\geq \frac{|J^+(M^+(A))|}{|N^+(A)|}$. Now,
\[|M^+(M^+(A))|=|A|+|N^+(A)|+|N^+(M^+(A))|\geq |A|+2\sqrt{ |N^+(A)|\cdot |N^+(M^+(A))|}\geq |A|+2\sqrt{|J^+(M^+(A))|}\]By the condition, this is at least $|A|+2\sqrt{4\min(|M^+(A)|, n-|M^+(A)|)}=|A|+4\sqrt{|M^+(A)|}$ (using $|M^+(A)|\leq \frac{n}{2}$).$\blacksquare$
Now, use the lemma to show $|(M^+)^i(\{x\})|\geq (i+1)^2$ as long as $|(M^+)^{i-1}({x})|\leq \frac{n}{2}$. This shows that using $m=\lfloor\sqrt{n/2}\rfloor$ moves one may reach more than $n/2$ vertices. This is enough for $n$ even. For odd $n$ one needs to work a bit harder. If $|(M^\pm)^k({x})|>n/2$ for some $k<m$ we are done. Similarly if $2m+1\leq \sqrt{2n}$ we are also done. Otherwise, we know $|(M^+)^m({x})|\geq (m+1)^2$ and $|(M^-)^m({x})|\geq (m+1)^2$, so
\[|(M^+)^m({x})|+|(M^-)^m({x})|\geq 2(m+1)^2\geq 2(\sqrt{n/2}+1/2)^2>n+2\sqrt{n/2}\geq n+1\]which again wins.
EthanWYX2009
08.12.2024 16:59
This is just a BFS problem. say there are $a_i$ vertices on $i$-th layer, use condition on $L_1\cup\cdots\cup L_i$ to get $4(a_1+\cdots +a_{i})\le a_ia_{i+1}.$ Prove $\sum_{i=1}^ka_i\ge k^2$ by induction and get contradiction by taking $k=\lfloor\sqrt{n/2}\rfloor.\Box$