There are some players in a Ping Pong tournament, where every $2$ players play with each other at most once. Given: (1) Each player wins at least $a$ players, and loses to at least $b$ players. ($a,b\geq 1$) (2) For any two players $A,B$, there exist some players $P_1,...,P_k$ ($k\geq 2$) (where $P_1=A$,$P_k=B$), such that $P_i$ wins $P_{i+1}$ ($i=1,2...,k-1$). Prove that there exist $a+b+1$ distinct players $Q_1,...Q_{a+b+1}$, such that $Q_i$ wins $Q_{i+1}$ ($i=1,...,a+b$)
Problem
Source: 2015 China Tst 1 Day 2 Q3
Tags: combinatorics, combinatorics proposed, China TST, 2015, China
MellowMelon
14.03.2015 23:37
Are draws are allowed? I assume so, since otherwise, a top cycle exists, it consists of the whole tournament by (2), and the whole tournament contains at least $a+b+1$ players by (1).
61plus
15.03.2015 01:44
It is not specified in the qn
yugrey
15.03.2015 01:49
"Every two players play each other exactly once" is redundant if there are draws, so there are probably not. I also do not think that ping pong has draws.
Take a maximal cycle $P_1...P_n$. Because $P_1P_2...P_n$ is maximal (call P_1 through P_n normal), then all other players either beat all these (call them pro) or lose to all these (call them sucky) lest they be inserted in the cycle. But then if $Q$ beats all these, $R$ loses to all these, and $R$ beats $Q$ then $P_1...P_nRQ$ is a cycle, which is oops. So then any pro player beats any sucky or normal player, and any normal player beats any sucky player, so from condition 2) that makes every player normal. But then there are at least $a+b+1$ people so we're done.
http://www.artofproblemsolving.com/community/c6h289586p1566054
Essentially this is another way to just get that condition 2) giving a Hamiltonian cycle in a directed complete graph, and in fact it gives this even stronger result.
Of course if draws are allowed none of this holds.
MellowMelon
15.03.2015 03:54
I now have a solution for the problem where draws are allowed. Not the hardest problem ever, but much trickier than the tournament case. It seems reasonable to assume that the problem intended to allow missing edges.
Take the longest path $v_1, v_2, \ldots, v_\ell$ and suppose $\ell \le a+b$. Notice that $v_\ell$'s $a$ wins must all be within this path; let $W$ be the set of the numbers of these vertices. Similarly $v_1$ must lose $b$ times within this path, so let $L$ be the indices of these vertices. Show that $W,L \subseteq \{3,4,\ldots,\ell-2\}$.
Define $W' = \{x-1 \mid x \in W, x \le \max L\}$ and $L' = \{x+1 \mid x \in L, x \ge \min W\}$. A quick investigation will show you that for any $x \in L'$, the vertices of our path can be reordered so that $v_x$ is the first vertex, and similarly any $x \in W'$ allows a reordering with $v_x$ being the last vertex. With some computation and $\ell \le a+b$, one can verify that $W$ and $L$ are large enough to force $W' \cap L'$ to be nonempty. This gives a vertex $v_x$ which could be the first or last vertex. All of $v_x$'s wins and losses must occur within the path, and thus the path must have at least $a+b$ other vertices as desired.
EDIT: On a second look, I don't think I used the second condition anywhere in this method...
61plus
15.03.2015 05:43
Sry I misitepreted the problem, should be that they play each other at most one, and a typo in $P_2=B$. No difference from draw though.
61plus
15.03.2015 05:48
I cant edit on mobile, so can any mod help with changing $P_2=B$ to $P_k=B$ (Fixed. -Melon)
MathPanda1
15.03.2015 22:24
Is proving the problem where draws are allowed stronger than proving the problem where draws are not allowed?
MellowMelon
15.03.2015 23:14
Well, yes, since even if draws were allowed, there may not have been any, so tournaments become a special case. The version of the problem that required every pair of players to play (a tournament) is easy and just a result of a mistranslation. The test really asked about the case where the digraph is not complete.
toto1234567890
07.04.2015 18:01
Anyone has solutions?
don2001
26.10.2017 18:34
Could you please give me some guidance ? Thank you.
Dan37kosothangnao
24.11.2021 06:36
hello does anyone has a solution, thank you
mathloverwww
26.01.2024 11:08
MellowMelon wrote: Well, yes, since even if draws were allowed, there may not have been any, so tournaments become a special case. The version of the problem that required every pair of players to play (a tournament) is easy and just a result of a mistranslation. The test really asked about the case where the digraph is not complete. so what is the hardest problem ever , can you please tell me thank you
mathloverwww
07.05.2024 12:02
very difficult and very long. i finally solve it(if i havent misundertsanding the meaning of condition 2),but delete it when typing by accident. MellowMelon your solution seems has some mistake,e.g.a<b<c<d<e<f exist f<x<a let f<d<a(this is assumption) then e<f<d<a<b<c , then x may be d again(it is possible),it will become the original path
mathloverwww
07.05.2024 12:13
(i guess k is constant of longest path for fixed a and b. here is what a and b stand for:at least $a$ players, and loses to at least $b$ players. E.g. longest path a<b<c<d k=4, d<?<?<a k also is 4, b<?<?<d also k is 4 but win and lose =>2) then prove that no matter which two numbers are first vertice and last vertice, it elements are consisting of the remaining elements of the original path.