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...

I've heard that only one person solve this. (I also tried almost 3 hours, but no idea ) Does anyone know the solution?

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$)

$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.

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.

@above, can you show how to prove the lemma? I tried induct but found it hard to complete...

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.

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...

because it was 31th korea final round. it doesnt mean anything

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

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?

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

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.

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$