A tale of two cities

In an island with 257 cities, there are 2018 railroad segments such that each segment connects exactly 2 cities, and each pair of cities are connected by at most 1 segment. A group of 10 cities is called "clustered" if each pair of those 10 is connected by a segment.

Prove that there exist 2 unconnected cities that we can connect without increasing the number of clustered groups.

Solution

Proof by contradiction. Suppose we cannot connect two cities without increasing the number of clustered groups.

Let $n=257$ be the number of cities. Take all possible groups of 10 cities, ${n \choose 10 }$ of them, and count how many segments there are among them. Of course, if the group is clustered, it should have ${10 \choose 2} = 45$ segments. Let $S$ be the sum of unconnected pairs, over all possible groups of 10 cities.

Now let us count $S$ in a different way. Take 2 connected cities $A$ and $B$. The segment $AB$ contributes to $S$ only when the chosen group of 10 cities include $AB$, so this segment is counted ${n-2 \choose 8}$ times. Because there are 2018 segments, then $S$ must be:

$$S = {n-2 \choose 8}.(2018)$$

Note that $2018 < 2020 = 8n-36$, so $S < {n-2 \choose 8}.(8n-26)$. That means, on average, there are $S / {n \choose 10 }$ segments.

Boys and Girls around the table

$(n+1)$ boys and $n$ girls are seated around a circular table playing a game. One boy started to put a stone on the table, and they subsequently went around the table clockwise. At each child's turn, if that child is a boy, he puts a stone on the table, but if that child is a girl, she takes away one stone from the table. They're finished when everyone has had one turn. If the table ever becomes empty (except before the first boy put his stone), they all lose the game.

Prove that there is a boy such that if he starts, they can complete the round without losing.

Furthermore, prove that there is only one such boy. That is, if any other boy starts, they would lose the game.

Harder version: suppose you now have $m+n$ boys and $n$ girls, with $m$ positive. Prove that there are exactly $m$ boys who could start a non-losing game.