Competition problem — Combinatorics

Library / /13 of 16

Combinatorics Difficulty 6.7 National Olympiad Prove it United States

Problem:

King Arthur and his 100 knights are having a feast at a round table. Each person has a glass with white or red wine in front of him. Exactly at midnight, every person moves his glass in front his left neighbor if the glass has white wine, or in front of his right neighbor if the glass has red wine. It is known that there is at least one glass with red and one glass with white wine.

a. Prove that after midnight there will be at least one person without a glass of wine in front of him.

b. If Lady Guinivera, the Queen, calls the King off the table before midnight, will the conclusion of part (a) still going to be correct?

Solution

Solution:

a. Suppose not. Label all seats as $1,2, \ldots, 101$ by going around the table anticlockwise. If each person still has a glass after midnight, then no one has received glasses from both of his neighbors, i.e. any two people with exactly one person between must have the same color wine. Thus, the following seats must correspond to the same color wine: $1,3,5, \ldots, 99,101,2,4, \ldots, 98,100$ . But these are all seats - this contradicts the hypothesis that there are glasses with red and glasses with white wine! Therefore, the supposition is wrong, and at least one person will be left without a glass after midnight.

b. The conclusion won't be correct. For example, give white wine to all odd seated people $1,3,5, \ldots, 99$ , and red wine to all even seated people $2,4,6, \ldots, 100$ . After midnight the two groups will switch the colors of their wines.

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.