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
30.12.2022 09:46
Proving we can get to more than $\frac n2$ places in $\sqrt{\dfrac n2}$ steps suffices.
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$
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.
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?
10.07.2023 18:45
We uploaded our solution https://calimath.org/pdf/CNO2022-6.pdf on youtube https://youtu.be/uhobo28S5IU.
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.
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:
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$