USA November TST Selection Test for IMO 2021 Problem 1 wrote: Let $a$, $b$, $c$ be fixed positive integers. There are $a+b+c$ ducks sitting in a circle, one behind the other. Each duck picks either rock, paper, or scissors, with $a$ ducks picking rock, $b$ ducks picking paper, and $c$ 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$, $b$, and $c$, the maximum number of moves which could take place, over all possible initial configurations.

The number of triples of the following form decreases by one of $a$, $b$, $c$ each move. [asy][asy]size(9cm); picture duck; pen duckborder = black+1.2; picture leg; draw(leg, (0.5*dir(-70))--(1.6*dir(-70)), duckborder); draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-95)), duckborder); draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-50)), duckborder); add(duck, leg); add(duck, reflect(dir(-90), dir(90))*leg); filldraw(duck, (1,0)--(-1,0)..(0,-1)..cycle, rgb("a67b5b"), duckborder); // body of duck draw(duck, (0.1,-0.4)..(-0.2,-0.35)..(-0.6,-0.2), duckborder); // part of wing draw(duck, (0.1,-0.8)..(-0.2,-0.7)..(-0.6,-0.2), duckborder); // part of wing filldraw(duck, (1.2,0.3)--(1.2,0)--(1.7,0.15)--cycle, yellow, duckborder); // beak of duck filldraw(duck, circle((0.7,0.3), 0.6), rgb("b9d3a4"), duckborder); // duck head fill(duck, ellipse((1.05,0.45), 0.08, 0.12), black); fill(duck, ellipse((1.07,0.49), 0.02, 0.03), white); draw(duck, (1.6,0.5)--(1.8,0.7)..(2.0,0.75)..(2.4,1.2)..(1.8,1.5)..(1.2,1.2)..(1.6,0.7)--cycle ); label(duck, "\textsf{quack}", (1.8,1.1), fontsize(9pt)); draw(scale(4)*unitcircle, blue+2); pen labelpen = red + fontsize(16pt); add(shift(5*dir(90))*duck); label("Rock", 3*dir(90), labelpen); add(rotate(120)*shift(5*dir(90))*duck); label("Paper", 3*dir(210), labelpen); add(rotate(240)*shift(5*dir(90))*duck); label("Scissors", 3*dir(330), labelpen); [/asy][/asy] Since the number of such triples is initially at most $abc$, this implies at most $\max(ab,bc,ca)$ moves are possible. Moreover, if $a = \min(a,b,c)$ without loss of generality, then the following configuration achieves the full $bc = \max(ab,bc,ca)$, by having only scissors-ducks move. [asy][asy]size(11cm); picture duck; pen duckborder = black+1.2; picture leg; draw(leg, (0.5*dir(-70))--(1.6*dir(-70)), duckborder); draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-95)), duckborder); draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-50)), duckborder); add(duck, leg); add(duck, reflect(dir(-90), dir(90))*leg); filldraw(duck, (1,0)--(-1,0)..(0,-1)..cycle, rgb("a67b5b"), duckborder); // body of duck draw(duck, (0.1,-0.4)..(-0.2,-0.35)..(-0.6,-0.2), duckborder); // part of wing draw(duck, (0.1,-0.8)..(-0.2,-0.7)..(-0.6,-0.2), duckborder); // part of wing filldraw(duck, (1.2,0.3)--(1.2,0)--(1.7,0.15)--cycle, yellow, duckborder); // beak of duc filldraw(duck, circle((0.7,0.3), 0.6), rgb("b9d3a4"), duckborder); // duck head fill(duck, ellipse((1.05,0.45), 0.08, 0.12), black); fill(duck, ellipse((1.07,0.49), 0.02, 0.03), white); draw(duck, (1.6,0.5)--(1.8,0.7)..(2.0,0.75)..(2.4,1.2)..(1.8,1.5)..(1.2,1.2)..(1.6,0.7)--cycle ); label(duck, "\textsf{quack}", (1.8,1.1), fontsize(9pt)); draw(scale(4)*unitcircle, blue+2); pen labelpen = red + fontsize(16pt); add(rotate(-10)*shift(5*dir(90))*duck); add(rotate(10)*shift(5*dir(90))*duck); label("Rocks", 3*dir(90), labelpen); add(rotate(100)*shift(5*dir(90))*duck); add(rotate(120)*shift(5*dir(90))*duck); add(rotate(140)*shift(5*dir(90))*duck); label("Papers", 3*dir(210), labelpen); add(rotate(200)*shift(5*dir(90))*duck); add(rotate(220)*shift(5*dir(90))*duck); add(rotate(240)*shift(5*dir(90))*duck); add(rotate(260)*shift(5*dir(90))*duck); label("Scissors", 3*dir(330), labelpen); [/asy][/asy]

oops The answer is $\text{max}(ab,bc,ac)$; if, say, $ab$ is the maximum, then this is achievable by putting all the $b$ ducks directly behind all the $a$ ducks. Now we show this is the maximum; say a duck $X$ attacks a duck $Y$ if duck $X$ was originally behind duck $Y$ and they swap. Observe that if $X$ attacks $Y$, then from then on $X$ can no longer be attacked and $Y$ cannot attack anyone. Let there be $x$ ducks who attacked with rock, $y$ ducks who attacked with paper, and $z$ ducks who attacked with scissors; then because of the previous observation we have that the total number of attacks is at most $$\underbrace{x(c-z)}_{\text{rock attacks}}+\underbrace{y(a-x)}_{\text{paper attacks}}+\underbrace{z(b-y)}_{\text{scissor attacks}}$$I claim that in general, for reals $(x,y,z) \in [0,a] \times [0,b] \times [0,c]$, this quantity is at most $\text{max}(ab,bc,ac)$. For the edge cases $x \in \{0,a \}, y \in \{0, b\}, z \in \{0,c \}$ it's easy to see the quantity is always at most $\text{max}(ab,bc,ac)$. Otherwise, setting the gradient of $x(c-z)+y(a-x)+z(b-y)$ of equal to zero, we get \begin{align*} y+z&=c \\ x+z&=a \\ x+y&=b \\ x(c-z)+y(a-x)+z(b-y)&=xy+yz+xz \end{align*}and assuming $x \ge y \ge z$, we have $xy+yz+xz \le (x+y)(x+z)=ab$.

Hopefully, it's correct. We adopt few notations first. Let $R,P,S$ denote rock, paper, scissors respectively. Let $\mathbb{R},\mathbb{P},\mathbb{S}$ denote sets of $R,P,S$ on circle where $|\mathbb{R}|=a$ and others respectively. Let $\mathcal{T}=\{R,P,S\}$ be the set of things. At a time, call a thing bad if it is not possible to exchange or switch it with either of it's partners (behind or forward one). WLOG assume ducks sit in the counterclockwise manner ($\clubsuit$). We can restate the problem to say that rocks, papers, scissors are doing operations accordingly. Now, we proceed with the following series of claims. Claim. We have Each $R\in\mathbb{R}$ can in and itself perform atmost $\max\{b,c\}$ operations. Each $P\in\mathbb{P}$ can in and itself perform atmost $\max\{a,c\}$ operations. Each $S\in\mathbb{S}$ can in and itself perform atmost $\max\{a,b\}$ operations. Proof. We focus on first one. Clearly either we can do $R \leftrightarrow S$ or $P \leftrightarrow R$ operations. These are the only possible operations involving $R$. If we/$R$ does $R \leftrightarrow S$ then consider the following: $$\ldots R^* \underbrace{S\ldots P\ldots S}_{c~\text{places}} \ldots$$where $P$ is the first paper $R^*$ faces and $R^*$ moves forward due to $(\clubsuit),$ we get $$\ldots S \underbrace{\ldots R^*P \ldots S}_{c~\text{places}} \ldots$$and $R^*$ stops since it cannot exchange it's place with $P$. Here we/$R^*$ has done $<c$ moves. But if there is no $P$ in-between $S\ldots S$ which are just all $c$ Scissors with $R^*$ before them, then $R^*$ can do $c$ moves and stops since he will face either another rock and paper which it cannot exchange it's place with, which is just because $R \leftrightarrow R$ and $R \leftrightarrow P$ are no valid operation considering $(\clubsuit)$. So we conclude we can do maximum of $c$ moves here. Now going other way, i.e. doing $P \leftrightarrow R$ and following same logic we conclude we can do maximum of $b$ moves then and stops.Therefore, $R$ can perform atmost $\max\{b,c\}$ moves overall. Analogously, we get other two parts as desired. $\square$ We have following as our direct conclusion from above reasoning: Each thing will become bad after atmost $\max\{a,b,c\}$ operations involving this particular thing Claim. We have All elements of $\mathbb{R}$ can do atmost $\max\{ab,ac\}$ operations. All elements of $\mathbb{P}$ can do atmost $\max\{ba,bc\}$ operations. All elements of $\mathbb{S}$ can do atmost $\max\{ca,cb\}$ operations. Proof. We focus on the first one. Using previous claim, each $R$ can do atmost $\max\{b,c\}$ operations. Hence all elements $\mathbb{R}$ can do atmost $a\cdot\max\{b,c\}=\max\{ab,ac\}$. We can have following as our desired construction. Consider the following: $$\ldots \underbrace{R \ldots R^*S\ldots SP\ldots P}_{a+b+c~\text{times}}\quad\quad(\spadesuit)$$where $R,P,S$ appears $a,b,c$ times respectively, consecutively. Now we perform maximum moves $b$ by $R^*$ and move it at last as shown $$\ldots \underbrace{R\ldots R^{**}S\ldots SR^*P\ldots P}_{a+b+c~\text{times}}$$Next, we move $R^{**}$ and performing so on and so forth, we now have performed $ac$ moves. Likewise, we could also do same by $P \leftrightarrow R$ to perform $ab$ moves. Hence $\max\{ab,ac\}$ is our desired answer. Analogously, the same construction works for rest of two with performing by $P,S$ instead of $R$ which finishes the proof. $\square$ Combining all of the above reasoning, we get each thing will become bad in atmost $\max\{ab,bc,ca\}$ operations. So we can perform atmost $\max\{ab,bc,ca\}$ operations, as desired. We have $(\spadesuit)$ as our desired construction again. $\blacksquare$

Sketch The answer is $max(ab, bc, ca)$ Equality case: $PP... PRR... RSS... S$ and make moves only to $P$'s and $R$'s. Obviously the moves are $ab$ Bound: -Let $I$ be the number of triples $(R, S, P)$ in this order in clockwise direction. -In the beginning $I$ is at most $abc$ -On each move $I$ decreases by one of $a, b, c$ The conclusion follows.

The answer is $\operatorname {max} ({ab,bc,ca)}$. The motivation is the equality case of $R^aS^bP^c$ where we move clockwise while going from R to P. If $a = \operatorname {min} (a,b,c)$ , then we could just do Paper-Scissor moves to win. The proof of bound is (again motivated by equality case consideration), is that every step must reduce the number of triples of the form $R\mapsto S \mapsto P$, where we are moving clockwise from $R \mapsto S$, etc. This value is atmost $abc$, but it also decreases by atleast $\operatorname {min}({a,b,c)}$ every move. This shows that we can have atmost $\operatorname {max} (ab,bc,ca)$ moves. $\square$

Here is a proof inspired by the techniques illustrated in Discrete Mathematics with Ducks by Sarah-Marie Belcastro. Let's denote each move as a "quack". The main claim is the following: Claim: Once you go quack, you'll never go back. In other words, if a duck moves fowards in some move, it can never move backward after that. WLOG, let us focus on a single rock duck. We prove this via inducktion on the number of the move where such fowl quackery happens. The backward move clearly can't happen on the $1$st move, because it has moved forward once before. Suppose it happens on the $n+1$th move. Just before that move, it looked like this: $$\cdots \text{[paper]}\text{[rock]}\cdots$$Since the rock's last move was past a scissors-duck by the inducktion hypothesis, that duck is also somewhere in the picture $$\cdots\text{[scissors]}\cdots \text{[paper]}\text{[rock]}\cdots$$But no move could have moved that scissors duck from immediately behind the rock duck to this cyclic order (this is just casework), so this is all mallard-key. A similar argument proves the dual statement: if some duck moves backward at some point, it will never go forward. One can now check using the above deducktion that given any triple of ducks with three different symbols, only one quack could ever happen between them. There are $abc$ such triples, so $abc$ such swaps: but each swap is counted in at least $\min\{a,b,c\}$ triples (for example, a rock-scissor swap is counted in $b$ triples, one for each paper-duck). After a suitable reducktion to account for this overcounting, we see there can be only $\tfrac{abc}{\min\{a,b,c\}}=\max\{ab,bc,ca\}$ quacks. This can be indeed be acheived by putting all rocks, followed by all scissors and then all papers in ducksession, so we are done. QED (Quacks Enumerated for Ducks).

$100$-th post! We claim that the answer is $max\{ab,bc,ca\}$. Assume WLOG $a=min\{a,b,c\}$ and also that the ducks are placed clockwise. The equality case is when we have rocks, papers and scissors placed such that each type lies on a contiguous segment of ducks such as $$\underbrace{RR...R}_{a} \underbrace{SS...S}_{b} \underbrace{PP...P}_{c}$$Then, we just do Paper-Scissor moves. Now, we prove the upper bound. Observe that when we make a move, say Paper-Scissor, it's impossible to make a move Rock-Paper with the Paper moved originally, because we can't make the Rock-Scissor move and since there is a since there is a Scissor in front of the Paper, this is indeed impossible. Thus, once we make a duck moves backwards, this duck can never move backward after that and vice-versa. $(\star)$ Furthermore, if the total of moves in a moment is $T$, then $$T \leq \frac{\sum_{1 \leq i \leq a} X_{a,i} + \sum_{1 \leq i \leq b} X_{b,i} + \sum_{1 \leq i \leq c} X_{c,i}}{2}$$where $X_{a,i}$ is the maximum number of moves such that the $i$-th duck picking Rock could have made. $X_{b,i}$ and $X_{c,i}$ are defined similarly. From $(\star)$, $X_{a,i} \in \{0,b,c\}, X_{b,i} \in \{0,a,c\}, X_{c,i} \in \{0,a,b\}$, so since each amount is counted twice $$\frac{\sum_{1 \leq i \leq a} X_{a,i} + \sum_{1 \leq i \leq b} X_{b,i} + \sum_{1 \leq i \leq c} X_{c,i}}{2} \leq max\{ab,bc,ca\}$$$\implies T \leq max\{ab,bc,ca\}$, as desired. Hence, we can have at most $max\{ab,bc,ca\}$ moves. $\blacksquare$

USA TSTST 2020 P1 wrote: Let $a$, $b$, $c$ be fixed positive integers. There are $a+b+c$ ducks sitting in a circle, one behind the other. Each duck picks either rock, paper, or scissors, with $a$ ducks picking rock, $b$ ducks picking paper, and $c$ 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$, $b$, and $c$, the maximum number of moves which could take place, over all possible initial configurations. Same as most solutions here. The answer is $\max(ab,bc,ca)$. To attain this bound, just consider $r,r, \ldots r,s,s,\ldots s,p,p,\ldots p$. To prove that it is the maximum, consider the number of $(r,s,p)$ triples. Assume that ''behind'' goes clockwise. Initially this number is obviously at most $abc$ and, after each move it decreases by $a,b$ or $c$ (if, for example, we swap $(r,s)$ then all $c$ triples $(r,s,p)$ are lost). Hence, at each move this quantity decreases by at least $\min (a,b,c )$, therefore at most $\frac{abc}{\min (a,b,c )}=\max (ab,bc,ca)$ moves can be performed, as desired.

time to actually formally write this up Label the positions of the $n = a + b + c$ ducks from $1$ to $n$. After each move, consider the number $S$ of ordered triples $(i, j, k)$ of positions $i, j, k$ where $i \to j \to k$ goes clockwise, such that the duck on $i$ picked rock, the duck on $j$ picked paper, and the duck on $k$ picked scissors. There are at most $S = abc$ such triples initially. I claim that after each move, the quantity $S$ decreases by $a$, $b$, or $c$. Indeed, if we swap a pair of paper $\iff$ scissors ducks, $S$ decreases by $i$, and similarly, if we swap a pair of scissors $\iff$ rock ducks, $S$ decreases by $j$, and if we swap a pair of rock $\iff$ paper ducks, $S$ decreases by $k$. Thus, there are at most $\tfrac{abc}{\min(a, b, c)}$ moves as $S$ cannot dip below $0$, so our answer is $\max(ab, bc, ca)$. This is achievable by putting all scissors ducks behind paper ducks behind rock ducks, then only swapping rock and paper ducks. $\blacksquare$

Quote: Once you go quack, you'll never go back. this is actually such a wonderful name for a claim

Consider all oredered triplets of $(x,y,z)$ where $x,y,z$ picked $rock,scissors,paper$ respectively. $\color{red} \textbf{claim:}$ the number $T=abc$ decreases by $a$ or $b$ or $c$. $\color{green} \textbf{proof:}$ if we swap $x,y$ then the quantity $T$ decreases by $c$,and similarly if we change $y,z$ it decreases by $a$ and for $x,z$ it decreases by $b$. so the maximum steps is $\frac{abc}{c}=ab$ where $c\le a,b$.

The answer is $\max(ab, bc, ac)$ By placing all $a$ rock ducks behind all $c$ scissor ducks, all $c$ scissor ducks behind all $b$ paper ducks, and the circle seating forces all $b$ paper ducks to behind all $a$ rock ducks, making any of these 3 possible. For the remainder of the proof, without loss of generality, assume $a \ge b \ge c$. To begin, a few terms must be introduced. Define a group to be all of the ducks that have a certain item(being rock, papaer, or scissors). Let a group be connected if all of the ducks in the group are adjacently seated in the circle, and 2 groups are clustered if they are adjacent, connected groups. Claim. Group $a$ and group $b$ must be clustered, with group $b$ behind group $a$, for an optimal amount of moves. Suppose that there was a duck in group $b$ disconnected from the rest of its group and in the middle of group $b$. This duck will simply move less than it originally would have it it were adjacent to its group, as there are less ducks in group $a$ ahead of it. Thus, for each duck that isn't adjacent to the rest of its group is simply losing moves, so for optimal moves, group $a$ and group $b$ must be connected for optimal moves. The second condition is obvious as otherwise no moves can be made. Claim. Group $c$ is clustered with groups $a$ and $b$ Consider each seperately, with group $a$ behind group $c$, and group $c$ behind group $b$ as otherwise no moves are possible. If there is a duck from group $a$ in between group $c$, then there are 2 optimal cases. One is where all of group $a$ goes in front of group $a$ goes in from of group $c$, which is $< ac < ab$, and the other is where the $c$ ducks in front of this $a$ duck go in front of group $b$, which is $< bc < ab$. Thus for optimal moves, group $c$ and group $a$ must be clustered. Similarly, if there is a duck from group $c$ in between group $b$, then by checking both cases similarly yields the desired result. Thus the optimal position is the originally stated orientation of groups $a, b, c$, which finishes the problem.

I approached the problem in a slightly different way. The answer is $\max(ab, bc, ca)$. This can be achieved by placing all ducks of the same kind together in the circle, with the rock group sitting behind the scissors group, the paper group sitting behind the rock group, and the scissors group sitting behind the paper group. Observe that if a rock-duck and a paper-duck switch, neither of them will ever be able to switch with a scissors-duck later on in the game. The same goes for paper-scissors and scissors-rock duck pairs. This implies that in an optimal configuration, the $a$ rock ducks can be divided into two groups of size $a = a_b + a_c$ where the $a_b$ ducks switch with paper ducks and the $a_c$ ducks switch with scissors ducks. We can similarly divide $b = b_c + b_a$ and $c = c_a + c_b$. WLOG, let $a \ge b \ge c$. Then, it suffices to prove the following: $$ab \ge a_b\cdot b_a + b_c \cdot c_b + c_a \cdot a_c$$We prove this by expanding: \begin{align*} a_b\cdot b_a + a_b\cdot b_c + a_c \cdot b_a + a_c \cdot b_c &\ge a_b\cdot b_a + b_c \cdot c_b + c_a \cdot a_c\\ b_c(a-c_b)+a_c(b_a-c_a) &\ge 0\\ \Longleftarrow b_c(c-c_b)+a_c(0-c_a) &\ge 0\\ b_c(c_a) - a_c(c_a) &\ge 0\\ \end{align*}Which is true by simply noting WLOG $b_c \ge a_c$ ($b_c$ and $a_c$ are interchangeable in our expansion) $\square$

We claim the optimal solution is $\max(ab,bc,ac)$. Take the setup $R\cdots RS\cdots SP\cdots P$. Then, for any $x,y$, we can swap each of the $x$ forward individually with $y$ moves, for a total of $xy$ where $x,y$ are the number of ducks for each move-type. To prove this is optimal, consider the number of clockwise pairs of $R-S-P$. Initially, there are at most $abc$ of these. However, in each swap of $x,y$, then it decreases this total by $z$ (number of the third type). Thus, it decreases by at least $\min(a,b,c)$. Therefore, there are at most \[\frac{abc}{\min(a,b,c)}=\max(ab,bc,ac)\]and we're done $\blacksquare$.

The answer is $\max\{ab, bc, ca \}$ moves. First, we provide a construction. WLOG, let $a \ge b \ge c$. Then, if we let all $b$ paper-ducks sit consecutively behind all $a$ rock-ducks, it's clear that all $ab$ pairs of paper-ducks and rock-ducks will switch places exactly once. Now, we will prove $\max\{ab, bc, ca \}$ is the maximum possible amount of moves. It's easy to see each pair of ducks can swap at most once. Now, given a move, say a duck moved forwards if it started behind the other duck it swapped with, and define a backwards move inversely. Claim: A duck cannot move both forwards and backwards. (We will call ducks which only move forwards jumpers, and ducks which only move backwards sitters.) Proof. WLOG, consider an arbitrary rock-duck, and suppose it just moved forwards. Then, we know a scissors-duck is directly behind it. Now, we proceed with contradiction. Notice our rock-duck can only move backwards if a paper-duck is directly behind it. But this would imply that a paper-duck moved in front of a scissors-duck, which is impossible. Hence, a duck which has moved forward cannot move backwards. The case where our rock-duck has just moved backwards follows similarly. $\square$ Now, we can separate our ducks into $6$ groups: rock-jumpers, rock-sitters, paper-jumpers, paper-sitters, scissors-jumpers, and scissors-sitters. Suppose the number of rock-jumpers, paper-sitters, and scissors-jumpers in our group is $x, y, z$ respectively. Then, it's easy to see the maximum possible number of moves is $$(a-x)(b-y) + yz + (c-z)x.$$Now, we perform casework. If $x \ge y$, then it's clearly optimal to make our sum $$(a-x)(b-y) + cx.$$If $b-y \ge c$, then the expression $a(b-y) \le ab$ is the maximum for this sub-case. If $b-y \le c$, then $ac$ is the maximum for this sub-case. If $x \le y$, then it's obviously optimal to make our sum $$(a-x)(b-y) + yc.$$If $a-x \ge c$, then $(a-x)b \le ab$ is the maximum for this sub-case. If $a-x \le c$, then $bc$ is clearly the maximum for this sub-case. Since $a \ge b \ge c$, we know $$\max\{ab, ac, ab, bc \} = ab$$which finishes. $\blacksquare$ Remark: While solving this question, I actually thought about the smart solution which considers "good" triples, but my logic was so bad, so I had to come up with another (uglier) method .

MortemEtInteritum wrote: Let $a$, $b$, $c$ be fixed positive integers. There are $a+b+c$ ducks sitting in a circle, one behind the other. Each duck picks either rock, paper, or scissors, with $a$ ducks picking rock, $b$ ducks picking paper, and $c$ 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$, $b$, and $c$, the maximum number of moves which could take place, over all possible initial configurations. We claim that the answer $\boxed{\max(\text{ab,bc,ca})}$ which is achieved by $$\underbrace{\text{Rock Rock...Rock}}_{a} \underbrace{\text{Scisor Scisor ...Scisor }}_{b} \underbrace{\text{Paper Paper...Paper}}_{c}$$To prove this is optimal, consider the number of clockwise pairs of $\text{Rock}-\text{Scisor}-\text{Paper}$. Initially, there are at most $abc$ of these. However, in each swap of $x,y$($x$ is the number of first type,$y$ is number of the second type),then it decreases this total by $z$ (number of the third type). Thus, it decreases by at least $\min(a,b,c)$. Therefore, there are at most \[\frac{abc}{\min(a,b,c)}=\max(ab,bc,ac)\]and we're done $\blacksquare$.

I'm very sorry. Abbreviate a duck picking rock to $A$, a duck picking paper to $B$, and a duck picking scissors to $C$, so we start with a circle of $a$ instances of $A$, $b$ instances of $B$, and $c$ instances of $C$. Then moves are $AC\to CA$, $BA\to AB$, and $CB\to BC$. Now, analyze a particular duck, WLOG it is called $A$, and consider how it may move over time. Any move with $A$ is either $AC\to CA$ or $BA\to AB$. Consider a particular duck $A$. If $AC\to CA$ occurs, then the only way $A$ could be moved again is if there is a $C$ following it or if, at some point, a $B$ appears between $C$ and $A$. But this latter possibility may not occur, as neither $AB\to BA$ nor $BC\to CB$ can occur. So then the only collections of moves around a particular swapping that may occur are a resorting of a contiguous block of $A$s and $C$s, a resorting of a contiguous block of $B$s and $C$s, and a resorting of a contiguous block of $A$s and $B$s. Note that in the discussion before, any given $A$ and $B$ cannot be swapped with each other twice. Hence the number of moves is certainly upper bounded by $ab+bc+ca$. Then the final configuration may be written as \[\underbrace{AA\cdots A}_{a_1}\underbrace{BB\cdots B}_{b_1}\underbrace{CC\cdots C}_{c_1}\underbrace{AA\cdots A}_{a_2}\underbrace{BB\cdots B}_{b_2}\underbrace{CC\cdots C}_{c_2}\cdots \underbrace{AA\cdots A}_{a_k}\underbrace{BB\cdots B}_{b_k}\underbrace{CC\cdots C}_{c_k}\]with the first $A$ and last $C$ bordering for some $k$ and $a_i,b_i,c_i$ satisfying $\min(a_i,b_i,c_i)\ge 1$ for each $i$ and $\sum_i a_i = a$, $\sum_i b_i = b$, and $\sum_i c_i = c$. Define the indices cyclically, so $c_0 = c_k$ etc. Remark that in the initial configuration, within say $\underbrace{BB\cdots B}_{b_1}$, an $A$ from the previous block cannot be any further to the right than any given $C$ from the following block is: otherwise the $A$ and $C$ would have swapped places illegally. Then there is a particular number $b_1'$ corresponding to the number of $B$s that could have been swapped with $A$s between the first and second blocks and $b_1-b_1'$ is the number of $B$s that could have been swapped with $C$s from the third block. Define each $a_i',b_i',c_i'$ analogously. Then there are at most \[\sum_i [(a_i-a_i')b_i' + (b_i-b_i')c_i' + (c_i-c_i')a_{i+1}']\]swaps. Now, observe that we may assume the values of $a_i,a_i',b_i,b_i',c_i,c_i'$ maximize this expression because equality can always be achieved. Write $(a_i-a_i')b_i' + (b_i-b_i')c_i' = b_i'[a_i-a_i' - c_i'] + b_ic_i'$. Thus we can take $b_i' = 0$ or $b_i'=b_i$ to maximize the value of this expression, and as we are taking the maximum to begin with, we see that each $b_i'$ is either $0$ or $b_i$ and analogous results hold for the $a_i'$ and $c_i'$. Now, we can assume all $a_i$s save one are $1$: if a particular $a_j$ and $a_k$ are multiplied by $d_1$ and $d_2$ in the sum, if $d_2\ge d_1$ then making $a_k$ equal to $a_k+a_j-1$ instead and changing $a_j$ to $1$ does not decrease the sum, so because we are at a maximum, this cannot occur. The same argument means that at most one $b_i$ is not $1$ and at most one $c_i$ is not $1$. WLOG $b = \max(a,b,c)$ and $b_1\ge b_i$ for all $i$. WLOG $b_1' = b_1$. Remark that we may assume $a_1'$ is equal to $0$, as otherwise changing it to $0$ would change the sum by $a_1[b_1-t]$ for some $t \le b_1$. Suppose that there exists some $i$ with $a_i > a_1$. Swapping $a_1$ and $a_i$ increases the sum by $(a_i-a_1)[b_1 - t]$ where we clearly have $t \le b_1$. So we can assume $a_1$ is maximal. Now, we have $a_1 = a-k+1$ and $b_1=b-k+1$. The other terms in the full summation must all be $1$ or $0$, with the potential exception of one term evaluating to $c-k+1$. Hence the number of swaps that occur is upper bounded by \[(a-(k-1))(b-(k-1)) + c-(k-1) + \bigg\lfloor \frac{3k-4}{2}\bigg\rfloor.\]Let $k-1=\ell$. The considered value is \[(a-\ell)(b-\ell)+c-\ell + \bigg\lfloor \frac{3\ell-1}{2}\bigg\rfloor = (a-\ell)(b-\ell)+c + \bigg\lfloor \frac{\ell-1}{2}\bigg\rfloor.\]Remark that if $c>a$, then $(c-\ell)(b-\ell) + a - (a-\ell)(b-\ell) - c = (c-a)(b-\ell - 1)$. Remark that $b \ge k$, so $b\ge \ell+1$ and we see that we ought to work with upper bound $(c-\ell)(b-\ell)+a+\lfloor \frac{\ell-1}{2}\rfloor$ instead. So we assume that $b\ge a\ge c$ and demonstrate that \[ab\ge (a-\ell)(b-\ell)+c + \bigg\lfloor \frac{\ell-1}{2}\bigg\rfloor.\]Remark that it is clear $ab$ can be achieved as a number of moves by taking $\ell = 0$ and starting with the configuration $\underbrace{BB\cdots B}_b \underbrace{AA\cdots A}_a \underbrace{CC\cdots C}_c$. So what we are proving is that the maximum number of moves is $\max(ab,bc,ca)$. We need to show \[\ell(a+b) \ge \ell^2 + c + \bigg\lfloor \frac{\ell-1}{2}\bigg\rfloor.\]If $\ell = 0$, this is false, but it does not matter because no members of the $C$ block can be swapped. If $\ell = 1$, the result is still clear: $a+b\ge 1+c$. Otherwise, remark that $\ell(a+b-\ell) \ge \ell(b+1)$, so it suffices to show \[0\le b\ell + \ell - b - \frac{\ell-1}{2} = b\ell + \frac{\ell+1}{2} - b.\]As $b(\ell-1) > 0$, the result follows.

Equivalent to maximizing the number of edges with no $K_3$'s in a tripartite graph. A simple double counting argument yields $\max(ab, bc,ac)$.

The answer is $\text{max} (ab, bc, ac)$. Construction: WLOG assume $a \geq b \geq c$. Then, place the $b$ paper ducks all consecutively. Then, in front of those ducks, place the $a$ rock ducks consecutively. Then, in front of those ducks, place the $c$ scissors ducks consecutively. We will acheive $ab$ moves from moving the $b$ paper ducks in front of the $a$ rock ducks, since moving each of the $b$ ducks requires $a$ moves. Call a triple of ducks distinct if each duck picks a different one of rock, paper or scissors. Call a distinct triple of ducks good if the three ducks, from front to back, are rock, paper and scissors, respectively. Call a distinct triple of ducks bad if the three ducks, from front to back, are rock, scissors and paper, respectively. Any distinct triple of ducks must either be good or bad. There are always $abc$ distinct triples of ducks, since we have $a$ choices for rock ducks, $b$ choices for paper ducks and $c$ choices for scissor ducks. At each move, if we, say, swap a rock duck $X$ and a paper duck $Y$, we will lose exactly $c$ good triples and gain $c$ bad triples, since any triple with $X$, $Y$ and a scissor duck goes from good to bad. So, in general, at each move, we lose either $a$, $b$ or $c$ good triples and gain that many bad ones. We can start out with at most $abc$ good triples, which gives us an upperbound of $\text{max} (a,b,c)$.

I'm finally understanding a friend of mine's bird hate addiction Groupsolved with KL, with help from RL Instead of rock, paper, scissors, we will use $0$, $1$, $2$ instead, to simplify notation. Notice that if $n$ mod $3$ is sitting behind $n-1$ mod $3$, then they will switch places. For simplification, we will also assume WLOG that $a\leq b \leq c$. We claim that the maximum number of swaps possible is $\text{max}(ab,ac,bc)$. 1. "Duck-domination triples" We define a triple of any three ducks in the circle (not necessarily consecutive) to be "duck-dominating" if they are in the clockwise order $2$, $1$, $0$, or rotations. Note that there are at most $abc$ "duck-domination" triples in the starting configuration - $c$ possibilities for the $2$-duck, $b$ for the $1$-duck, and $a$ for the $0$-duck. 2. Dominating ducks as an invariant Notice that every time we swap a $0$ and $1$-duck, we decrease the number of "duck-dominating" triples by $c$ - aka all the triples with the $0$ and $1$-duck fixed as the ducks we just swapped, with $c$ possibilities for the $2$-duck. Similarly, if we swap a $1$ and $2$-duck, the number of "duck-dominating" triples will go down by $c$. It also follows that by swapping a $2$ duck and a $0$-duck, the number of "duck-domination" triples goes down by $a$. Notice that when there are no more "duck-dominating" triples, we can no longer swap any more ducks. However, with each swap, the number of "duck-domination" triples must go down by $a$, meaning that we can make at most $bc$ moves. 3. How to swap ducks? The maximum can be achieved by having the all the ducks in $0$, $1$, $2$ blocks, in the order of $2$, $1$, $0$, clockwise. Then we can just swap out all of the $1$s and $2$s until the two blocks completely swap places, which takes $bc$ moves, finishing the problem.

Easiest TSTST problem ever. We claim the answer is max(ab,bc,ca), with blocks of rock, scissor, then paper ducks. Consider the number of triples of rock-scissor-paper (must be this order, no cyclic shifting) going clockwise; for every switch of two types x and y, the value decreases by z since the x-y switching to y-x gives the x one less option of y, multiplied by z means subtracting z). Hence it decreases by at least min(a,b,c), implying there are at most \(\frac{abc}{\min(a,b,c)}=\max(ab,bc,ac)\) moves. Remark. The construction is obviously an easy one to guess, and also we're motivated by the fact that we want to subtract as little as possible each time, which means they should be blocks.

quack. The answer is $\max(ab, bc, ca)$. A construction is to take $a$ rock-ducks, then $c$ scissor-ducks, then $b$ paper ducks - clearly this works. To see this is maximal, count the number of triples of ducks $(d_1, d_2, d_3)$ such that $d_1$ is a rock-duck, $d_2$ is a scissor-duck, and $d_3$ is a paper duck. With a move, the number of these triples decreases by one of $a$, $b$, $c$, but there are at most $abc$ of these triples, from where we extract the answer.

Very easy problem The answer is Maximum of (ab,bc,ca)

Quack. Denote the rock, paper and scissors ducks by $d^r$, $d^p$ and $d^s$ ducks. Denote the cycle of ducks by $(d_1, d_2, \dots, d_{a+b+c})$, with $d_i$ behind $d_j$ if $i < j$ and $d_{a+b+c}$ behind $d_1$. Consider the triples of the form $(d^r d^s, d^p)$. Clearly in such a triple each duck majorizes the duck in front of them. Also note that once one swap occurs between these three ducks, this triple may perform no more swaps. For example if $d^r$ and $d^s$ swap we are left with $(d^s, d^r, d^p)$ which may be observed to have no moves. Thus for any of these triples over all ducks we may perform at most $1$ move. Now note that the number of such triples is at most $abc$. Now the nuanced part. Say that a duck $d^r$ and $d^p$ swap. Then we may find that the total number of triples $(d^r, d^s, d^p)$ decreases by $c$. Similarly on swaps between ducks $d^s$ and $d^p$ we find the triples decrease by $a$, and $d^s$ and $d^r$ leads to a decrease in triples by $b$. To maximize the number of moves, we should try to minimize the loss of triples at each move. Thus if $a \leq b \leq c$, we would always swap ducks $d^s$ and $d^p$. The actual answer is then given by $\boxed{\frac{abc}{\min(a, b, c)}}$. To see equality achieved, assume $a \leq b \leq c$. Then place all $d^r$ ducks in front of $d^p$ ducks, all $d^p$ ducks in front of $d^s$ ducks and all $d^s$ ducks in front of $d^r$ ducks. Then only perform swaps involving $d^r$ ducks and $d^s$ ducks which gives $bc$ swaps as desired.

Solved with hints. I'm just really bad at process-type problems. We claim that the answer is $\max(ab,bc,ca)$. WLOG, we consider that a duck $D_1$ is behind another duck $D_2$ if and only if duck $D_1$ lies after $D_2$, in the clockwise direction (starting from the top-most point of the circle). It is easy to see that this answer is clearly achievable by consider the $a$ ducks with rocks, $b$ ducks with paper and $c$ ducks with scissors being placed consecutively, in that order going clockwise. Assume WLOG, $ab = \max(ab,bc,ca)$. Then, each of the ducks with rocks, and swap places with each duck with paper in a turn, and move to the end of the chain of ducks with paper. Then, each duck with rock swaps positions which each duck with paper so we have $ab$ moves. Now, let $\mathcal{T}$ at any given moment, be the number of triples of ducks $(D_1,D_2,D_3)$ where $D_1$ picks rocks, $D_2$ picks paper and $D_3$ picks scissors, and they lie in this order going clockwise. Now, we make the following observation. Claim : After each move $\mathcal{T}$ (strictly) decreases. In particular if a move is done on a pair of ducks picking rock and paper, then $\mathcal{T}$ decreases by $c$. Proof : WLOG, consider a move which swaps a duck $D_R$ picking rock and a duck $D_P$ picking paper . Consider a triple $T_1$ of ducks of the above described form. Then, if $D_R$ and $D_P$ are both included in this triple, after the swap this triple will be invalidated since the duck picking rock and the duck picking paper are now in the wrong order. Further, if $D_R$ is only included in this triple, swapping $D_R$ and $D_P$ will have no effect to the inclusion of $T_1$ is the count $\mathcal{T}$, since $R$ is still in front of any duck picking paper which is behind $D_P$. Similarly, if $D_P$ is only included in this triple, the swap won't have an effect. If neither $D_R$ nor $D_P$ is included then it clearly won't have an effect since the positions of all ducks besides these two are not even changed. Thus, each move decreases $\mathcal{T}$ by $c$ since every pair of ducks $D_R$ and $D_P$ contributes exactly $c$ triples (consider the triples $(D_R,D_P,D_C)$ for each duck $D_C$ picking scissors - which all work since these triples are all in clockwise direction). Now, note that each move decreases $\mathcal{T}$ by one of $a$ , $b$ or $c$ depending on which type of move has been executed. Now, in the beginning $\mathcal{T}\leq abc$ since if there exists a duck picking scissors between a duck picking rock and a duck picking paper etc, the number of triples $\mathcal{T}$ will not be maximized. Thus, the maximum is when all the ducks of each type are consecutive, which can be simply counted to give $\mathcal{T}=abc$ in the starting configuration. Now, note that if $a=\min(a,b,c)$, then in each move $\mathcal{T}$ decreases by atleast $a$. So, we cannot expect to have more than, $\frac{abc}{a}=bc = \max(ab,bc,ca)$ moves as claimed.

I don’t understand this problem. If a duck which chooses rock is sitting behind a scissor-duck and behind it (the original rock-duck) there is a paper-duck, where will it go / move?

The answer is $\max(bc,ca,ab)$, achieved by placing rock ducks before paper ducks before scissors ducks. Suppose each duck faces the one after it in counterclockwise order. Consider a graph with a vertex at each duck's initial position, and connect two vertices if one of the ducks they correspond to ever passes the other. Label rock, paper, and scissors vertices with $0$, $1$, and $2$ respectively. Claim: There cannot be a vertex connected to vertices of both other labels. Proof: If the three vertices in counterclockwise order are $0$, $1$, and $2$, then no moves can be made between them, so their relative positions are unchanged. If the three vertices in counterclockwise order are $0$, $2$, and $1$, then only one move can be made before the vertices are ordered $0$, $1$, and $2$. Thus, none of the vertices can be connected to the other two. $\square$ Let an $xy$ vertex be a vertex with label $x$ connected to a vertex with label $y \ne x$, and let $a_{xy}$ be the number of $xy$ vertices. Notice that $x_{01}+x_{02} \le a$, $x_{12}+x_{10} \le b$, and $x_{20}+x_{21} \le c$. We also know the total number of duck swaps is at most \[x_{01}x_{10}+x_{12}x_{21}+x_{20}x_{02} \le x_{01}(b-x_{12})+x_{12}(c-x_{20})+x_{20}(a-x_{01}).\]Since this equation is linear in $x_{01}$, $x_{12}$, and $x_{20}$, we only need to check the boundary points of $\{0,a\} \times \{0,b\} \times \{0,c\}$. If all three are zero or all three are nonzero, the expression becomes $0$. If one or two are nonzero, the expression becomes one of $ab$, $bc$, or $ca$, so it is maximized at $\max(ab,bc,ca)$, as desired. $\blacksquare$

The answer is $\max(ab, bc, ca)$, which can be achieved by placing all rock ducks, then all scissor ducks and then all paper ducks. Let's consider a tuple of rock, scissor and paper duck in that cyclic order to be called as fight tuple.. Then initially there can be at most $T = abc$ fight tuples. When we swap a rock duck with scissor duck, we decrease $T$ by $b$. Similar argument happens when we swap scissor duck with paper duck and paper duck with rock duck. Hence proved.

$ $