Competition problem — Combinatorics

Library / /9 of 11

Combinatorics Difficulty 8.9 Shortlist Prove it United States

Let $n$ be a positive integer. Tasty and Stacy are given a circular necklace with $3n$ sapphire beads and $3n$ turquoise beads, such that no three consecutive beads have the same color. They play a cooperative game where they alternate turns removing three consecutive beads, subject to the following conditions:
* Tasty must remove three consecutive beads which are turquoise, sapphire, and turquoise, in that order, on each of his turns.
* Stacy must remove three consecutive beads which are sapphire, turquoise, and sapphire, in that order, on each of her turns.
They win if all the beads are removed in $2n$ turns. Prove that if they can win with Tasty going first, they can also win with Stacy going first.

Solution

Observe that the condition about not having three consecutive matching beads is equivalent to saying there are no zigzag of lengths 1.

The main claim is that the game is winnable (for either player going first) if and only if there are at most $2n$ dividers. We prove this in two parts, the first part not using the hypothesis about three consecutive letters.

Claim. The game cannot be won with Tasty going first if there are more than $2n$ dividers.

Proof. We claim each move removes at most one divider, which proves the result.

Consider removing a TST in some zigzag (necessarily of length at least 3). We illustrate the three possibilities in the following table, with Tasty's move shown in red.

Before	After	Change
...ST	<span style="color:red;">TST</span>	TS...	...ST	TS...	One less divider; two zigzags merge
...ST	<span style="color:red;">TST</span>TST...	...STST...	One less divider; two zigzags merge
...<span style="color:red;">TSTS</span>...	...S	S...	One more divider; a zigzag splits in two

The analysis for Stacy's move is identical. ☐

Claim. If there are at most $2n$ dividers and there are no zigzags of length 1 then the game can be won (with either player going first).

Proof. By symmetry it is enough to prove Tasty wins going first.

At any point if there are no dividers at all, then the necklace alternates TSTST... and the game can be won. So we will prove that on each of Tasty's turns, if there exists at least one divider, then Tasty and Stacy can each make a move at an endpoint of some zigzag (i.e. the first two cases above). As we saw in the previous proof, such moves will (a) decrease the number of dividers by exactly one, (b) not introduce any singleton zigzags (because the old zigzags merge, rather than split). Since there are fewer than $2n$ dividers, our duo can eliminate all dividers and then win.

Note that as the number of S and T's are equal, there must be an equal number of
* zigzags of odd length ( $\ge 3$ ) with T at the endpoints (i.e. one more T than S), and
* zigzags of odd length ( $\ge 3$ ) with S at the endpoints (i.e. one more S than T).

Now iff there is at least one of each, then Tasty removes a TST from the end of such a zigzag while Stacy removes an STS from the end of such a zigzag.

Otherwise suppose all zigzags have even size. Then Tasty finds any zigzag of length $\ge 4$ (which must exist since the average zigzag length is 3) and removes TST from the end containing T. The resulting merged zigzag is odd and hence S endpoints, hence Stacy can move as well. ☐

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.