$\displaystyle 2n$ students $\displaystyle (n \geq 5)$ participated at table tennis contest, which took $\displaystyle 4$ days. In every day, every student played a match. (It is possible that the same pair meets twice or more times, in different days) Prove that it is possible that the contest ends like this: - there is only one winner; - there are $\displaystyle 3$ students on the second place; - no student lost all $\displaystyle 4$ matches. How many students won only a single match and how many won exactly $\displaystyle 2$ matches? (In the above conditions)
Problem
Source: RMO 2006, 9th grade
Tags: combinatorics proposed, combinatorics
Jumbler
18.11.2006 16:17
Anybody?
mornik
22.06.2007 11:00
This problem was also on Croatian MEMO Selection Test 2007. My solution is as follows: There is obviously 4n victories altogether. Let p be the number of winners' victories. Let d be the number of victories of one of second placed players. Let t be the number of victories of one of the third placed players and let c be the number of victories of one of the fourth placed players (if there are any). Obviously, c<t<d<p and p$\ge$3, d$\ge$2. There are four cases. 1. p=3, d=2, t=1 --- 1*p+3*d+(2n-4)*t=4n, and this leads to 2n=5. Contradiction. 2. p=4, d=2, t=1 --- 1*p+3*d+(2n-4)*t=4n, which leads to n=3. Problem states that n>4. Contradiction. 3. p=4, d=3, t=1 --- 1*p+3*d+(2n-4)*t=4n, 2n=9. Contradiction. 4. p=4, d=3, t=2, c=1 --- let k be the number of third-placed people. Then, 1*p+3*d+k*t+(2n-k-4)*c=4n, therefore k=2n-9. There are 2n-9 players with 2 victories and 5 players with 1 victory. We only have to show that this is actually achievable. Let 1 be the number of first placed player Let 2,3,4 be the numbers of second placed players Let 5..2n-5 be the numbers of third placed players Let 2n-4..2n be the numbers of fourth placed players Winner - loser - day 1 - 2n-4 - 1 1 - 2n-3 - 2 1 - 2n-2 - 3 1 - 2n-1 - 4 2 - 2n - 1 2 - 2n-4 - 2 2 - 2n-3 - 3 3 - 2n-2 - 4 3 - 2n-1 - 1 3 - 2n - 2 4 - 2n-4 - 3 4 - 2n-3 - 4 4 - 2n-2 - 1 5 - 2n-1 - 2 5 - 2n - 3 2n - 2 - 4 2n-1 - 3 - 3 2n-2 - 4 - 2 2n-3 - 5 - 1 2n-4 - 5 - 4 Now we have an even number of players (6..2n-5). Each of them with an even number can play, say, with the player with the following number and win on days 1 and 2 and lose on days 3 and 4. That's, all, folks...