A chess tournament had 10 participants. Each round, the participants split into pairs, and each pair played a game. In total, each participant played with every other participant exactly once, and in at least half of the games both the players were from the same town. Prove that during each round there was a game played by two participants from the same town. (Boris Frenkin)
Problem
Source:
Tags: combinatorics
lifeisgood03
30.01.2018 14:04
There are a total of $\binom{10}{2}=45$ games played, so there must be at least 23 games in which two players from the same town. By the Pigeonhole Principle, if there are at least six people from the same round, there must be two players playing each other from the same town. Lemma: $\binom{a}{2}+\binom{b}{2}\le \binom{a+b}{2}$ This is just expansion: $$2ab+a^2+b^2-a-b\ge a^2+b^2-a-b$$$$(a+b)(a+b-1)\ge a(a-1)+b(b-1)$$$$\binom{a+b}{2}\ge \binom{a}{2}+\binom{b}{2}$$$\blacksquare$ Assume for the sake of contradiction that the number of students from each town is less than or equal to 5. If there are two towns, then both have exactly 5 students. If there are three or more towns (say, k towns), the number of pairs of towns is $\binom{k}{2}$ and the sum of the number of students in those pairs is $10(k-1)$, so the average number of total students in a pair of towns is $$\frac{20}{k}\le \frac{20}{3}$$This means there exists at least one pair of towns such that the sum of the number of students in those two towns is less than or equal to 6. This implies that every arrangement of the number of towns can be simplified using our lemma to either an arrangement of two towns with 5 and 5 students or two towns with 6 and 4 students. However, we can easily confirm that $\binom{5}{2}+\binom{5}{2}< 23$ and $\binom{6}{2}+\binom{4}{2}<23$, which contradicts the statement where half of the games had two players from the same town. Thus, there must be at least 6 players from the same town, so each round had a game played by two participants from the same round.$\blacksquare$
enthusiast101
19.06.2019 14:02
First, note that the number of games played is $t_9=45$ and if at least half were played between $2$ from the same town, it implies that at least $23$ were played by people from the same town. Now if we had $2$ people from the same town, at most $1$ game can be played where both players are from the same town. If we add a person who belongs to that town, at most $2$ more games can be played. Again, if we add another person, at most $3$ more games can be played. Notice that at most $t_n$ games can be played where both players are from same town where $n$ is number of people from the town. Note that we have minimised the number of players from the same town required to play the games. So the least value of $n$ for which $t_n \geq 23$ is the least number of players for which $23$ or more games can be played with $2$ people in the same town.
The value of $n$ is clearly $n \geq 7$.
Hence there are at least $7$ players from the same town. $7 \geq 5$ and we are done.
anser
15.08.2019 05:05
For the sake of contradiction, suppose during some round each game is between two participants from different towns. Then there are no more than 5 participants from any town. The number of games between participants from the same town is maximized when there are 5 participants from each of two towns, but this maximum is $2\binom{5}{2}=20<\frac{45}{2}$, a contradiction.
ChCar
01.11.2022 17:17
There are exactly $\binom{10}{2}=45$ games. Let $M$ be the set of games played by participants of the same town . By hypothesis $|M| \ge 23$. Let $n$ be the number of participants from this town.
Notice that $21 = \binom{7}{2} < 23 \le |M|$. Thus $n \ge 7$ . There $9$ round of $5$ games each, then by pigeonhole principle there are at least $2$ participants of the same Town taking part in each game, in each round.