During a school year 44 competitions were held. Exactly 7 students won in each of the competition. For any two competitions, there exists exactly 1 student who won both competitions. Is it true that there exists a student who won all the competitions?
Problem
Source:
Tags: combinatorics
27.10.2015 14:46
Take any competiton $C$ with winers $1,2,...,7$. Since there is $43$ other competitions one of them, say $1$, must win at least $[43/7 ]+1 = 7$ competitions. Since he also wins at $C$ he wins at least $8$ competitons, say $C, C_1,...C_7$. Now suppose there is competition $B$ he didn't win. Then, since sets $$ B\cap C,\;\;\;\; B\cap C_1,\;\;\;\;B\cap C_2,...,B\cap C_7$$are diferent and nonempty $B$ must have at least $8$ winers. Contradiction.
28.01.2016 18:38
Suppose no one won everything, then every person wins at most $7$ games. Proof: Suppose player $A$ won $8$ or more games and suppose he didn't win competition $C$, then for every competition $D$ won by $A$ there is a person that won $C$ and $D$ (and no other competition won by $A$). Therefore competition $C$ was won by at least $8$ persons, contradiction. Let $p_1,p_2\dots p_n$ be the number of games won by each player, notice $p1+p2+\dots + p_n=44\times 7$, it is easy to show that $\binom{p_1}{2}+\binom{p_2}{2}+\dots \binom{p_n}{2}\leq 44\binom{7}{2}$ (since each $p_i$ is less than $8$). Now notice $44\times \binom{7}{2}<\binom{44}{2}$. Therefore at least one pair of tournaments $T_1,T_2$ was not simmultaneously won by the same player.
26.05.2016 08:28
We can also solve it by Graph Theory.And probably it is how the queston designed.
26.05.2016 09:05
Same as HongKongTST1999