Official solutions post (also at http://web.evanchen.cc/problems.html): In the necklace, we draw a divider between any two beads of the same color. Unless there are no dividers, this divides the necklace into several zigzags in which the beads in each zigzag alternate. Each zigzag has two endpoints (adjacent to dividers). Observe that the condition about not having three consecutive matching beads is equivalent to saying there are no zigzags of lengths $1$. [asy][asy] size(7cm); string[] s = {"T", "S", "S", "T", "T", "S", "T", "T", "S", "T", "T", "S", "S", "T", "S", "T", "S", "S", "T", "S", "S", "T", "S", "T"}; pen[] colors = {white, red, deepgreen, blue, heavygreen, grey, purple, orange, deepcyan}; int j = 0; for (int i=0; i<24; ++i) { if ((i == 0) || (s[i] == s[i-1])) { ++j; draw(0.9*dir(187.5-15*i)--1.1*dir(187.5-15*i), black+1.5); } label(s[i], dir(180-15*i), dir(180-15*i), colors[j]); } draw(unitcircle); [/asy][/asy] 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. Check that each move removes at most one divider, which proves the result. $\blacksquare$ 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\dots$ 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. $\blacksquare$ Remark: There are many equivalent ways to phrase the solution. For example, the number of dividers is equal to the number of pairs of two consecutive letters (rather than singleton letters). So the win condition can also be phrased in terms of the number of adjacent pairs of letters being at least $2n$, or equivalently the number of differing pairs being at least $4n$. Remark: The constraint of no three consecutive identical beads is actually needed: a counterexample without this constraint is $\mathtt{TTSTSTSTTSSS}$. (They win if Tasty goes first and lose if Stacy goes first.) Remark: Many contestants attempted induction. However, in doing so they often implicitly proved a different problem: ``prove that if they can win with Tasty going first without ever creating a triplet, they can also win in such a way with Stacy going first''. This essentially means nearly all induction attempts fail. Amusingly, even the modified problem (which is much more amenable to induction) sill seems difficult without some sort of global argument. Consider a position in which Tasty wins going first, with the sequence of winning moves being Tasty's first move in red below and Stacy's second move in blue below: \[ \dots \mathtt{TTSSTT} \underbrace{\mathtt{\color{blue}S} \overbrace{\mathtt{\color{red}TST}}^{\text{Tasty}} \mathtt{\color{blue}TS}}_{\text{Stacy}} \mathtt{STTSST} \dots. \]There is no ``nearby'' $STS$ that Stacy can remove instead on her first turn, without introducing a triple-$T$ and also preventing Tasty from taking a $TST$. So it does not seem possible to easily change a Tasty-first winning sequence to a Stacy-first one.

Is it exactly $2n$ or less than equal to?

hellomath010118 wrote: Is it exactly $2n$ or less than equal to? I mean, there are $6n$ beads and three beads are removed each turn, so it's not really relevant...

Define a block to be a maximal contiguous substring of the necklace with alternating colors. We claim that they can win with Tasty going first if and only if the number of blocks is at most $2n$. By symmetry then, they win with Stacy going first if and only if there are at most $2n$ blocks, so they win with Tasty going first if and only if they win with Stacy going first. First, suppose they can win. Note that each removal of a $TST$ or $STS$ either increases the number of blocks by one if the removal was smack in the middle of a block, or it decreases the number of blocks by one if the removal was on the edge of a block. For the former, an example is \[(STSTST)(TSTSTST)(TSTSTS)\mapsto(STSTST)(TS)(ST)(TSTSTS),\]and for the latter, we have \[(STSTST)(TSTSTST)(TSTSTS)\mapsto(STSTST\quad STST)(TSTSTS).\]Note that there are $2n$ turns, so if there were more than $2n$ blocks to start with, there will be more than $0$ blocks after $2n$ turns, which is a contradiction as there should be $0$ blocks at the end (of course if there were more than $2n$, then the necklace would stop at some point with all block sizes $1$ or $2$, which allows for no removals). Now we'll show that if there are currently $m$ blocks and $3m$ beads with no size one block, then no matter whose turn it is, they can remove something to make the necklace $m-1$ blocks and $3(m-1)$ beads. WLOG, suppose it's Tasty's turn, and suppose for sake of contradiction the desired function isn't possible. Note that removing a $TST$ from an endpoint of a block does the desired function. Thus, if there is any block of even length with length at least $4$, then the function is possible, so all even length blocks have size $2$. Furthermore, Tasty can do a proper removal if there's any odd lengthed block starting with $T$. Thus, all odd blocks start with $S$. But this means that there are more $S$s than $T$s which implies that it is in fact Stacy's turn, which is a contradiction. Thus, there are no odd blocks, so all blocks have size $2$. But this means that there are only $2m$ beads, which is a contradiction. Thus, Tasty can make the desired move. In this manner, Tasty and Stacy can remove all the beads if there are at most $2n$ blocks, so the problem is finished. $\blacksquare$

Oops awang11 spoiled the main idea to me. Abbreviate each turquoise bead by $T$ and each sapphire bead by $S$ so there is a sequence of $S$s and $T$s. Split the graph into maximal alternating sequences of $S$s and $T$s: for example, $TSTTSTSSTSTS$ would be broken up as $TSTS\ STSTSTST$, where the sequences cannot be made any bigger. Then any move of Tasty or Stacy either deletes a chunk from the end or beginning of one of the sequences (possibly eliminating it) and thus combines it with the adjacent sequences if the sequence does not have length exactly three, or splits a sequence into two parts. Thus there can certainly not be any more than $2n$ initial maximal sequences. We now argue that if there are at most $2n$ initial maximal sequences, we win starting with Tasty (which suffices by symmetry). Observe that no sequence of steps can ever yield a maximal sequence of length $1$: there cannot be one to start with, and any procedure that would form one would merge the remaining bead with another because our strategy will always have Tasty or Stacy take an exterior chunk. At each step, Tasty can proceed and reduce the number of sequences iff some endpoint of a maximal sequence with length at least $3$ is $T$. If this is not the case, then every sequence either has length $2$ or has odd length and begins and ends with an $S$: this clearly cannot occur because the number of $S$s and $T$s are equal. Then Stacy is given some number of sequences, in which there is $1$ more of the $S$s than of the $T$s. Again, Stacy would only be unable to proceed if every sequence had either length $2$ or odd length and began and ended with a $T$. This cannot occur because she must start with more $S$s than $T$s.

Solution in stream: Let $s_i$ be the number of Sapphire beads in the $i$th group, and $t_i$ be the number of Torquoise beads in the $i$th group (for example, SSTSTT has $s_1=2, t_1=1, s_2=1, t_2=2$) For a position, define its danger to be the number of $s_i\ge 2$'s plus the number of $t_i\ge 2$'s. I claim the danger of a position can decrement by at most 1 each move. Proof. Easy casework. In the end, the danger is obviously 0, and since there are $2n$ moves, the initial danger must be at most $2n$. I also claim that all positions with danger at most $2n$ is winnable for both players. Proof. Suppose one player (WLOG he's Tasty) cannot decrease the danger. From the casework, we can see that this implies $t_i, t_{i+1} \le s_i$ for each $i$. Notice $0\le \sum (t_i-s_i) = \sum (t_{i+1}-s_i)$, so it follows that $s_i=t_i=s_{i+1}$, so $s,t$ are constant, which means that they're either always equal to 2 (which is obviously losing for either player) or always equal to 1 (obviously winning for either player). Therefore, Tasty and Stacy can win a position iff its danger is at most $2n$. We are done. Motivational remarks: When I do such a combinatorics problem, I always think about simple cases and try to learn from them. Note the 3-consecutive condition is actually necessary, the case TTTSSTSTSTSS is winnable if Stacy goes first ($TTTS[STS]TSTSS \rightarrow TT[TST]STSS \rightarrow TT[STS]S \rightarrow TTS$) but if Tasty goes first, we can see that it's either $TTTSS[TST]STSS \rightarrow TTTSS[STS]S (forced) \rightarrow TTTSSS$ or $TTTSSTS[TST]SS \rightarrow TTTS[STS]SS (forced) \rightarrow TTTSSS$, both fails. Therefore, all induction attempts fail. Since it's asking us to show the "symmetry" of the position, we need a categorization of positions that doesn't depend on the special properties of the players' moves. By some experimentation (and extremal cases), we can see the fewer SS's or TT's we have, the more likely we can win.

We can win in both cases iff the number of initial components is at least $4n$, proving the claim. This is true because: We can always find a single bead to remove on each turn which reduces the total number of connected components by at most $2$. The necessity there is since there are at least two removed on each operation. If this does not exist, with the assumption that all blocks are length $1$ or $2$, we have some series of $BBRRBBRRBB$ blocks between some $RBRBRBRBR$ blocks. Notice if we are forced to remove $RBR$ such that both $R$ are single blocks, then this means there are more $B$s than $R$. But either the number of $B$ and $R$ are balanced or previously we removed $BRB$ where the number of $R$s is greater than the number of $B$s, so this never occurs. It is easy to check that as long as this case is more or less avoided, we win as desired since the operation, if it obeys our condition, never creates blocks of length $3$.

At any point, the necklace can be divided into blocks of consecutive beads, where two adjacent beads are considered to be a block boundary iff they have the same color. In other words, the blocks are maximal blocks of alternating beads. If there are either 0 or 1 pairs of adjacent beads of the same color, we consider the entire necklace to be one block. In any single operation, by either player, the three beads removed must come from the same block, $B$. Consider three types of moves: Type 1: If the removal occurred at $B$'s edge (first 3/last 3 beads of $B$ removed), then the remaining elements of $B$ will be combined with an adjacent block, on the side where the removal took place, to form a larger block. Type 2: If the removal occurred internally within $B$, then $B$ is split into two blocks at the point of the removal. Type 3: If $B$ contains exactly 3 beads and the operation removed the entirety of $B$, then the remaining blocks remain as is. Lemma: The average block size is at least 3. Proof: Suppose otherwise. Then consider the winning strategy with Tasty going first. We claim that the average block size remains less than 3 after every move. Assume that there are at least two blocks remaining. Then a type 1 or type 3 move would decrease the necklace's size (total size of all blocks) by 3 and the number of blocks by 1, and a type 2 move would decrease the necklace's size by 3 and increase the number of blocks by 1. In either case, if the average block size is less than 3 before, it will be less than 3 after. In the end, there will be a single block remaining with size less than 3, which is absurd. $\square$ Now we provide the following algorithm to win with Stacy going first. The algorithm will maintain the following two invariants: (1) There will never be a block of size 1; in other words, there will never be three consecutive beads of the same color. (2) The average block size will always be at least 3. Initially, these invariants are satisfied, by the problem's given condition and by the Lemma. Abbreviate sapphire by S and turquoise by T. On each move, assuming that there are at least two blocks left, we do the following: 1. If there exists a block of even size at least 4, then one end of the block will be STS and the other end will be TST. Perform a type 1 move on the block on the end appropriate for the player having the current turn. 2. Otherwise, by invariant (2), there exists at least one block of size at least 3 (all such blocks must have odd size); the rest of the blocks, by invariant (1), must have size 2. Call an odd-sized block starting and ending with S a S-block, and define T-blocks similarly. If it is Stacy's turn, there are an equal number of S's and T's in the necklace, so there must exist equally many S-blocks and T-blocks, and in particular an nonzero number of each since we know we have odd-sized blocks. Stacy can now perform a type 1 or 3 move on an S-block (on either end, if type 1). Similarly, if it is Tasty's turn, there is one more T-block than S-blocks, so there exists a T-block. Tasty performs a type 1 or 3 move on a T-block. In the end, there will be a single block left with alternating beads, which is easy to handle. Now we just have to prove that each step of the algorithm preserves invariants (1) and (2). Note that the algorithm only ever performs type 1 and 3 moves. The former combines two blocks into one after shrinking one of them; the latter deletes a single block. Neither can generate new blocks of size 1. Also, each move of these types reduces the total number of beads over all blocks by 3 and the number of blocks by 1, so invariant (2) is also preserved, and we are done.

Split the necklace into components by drawing a divider between any two same-color beads; each component has alternating colors. Note that no component has size one. We have the following characterization of winning positions. Claim: The game is winnable (for both choices of starting player) iff there are at most $2n$ dividers (equivalently, at most $2n$ components). Proof: First off, check that each move either removes or adds a divider, so this condition is necessary. We now prove that it is sufficient by induction on $n$, with the base case of $n=0$ being vacuous. If a bead removal takes place along a divider (i.e. at least one of the beads removed is adjacent to a divider) then it is clear that the number of dividers decreases by $1$, and that no component of size $1$ is generated. Therefore it suffices to show that we can perform such a removal twice regardless of which player removes first, whence we will be done by inductive hypothesis. Classify the connected components into three types: Type 0, which contain an even number of elements, Type 1, which contain an odd number of elements and one more sapphire bead than turquoise bead, Type 2, which contain an odd number of elements and one more turquoise bead than sapphire bead. By counting the total number of beads, it is clear that there are an equal number of type 1 and type 2 components. Since all such components have size at least $3$, if a type 1 and a type 2 component exist then we can perform a divider-adjacent removal along each one regardless of move order, since these moves are "independent". Thus suppose that no type 1 or 2 components exist, so every component is even. If some even component has size at least $6$, then Tasty can remove from one end and Stacy can remove from the other end regardless of move order, since these moves are also "independent". If two even components have size at least $4$, then we can assign one to each person and have them perform "independent" divider-adjacent removals as well. Therefore suppose that no even component has size at least $6$, and that at most one even component has size $4$. Because we have $6n$ total beads and at most $2n$ components, it follows that we must have $n=1$, and there is one even component with size $4$. Then up to rotation, the bracelet reads $TSTSST$. It is clear by inspection that the game is winnable here regardless of starting player, so we are done. $\blacksquare$

Define a necklace to be winnable if Tasty and Stacy may win, with Tasty moving first. Replace sapphire beads with $0$'s and turquoise beads with $1$'s. We first attempt to characterize all winnable necklaces. Define a crossing in the necklace to be a place where the bead types switch. Namely they appear as $01$ or $10$. Claim: After either Stacy or Tasty moves, the number of crossings decrease by at least $2$.   Proof. Without loss of generality assume that Tasty moves. Note that we have a couple cases. Namely, $01010$ $11011$ $01011$ Clearly the first case reduces the number of crossings by $4$. The second case decreases the number of crossings by $2$. Finally the last case decreases the number of crossings by $2$. $\square$ Specifically, the number of crossings decreases every turn. Now say that there are $2k$ distinct crossings in a necklace as the number of crossings is always even. Note that there must be at least $2$ crossings on the necklace for a move to occur. Thus as Tasty and Stacy take $2n$ turns, there must be at least $4n$ crossings. Claim: All necklaces with at least $4n$ crossings are winnable. Proof. The goal is to show that Tasty and Stacy may ``reduce" the necklace to the case of $6n - 6$ beads, with at least $4n - 4$ crossings. We first show on Tasty's first turn, given that the number of crossings is less than $6n$, he may find a crossing of one of the following forms: $11010$ $11011$ More specifically he may find a substring such that on his turn, the number of crossings decreases by at most $2$. Indeed assume for the sake of contradiction none of these sub-strings appear. Then note that combined with condition that no three consecutive beads are of the same color, we know the following: The length of a substring between two consecutive crossings has length at most $2$. Between any two crossings we have sub-strings of the form $01010$, $110011$ and $010011$. There are at least $4n$ crossings. Now begin by noting that the second type of sub-string may never be adjacent to any other type of string, and thus cannot appear in our necklace. Then the first and third sub-strings may combine in one of two ways. $01010 \text{ } 010011$ $01010 \text{ } 10011$ The first sub-string may combine to itself in two ways. $01010 \text{ } 01010$ $01010 \text{ } 1010$ Finally the third string may not combine with itself. Thus each of the third strings are sandwiched between two of the first strings. However it may easily be observed that this is a contradiction. Namely we get a string of the form: \begin{align*} 01010 \text{ } 0100\boxed{11 \text{ } 010}101 \end{align*}with the boxed substring going against our original assumption. Then the necklace is composed solely of the first type of string. Namely each color $1$ bead is sandwiched in between two color $0$ beads. However as there are exactly $4n$ beads our necklace must be of the form, \begin{align*} \dots 1010101010 \dots \end{align*}which can easily be observed to be winnable. All this shows is that Tasty is guaranteed to find a substring of the form $11010$ or $11011$, which decreases the number of crossings by exactly $2$. Now for Stacy's following turn we may undergo a similar analysis, except for the very last part. Once we determine the necklace is composed solely of $10101$ strings we may note that on the necklace there are exactly $3n - 2$ beads of color $1$, and $3n - 1$ beads of color $0$. Thus our necklace must be of the form, \begin{align*} \dots 01\boxed{010}01010 \dots \end{align*}However removing the boxed substring sends this necklace to one of the form, \begin{align*} \dots 0101010 \dots \end{align*}which can easily be observed to be winnable. Thus this is a non-issue. From this we may conclude that given that Tasty and Stacy are not playing on a ``trivial" board of alternating beads of color $0$ and color $1$ which has $6n$ crossings, together they can play such that they reduce the board to one with $6n - 6$ beads, with at least $4n - 4$ crossings. Then from induction downward we are done. $\square$ Claim: If there exists a strategy for the players to win with Tasty going first, there exists a strategy for the players to win with Stacy going first. Proof. Call the first necklace $n_1$. Simply consider flipping $0 \mapsto 1$ and $1 \mapsto 0$. Clearly this sends one winnable string to another winnable string. Call this second necklace $n_2$. Let Stacy  ``phantom" Tasty's moves from $n_2$ onto $n_1$ by playing with the corresponding beads, and similarly let Tasty  ``phantom" Stacy's moves from $n_2$ onto $n_1$. This clearly works as $n_2$ is winnable and thus $n_1$ is winnable with Stacy going first. $\square$ Remarks: Hopefully this solution is correct. If it is, then I feel that the problem was pretty motivated and not extremely difficult if you think about how you wish to approach it. Mainly, instead of thinking about Tasty or Stacy starting first, the biggest jump is to flip the colors of all beads. Then the conclusion implies that if Tasty begins, this string is winnable. This in turn motivates characterizing all winnable strings, which is not extremely difficult. The main difficulty is ensuring the writeup is rigorous.

We will characterize circles of beads by four quantities: $t_1$, the number of turquoise beads that are surrounded by two sapphire beads; $t_2$, the number of adjacent pairs of turquoise beads; $s_1$, the number of sapphire beads that are surrounded by two turquoise beads, and $s_2$, the number of adjacent pairs of sapphire beads. I claim that the game can be won with Tasty going first if and only if $t_1 \geq n$ and $s_1 \geq n$. By symmetry, this will imply the result. Bound: Consider the circle of beads (initially) as a circular sequence of $1$'s and $2$'s corresponding to the length of the run of consecutive beads; we denote $n_T$ and $n_S$ to be runs of $n$ turquoise and $n$ sapphire beads, respectively. [Notice that we can have $n \neq 1, 2$ past the first move.] Then, on Tasty's move, he must convert $$a_T + 1_S + b_T \to (a+b-2)_T.$$In particular, on every one of Tasty's $n$ moves, at least one $1_S$ is removed; thus, as there are $s_1$ such $1_S$'s in the beginning, we must have $s_1 \geq n$. Similarly, Stacy also performs $n$ moves, so we also have $t_1 \geq n$. Construction: We consider a turn to encompass both players' moves. It suffices to show that at every point, there still exists one valid possible turn (hence both players making valid moves). Call a sapphire entry point a $1_S$ adjacent to a $2_T$ and define a turquoise entry point similarly. We will only perform turns with $\{a, b\} = \{1, 2\}$; hence, no runs of three turquoise or three sapphire beads will ever be generated [as $a+b-2$ is always nonzero]. First, we consider cases where there is at least one $2_S$ or $2_T$ (and thus one entry point) remaining. Claim. At the beginning of every such turn, there is at least one sapphire entry point and at least one turquoise entry point. Proof. Suppose otherwise, and assume that all entry points are turquoise. Then it follows that every run of $1$'s starts and ends with $1_T$; say there are $k$ such runs. Then $t_1 = s_1 + k$, but it follows that there exist $k$ runs of $2$'s that start and end with $2_S$, and thus $s_2 = t_2 + k$. Then we cannot have $s_1+2s_2 = t_1+2t_2$, which is an obvious contradiction. $\blacksquare$ Thus, on Tasty's turn, he removes the $1_S$ and $2_T$ at the sapphire entry point, which does not affect any existing turquoise entry points. Stacy can then remove the $1_T$ and $2_S$ at the turquoise entry point. The result is a necklace with $6$ less beads with no triplets. The second case occurs when all the beads are alternating. In this case, Tasty chooses any $1_T$, $1_S$, $1_T$ sequence and deletes it to form a $2_S$ along with the rest of the $1$'s. This creates a turquoise entry point for Stacy, so the process proceeds similarly. This completes the proof.

Consider run-lengths. All of them must be ones or twos. We claim that they can win iff the number of ones is less than or equal to the number of twos. First if there are more twos than ones, it is impossible since each turn removes at least one one and at most one two. If there are only ones, it is easy because we can remove them consecutively six at a time. Now suppose there is a two. Then there is also a two of the other color, since the sum of each color is the same. Now we claim that for a certain color, we can find a one of that color next to a two of the opposite corner. This is because if we consider all numbers with that color, then either there is a one which is directly clockwise of a two of the other color, or all twos are directly clockwise of twos. Then among that one color, there is both a one and a two, so there is a two directly clockwise of a one. The number between them must be a two, so the one is directly counterclockwise of a two, so we have found a one-two pair of this color. Now we can remove it, since this is equivalent to operating on the string centered on the one. Now we have the same setup, but the other color sums to one less than the original color. Thus for at least one one of the other color, the original color number directly clockwise of it must be a two. Then we can remove this one-two pair as well. In particular this reduces the setup, preserving the number of twos being less than or equal to the number of ones. Thus we may repeat this until either there are only ones, or all numbers are removed. This finishes.