Hkg TST

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Hong Kong

On a table there are $1999$ tea cups with their mouths facing upward initially. In each move, $100$ of them are turned upside down. After a number of moves, can they be turned so that all their mouths face downward? Why?

Answer the above two questions for the case where the number of cups is $1998$ .

Solution

No. In a move, if we choose $100$ cups where $k$ of them are facing downward and $100-k$ of them are facing upward, then the number of cups facing downward is changed by $(100-k) - k = 100 - 2k$ . Since there is an even number of cups facing downward initially, there is always an even number of cups facing downward. Thus, it is impossible to make all $1999$ cups face downward.

It is possible to make all cups face downward if there are $1998$ cups. If we turn over cups $1, 2, \ldots, 100$ and then turn over cups $2, 3, \ldots, 101$ , we see that only cups $1$ and $101$ are turned over. This shows we can turn over any $2$ cups after $2$ moves. Since $2 \mid 1998$ , we can repeat the same process to turn over all cups.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.