For 31 years, n (>6) tennis players have records of wins. It turns out that for every two players, there is a third player who has won over them before. Prove that for every integer $k,l$ such that $2^{2^k+1}-1>n, 1<l<2k+1$, there exist $l$ players ($A_1, A_2, ... , A_l$) such that every player $A_{i+1}$ won over $A_i$. ($A_{l+1}$ is same as $A_1$)
Problem
Source: 2018 FKMO problem 3
Tags: combinatorics, graph theory
24.03.2018 14:31
cloneofsimo wrote: Prove that for every integer $k,l$ such that $2^{2^k+1}-1>n, 1<l<2k+1$, there exist $l$ players ($A_1, A_2, ... , A_l$) such that every player $A_{i+1}$ won over $A_i$. ($A_{l+1}$ is same as $A_1$) I think it should be For every $k$ such that $2(2^{(2^k)}-1) \ge n$, there exists some $2 \le l \le 2k $ players...
24.03.2018 16:47
I've heard that only one person solve this. (I also tried almost 3 hours, but no idea ) Does anyone know the solution?
26.03.2018 09:10
More better formatting. For $31$ year, $n>6$ tennis players have records of wins it is turns out that for every two players, there is a third player who has won over them before. Prove that for every $k$ such that $2(2^{(2^k)}-1) \ge n$, there exists some $2 \le l \le 2k $ players $A_1, A_2, ... , A_l$ ,such that every player $A_{i+1}$ won over $A_i$. ($A_{l+1}$ is same as $A_1$)
26.03.2018 09:49
$Lemma$: every $m$ players, there is another player who has won all of them. Then, there are at least $2^{m+1}-1$ players. Using this lemma, we can prove this problem easily.
26.03.2018 15:04
jujunghun wrote: $Lemma$: every $m$ players, there is another player who has won all of them. Then, there are at least $2^{m+1}-1$ players. Using this lemma, we can prove this problem easily. That is extremely clever! For those who need more detail: Consider the a new graph $G$ with $V$ the set of players and $v \to w$ if there is a path of length $\le k$. If there is no cycle of length $\le 2k$, then there the graph is simple. By the condition that for any two players, there exists a third player who has won over them before, for each set of $2^k$ vertices $S \subseteq G$, there is another vertex $x$ such that $v \to x$ for every $v \in S$. (Form a perfect binary tree of height $k$, place the vertices of $S$ at the leaves, and fill in the other vertices.) Then by the lemma, there should be at least $2^{2^k + 1} - 1$ players.
18.04.2018 04:28
@above, can you show how to prove the lemma? I tried induct but found it hard to complete...
28.06.2018 08:38
liekkas wrote: @above, can you show how to prove the lemma? I tried induct but found it hard to complete... @above just to find a man with no more than half of the people won him consider the men who had won this man. and then induct.
29.04.2019 00:43
cloneofsimo wrote: For 31 years, n (>6) tennis players have records of wins. It turns out that for every two players, there is a third player who has won over them before. Prove that for every integer $k,l$ such that $2^{2^k+1}-1>n, 1<l<2k+1$, there exist $l$ players ($A_1, A_2, ... , A_l$) such that every player $A_{i+1}$ won over $A_i$. ($A_{l+1}$ is same as $A_1$) Could someone please rephrase this in terms of graph theory? Where do we use the $31$? (Does it mean there are 31 tournaments overlaid on each other or each vertex has degree $31$ or something else?) Sorry I'm not able to understand the question...
01.05.2019 15:00
because it was 31th korea final round. it doesnt mean anything
16.09.2021 11:24
Jettofaiyafukushireikan wrote: liekkas wrote: @above, can you show how to prove the lemma? I tried induct but found it hard to complete... @above just to find a man with no more than half of the people won him consider the men who had won this man. and then induct. Can you post the proof of lemma
16.09.2021 11:24
jujunghun wrote: $Lemma$: every $m$ players, there is another player who has won all of them. Then, there are at least $2^{m+1}-1$ players. Using this lemma, we can prove this problem easily. can you post the proof of lemma please?
18.09.2021 05:15
Jettofaiyafukushireikan wrote: liekkas wrote: @above, can you show how to prove the lemma? I tried induct but found it hard to complete... @above just to find a man with no more than half of the people won him consider the men who had won this man. and then induct. Can you post the proof of lemma?. thank you
07.10.2021 18:36
the proof of the lemma: an observation is that for each vertex u,indeg(u)<=(2^m)-1(by induction),then we have ((2^m)-1)|v|<=|E|<=0.5|v|(|v|-1),which shows that |v|>=(2^(m+1))-1 then we are done.
08.10.2021 19:30
Take some $k$ such that $2(2^{(2^k)}-1) \ge n.$ Consider the directed graph $G$ over the set of players where for two players $p,q,$ $p \to q$ iff $p$ beats $q.$ Consider the directed graph $H$ over the same set of players where for two players $p, q,$ $p \to q$ iff there is a path of length $\le k$ going from $p$ to $q$ in $G.$ The graph is simple, or $p \to q$ and $q \to p$ for some players $p,q$ and we're done already. For any set $S$ of $2^k$ vertices in $G$ and $H,$ we may construct a perfect binary tree with height $k$ with these vertices as the leaves. We fill in the rest of the nodes in this tree from the bottom up as follows: if the two children of a node happen to be identical, we let it be identical to each of these two children, otherwise, we take it to be the vertex that goes to each of the other two in $G$ (it is given that this always exists). The root $r$ now satisfies the property that in the graph $H,$ for any $p \in S,$ $r\to p.$ We are given that such an $r$ exists for any subset $S$ of $2^k$ vertices in $G$ and $H.$ Lemma: Let $m \ge 0$ be an integer. Suppose that for any $m$ vertices in a simple directed graph $H,$ there's a vertex $r$ that goes to each of them. Then there are at least $2^{m+1} - 1$ vertices. We prove this using induction on $m.$ The base case is trivial. For the inductive step, suppose that we have proven the statement for an integer $m\ge 0.$ Suppose that for any $m+1$ vertices in a simple directed graph $H,$ there's a vertex $r$ that goes to each of them. Take a vertex $v$ where no more than half the other vertices go to it. Then the subset $S$ of vertices that go to it must have size at least $2^{m} - 1$ by the inductive hypothesis. (Take any $m-1$ vertices $\in S$ as well as $v$ and there must be a vertex $\in S$ going to each of these.) So the size of $H$ must be at least $2(2^m-1) + 1 = 2^{m+1}-1$ as desired. $\square$ Applying this on $H$ shows us that it has size at least $2^{2^k+1}-1,$ so $2^{2^k+1}-1 \le n \implies 2(2^{(2^k)}-1) < n.$ But $2(2^{(2^k)}-1) \ge n$ so this is contradiction. $\blacksquare$