Maths Olympiad Prep

Library / /12 of 28

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

On a table there are 19991999 tea cups with their mouths facing upward initially. In each move, 100100 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 19981998.

Solution

No. In a move, if we choose 100100 cups where kk of them are facing downward and 100k100-k of them are facing upward, then the number of cups facing downward is changed by (100k)k=1002k(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 19991999 cups face downward.

It is possible to make all cups face downward if there are 19981998 cups. If we turn over cups 1,2,,1001, 2, \ldots, 100 and then turn over cups 2,3,,1012, 3, \ldots, 101, we see that only cups 11 and 101101 are turned over. This shows we can turn over any 22 cups after 22 moves. Since 219982 \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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