Skip to main content
OlympiadHQ

Browse · MathNet

Print

USA TSTST

United States counting and probability

Problem

Let be fixed positive integers. There are ducks sitting in a circle, one behind the other. Each duck picks either rock, paper, or scissors, with ducks picking rock, ducks picking paper, and 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 , and , the maximum number of moves which could take place, over all possible initial configurations.

problem


problem
Solution
The maximum possible number of moves is . 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.) Claim — The number of feisty triplets decreases by if a paper duck swaps places with a rock duck, and so on. Proof. Clear. ☐

Obviously the number of feisty triples is at most to start. Thus at most 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 and suppose we have rocks, papers, and scissors in that clockwise order. Then, allow the scissors to filter through the papers while the rocks stay put. Each of the papers swaps with scissors, for a total of swaps.
Final answer
max(ab, ac, bc)

Techniques

Invariants / monovariantsColoring schemes, extremal arguments