Maths Olympiad Prep

Library / /7 of 9

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it United States

Let a,b,ca, b, c be fixed positive integers. There are a+b+ca+b+c ducks sitting in a circle, one behind the other. Each duck picks either rock, paper, or scissors, with aa ducks picking rock, bb ducks picking paper, and cc ducks picking scissors.
A move consists of an operation of one of the following three forms:
* If a duck picking rock sits behind a duck picking scissors, they switch places.
* If a duck picking paper sits behind a duck picking rock, they switch places.
* If a duck picking scissors sits behind a duck picking paper, they switch places.
Determine, in terms of a,ba, b, and cc, the maximum number of moves which could take place, over all possible initial configurations.

Solution

The maximum possible number of moves is max(ab,ac,bc)\max(ab, ac, bc).
First, we prove this is best possible. We define a feisty triplet to be an unordered triple of ducks, one of each of rock, paper, scissors, such that the paper duck is between the rock and scissors duck and facing the rock duck, as shown. (There may be other ducks not pictured, but the orders are irrelevant.)
Figure 1
Claim — The number of feisty triplets decreases by cc if a paper duck swaps places with a rock duck, and so on.
Proof. Clear. ☐

Obviously the number of feisty triples is at most abcabc to start. Thus at most max(ab,bc,ca)\max(ab, bc, ca) moves may occur, since the number of feisty triplets should always be nonnegative, at which point no moves are possible at all.
To see that this many moves is possible, assume WLOG a=min(a,b,c)a = \min(a, b, c) and suppose we have aa rocks, bb papers, and cc scissors in that clockwise order.
Figure 2
Then, allow the scissors to filter through the papers while the rocks stay put. Each of the bb papers swaps with cc scissors, for a total of bc=max(ab,ac,bc)bc = \max(ab, ac, bc) swaps.

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 and solution reproduced as published; topic and difficulty added by this site.