When replying to the problem, I ask that you make posts for solutions and submit comments, jokes, smilies, etc. separately. Please use LaTeX for posting solutions. Thanks.

Assume we have proven this for $1,2,\ldots,n-1$. We now perform another induction (an induction within an induction ) as follows: We prove that: $(*)$ given $i\in\overline{1,n-1}$, after the $i$'th operation, $a_n$ is $\ge a_i$, with equality iff $a_i=a_{i+1}=\ldots=a_n$ (in which case the process stops, of course). Suppose we have shown the above for $1,2,\ldots,i-1$. After the $i-1$'th step, the values of $a_1,\ldots,a_i$ will no longer change, by the induction hypothesis, and this implies that $a_0\le a_1\le\ldots\le a_i$, as can easily be seen. We also know that $a_n$ is $\ge a_{i-1}$, with equality iff $a_{i-1}=\ldots=a_n$, in which case we're done, so we can now assume that $a_n>a_{i-1}$. If $a_n=a_i$, then, after one more step (the $i$'th) we have $a_n\ge a_i$ (because $a_i$ doesn't change, and there are at least as many terms different from $a_i=a_n$ among $a_0,\ldots,a_{n-1}$ as there are among $a_0,\ldots,a_{i-1}$), and if there happens to be an equality, then it's clear that all the terms between $a_i$ and $a_n$ have to be equal to $a_i$. If, on the other hand, $a_n\ne a_i$, then $a_0,\ldots,a_i$ are different from $a_n$, meaning that after one more step (again, the $i$'th) we will have $a_n\ge i+1>a_i$. $(*)$ is now proven for $i$, so, by induction, it holds for all values $\in\overline{1,n-1}$. Now we apply $(*)$ to $i=n-2$. We perform the exact same steps as in the proof of $(*)$, except that this time, if $a_n\ne a_{i+1}$, there must be $n$ terms different from $a_n$ preceding it, and we get $a_n=n$ after the $n-1$'th step. Otherwise, if $a_n=a_{i+1}=a_{n-1}$, then we're already at a dead end. Either way, $n-1$ steps suffice to reach a sequence which no longer changes. I'm sure I messed up those indices somewhere in there, but I hope at least that the idea is Ok .

please tell me what is wrong with my solution, because it is otherwise too easy for a USAMO #3: prove by induction, the exact claim of the problem itself (i.e. not some instructive induction within an induction; jsut an easy normal induction) on $n$. Suppose everything up to $n-1$ is proved. Now consider an $n$ situation. Operate it $n-1$ times. At the $n-1$ turn, we will get $a_{1}, ...a_{n}$ such that at the $n$ turn, $t(a_{i})=a_{i}$ for all $i$ between 0 and $n-1$,by the induction hypothesis. (*) Now, examine in the $n$ turn: see how its $a_{n}$ changed from the $n-1$ turn: $t(a_{n})$= # of $a_{i}$'s that are different from $a_{n}$. (**) At the $n+1$ turn now, the $n$th term will remain constant now, because of (*), combined with (**), and the induction is complete.

Hmm this is really easy for a USAMO #3... Here's a solution that doesn't use induction: Let $ i\in\{0,1,2,...,n\}$. First, note that $ t(a_{i})\le i$, since there are $ i$ terms before it and thus no more than $ i$ terms precede it and are distinct from it. Next, we show that $ t(a_{i})\ge a_{i}$. The numbers $ a_{0},...,a_{a_{i}-1}$ are all less than $ a_{i}$ and precede it in the sequence, so there are at least $ a_{i}$ terms before $ a_{i}$ that are distinct from it. Each time we perform the operation, either $ a_{i}$ will increase or it will remain the same. If it remains constant, this means that $ a_{a_{i}}= a_{a_{i}+1}= ... = a_{i}$, and thus the terms $ a_{a_{i}},...,a_{i}$ will always remain constant. Otherwise, it will increase until it reaches $ i$ and will then become constant. For $ i\le n-1$, $ a_{i}$ will thus become constant in less than $ n$ applications of $ t$. In the case of $ a_{n}$, we need only worry if $ a_{n}= 0$, in which case $ n-1$ applications of $ t$ will not necessarily make $ a_{n}$ become constant or equal to $ n$. We need to show that it either becomes constant or that it increases by at least $ 2$ during some application of $ t$, so that it will reach $ n$ in less than $ n$ applications of $ t$. If all terms the terms are 0, then the sequence will remain constant under the operation. If at least two terms preceding $ a_{n}$ are nonzero, then $ a_{n}$ will become at least $ 2$ after one application of $ t$ and will then become constant within $ n-2$ more applications of $ t$. Otherwise, exactly one preceding term, which we denote by $ a_{k}$, is nonzero. If $ k = 1$ then $ t(a_{0}) = 0$ and $ t(a_{1}) = t(a_{2}) = ... = t(a_{n}) = 1$ so the sequence becomes constant. If $ k > 1$, then $ t(a_{0}) = t(a_{1}) = 0$, $ t(a_{k})\ge 2$ because $ a_{k}\neq 0 = a_{0}= a_{1}$, and $ t(a_{n}) = 1$. Thus a second application of $ t$ will make the last term at least 3, so $ n-3$ more applications will make it constant. Thus, no matter what, after fewer than $ n$ applications of $ t$ the sequence will become constant. QED

sunchips wrote: please tell me what is wrong with my solution, because it is otherwise too easy for a USAMO #3: prove by induction, the exact claim of the problem itself (i.e. not some instructive induction within an induction; jsut an easy normal induction) on $ n$. Suppose everything up to $ n - 1$ is proved. Now consider an $ n$ situation. Operate it $ n - 1$ times. At the $ n - 1$ turn, we will get $ a_{1}, ...a_{n}$ such that at the $ n$ turn, $ t(a_{i}) = a_{i}$ for all $ i$ between 0 and $ n - 1$,by the induction hypothesis. (*) Now, examine in the $ n$ turn: see how its $ a_{n}$ changed from the $ n - 1$ turn: $ t(a_{n})$= # of $ a_{i}$'s that are different from $ a_{n}$. (**) At the $ n + 1$ turn now, the $ n$th term will remain constant now, because of (*), combined with (**), and the induction is complete. This problem is confusing me. Correct me if I'm wrong but I think there is a problem with the induction step at the $ n$ turn. By the induction hypothesis, terms $ 0$ to $ n-1$ remain invariant. However, it may take more than one turn to get term $ a_n$ invariant. After we transform $ a_n$ on turn $ n$, $ a_n$ changes to something else, but that gives the possibility of it changing again. Here is an example, take the sequence $ 002344663$. We see that the $ 3$ at the end changes to $ 7$. Now we get $ 002344667$. Now we see that another transformation turns the $ 7$ into an $ 8$. Giving us $ 002344668$ which took $ 2$ moves to stabilize. Now, does this affect the validity of other induction solutions? Thanks!

Let an "awesome-k" sequence be a sequence such that for every $ 0 \leq i \leq k$, $ t(a_i) = a_i$, and for every $ j > k$, $ a_j$ is bigger than the second highest distinct integer among $ a_{ - 1}, a_0, a_1 \cdots a_k$. Also, $ a_k$ must be the biggest term among $ a_0, a_1, \cdots a_k$. We use an auxiliary term of $ a_{ - 1} = - 1$, so this will remain true even when there is only one value. It is immediately evident that the starting sequence is an awesome-0 sequence. All the numbers are greater than -1. Assume that we have an "awesome-k" sequence after $ k$ applications of $ t(A)$. We have two cases: Case 1: $ a_{k + 1} = a_k$. This means that $ a_{k + 1}$ is already fixed and the second highest value in $ a_0, a_1 \cdots a_k$ will not change, and thus we get an "awesome-k+1" sequence after applying $ t(A)$ once.. Case 2: $ a_{k + 1} \neq a_k$. $ a_{k + 1}$ cannot be equal to any term among $ a_0, a_1 \cdots a_k$, and thus $ t(a_{k + 1}) = k + 1$. The previous $ a$'s are all fixed, and thus $ a_{k + 1}$ is also fixed after applying $ t(A)$. For the rest of the $ a_i$'s in which $ i > k + 1$, we have 2 cases: Case 2.1: $ a_i = a_k$. This means that $ t(a_i) > a_k$, because $ a_i$ is different from $ a_{k + 1}$ in addition to the terms that $ a_k$ is different from. Case 2.2: $ a_i \neq a_k$. $ a_i$ cannot be equal to any term among $ a_0, a_1 \cdots a_k$, and thus $ t(a_i) > k \ge a_k$. In both cases, $ t(a_{k + 1}) \ge a_k$, and as $ a_k$ is the biggest term among $ a_0, a_1, \cdots a_k$, $ t(a_{k + 1})$ must be the biggest term among $ t(a_0), t(a_1) \cdots t(a_{k + 1})$. In addition, $ t(a_k) = a_k$ must be either the second or first biggest term in $ t(A)$, and thus, after applying $ t(A)$, we are left with an "awesome-k+1" set. We have taken $ k + 1$ moves, completing our inductive step. We immediately see that the "awesome-n" set satisfies the problem statement, and we are done.

I'm not understanding what $ t(a_i)$ represents when applied to a sequence. You said above that it is the number of terms that precede a given element in a sequence and are different from it. Are the elements in the sequence ordered according to their magnitude.

We use strong induction on $n\ge1$, where the base case $n=1$ is obvious. For $n\ge2$, first note that $t^r(a_i)\le i$ for all $r\ge0$. If $a_i=i$ for all $0\le i\le n$ we're trivially done. Otherwise, let $a_k$ be the first number in the sequence such that $a_k\le k-1$ (so $1\le k\le n-1$). If $a_l\le k-1$ for all $l\ge k$, then $t^2(A)=t(A)$. Otherwise, let $a_l$ with $k+1\le l\le n$ be the first number after $a_k$ such that $a_l\ge k$. Then (1) $t(a_i)=i$ for $0\le i\le k-1$, (2) $t(a_i)=k-1$ for $k\le i\le l-1$, and (3) $k\le t(a_i)\le i$ for $l\le i\le n$ by considering the numbers $a_0,a_1,\ldots,a_{k-1},a_{k},a_l$ preceding $a_i$ (except for $i=l$, in which case $k+1\le t(a_l)\le l$ anyway). Hence (1) $t^2(a_i)=i$ for $0\le i\le k-1$, (2) $t^2(a_i)=k-1$ for $k\le i\le l-1$, and (3) $k<l\le t^2(a_i)\le i$ for $l\le i\le n$ by considering the numbers $a_0,a_1,\ldots,a_{l-1}$ preceding $a_i$. If $l=n$, then $t(A)=t^2(A)$, so suppose that $l\le n-1$ ($l\ge k+1\ge2$, so $n\ge3$). Now define the sequence $A'$ by $a'_i=t^2(a_{i+l})-l\in[0,i]$ for $0\le i\le n-l$. By the inductive hypothesis, \[t^{n-l-1}(A')=t^{n-l}(A')\implies t^{n-3}(A')=t^{n-2}(A').\]But it's easy to see for all $r\ge0$ that $t^{r+2}(a_i)=t^2(a_i)$ for $0\le i\le l-1$ and $t^{r+2}(a_i)-l=t^{r}(a'_{i-l})$ for $l\le i\le n$, so \[t^{n-1}(A)=t^{n}(A),\]as desired.

MithsApprentice wrote: Let $n \neq 0$. For every sequence of integers \[ A = a_0,a_1,a_2,\dots, a_n \]satisfying $0 \le a_i \le i$, for $i=0,\dots,n$, define another sequence \[ t(A)= t(a_0), t(a_1), t(a_2), \dots, t(a_n) \]by setting $t(a_i)$ to be the number of terms in the sequence $A$ that precede the term $a_i$ and are different from $a_i$. Show that, starting from any sequence $A$ as above, fewer than $n$ applications of the transformation $t$ lead to a sequence $B$ such that $t(B) = B$. This seems too good to be true, so someone please point out any errors. We go by strong induction on $n$ with the base cases $n=1$ and $n=2$ done by hand. If $a_0 = 0$ and $a_1 = 1$, so $1 \le t(a_i) \le i$ for $i \ge 1$; now apply induction to $\left(t(a_1)-1, t(a_2)-1, \dots, t(a_n)-1\right)$. Otherwise, assume that $a_0 = a_1 = \dots = a_{k-1} = 0$ but $a_k \neq 0$, where $k \ge 2$. Assume $k < n$ or it's obvious. Then $t(a_i) \neq 0$ for $i \ge k$, thus $t(t(a_i)) \ge k$ for $i \ge k$, and we can apply induction hypothesis to $\left( t(t(a_k))-k, \dots, t(t(a_n))-k \right)$.

This seems too convenient for a USAMO P3 and possibly even for a 25M problem (rated by v_Enhance). Can anyone check if this is correct? We say that $a_i$ is contiguous with $a_j$ if and only if either $a_i=a_{i+1}=a_{i+2}=\hdots=a_j$ or $a_i=a_{i-1}=a_{i-2}=\hdots=a_j$. The key claim is the following. Claim: $t(a_i)\geq a_i$ for all $i$. Moreover, if $t(a_i)=a_i$, then $t(t(a_i)) = a_i$. Proof: Consider the smallest index $k$ which $a_k=a_i$; notice that $k\geq a_i$ by the problem. Thus, $a_0,a_1,\hdots,a_{k-1}$ are all different to $a_i$, which means that $t(a_i)\geq k\geq a_i$. If the equality occurs, then $k=a_i$ and $a_{a_i},a_{a_i+1},\hdots,a_i$ are all equal to $a_i$. This string of $a_i$'s clearly remains fixed throughout subsequent applications of $t$, which implies the claim. $\blacksquare$ By the claim, each term strictly increases or remains stable forever, but each term must lie in $[0,n]$, so it cannot increase $n+1$ times or more; this means that after at most $n$ applications of $t$ produce a sequence which is fixed by $t$. It remains to show that the equality never occur. This happens only if $a_n$ goes from $0\to 1\to 2\hdots\to n$. From the first application, we can see that the sequence must be in form \begin{align*} &\overbrace{0,0,\hdots,0}^{k\ 0\text{'s}},\color{red}1\color{black},0,0,\hdots,0 \\ \stackrel{t}{\mapsto}\ &0,0,\hdots,0,\color{red}1,1,1,\hdots,1\color{black} \\ \stackrel{t}{\mapsto}\ &0,0,\hdots,0,\color{red}k,k,k,\hdots,k \\ \stackrel{t}{\mapsto}\ &0,0,\hdots,0,\color{red}k,k,k,\hdots,k \end{align*}which is a contradiction if $n\geq 3$. The case $n=1,2$ can be checked manually.

Solution with awang11. Claim: We have $t(a_i)\ge a_i$. Solution: Suppose otherwise. Then there are more than $i-a_i$ values of $j$ for which $j<i$ and $a_j=a_i$. But one of those values of $j$ must be at most $a_i-1$, which is a contradiction. $\fbox{}$ Claim: If $t(a_i)=a_i$ and $a_i=x$ then $a_x=...=a_i$. Solution: None of $a_0...a_{x-1}$ are equal to $x$ so we can yeet $a_x\dots a_i$ out of the window since they must have nothing unequal to $x$ and the claim is shown. $\fbox{}$ In particular, $t(a_i)=a_i$ implies $t(t(a_i))=a_i$ and so on because each of $a_x,a_{x+1},\dots,a_i$ must become fixed at $x$. Now, for the endgame: strong induct on $n$ with the result obvious at $n=1$. Consider the sequence $a_n,t(a_n),\dots,t^n(a_n)$. These numbers must all be distinct, or we are done by the induction hypothesis along with the last two claims. That is, we get $t^i(a_n)=i\forall 0\le i\le n$. Suppose that $a_{n-1}$ was fixed at step $k$ with value $x$. Clearly $k\le x$. By step $x$, $t^x(a_n)$ is $x$, so the next step may not change the value of $a_n$. This implies $a_n$ is fixed, so we are done.

Why do all the problems in Rigid feel like they're shifted up a slot compared to their actual difficulty??

Derp We proceed with strong induction. The base case $n=1$ is trivial. Claim: after an application, there can be no zeroes following a nonzero term. Proof: suppose that $t(a_i)\neq 0$; this necessarily means that there are at least two distinct values present among $a_0,a_1\ldots a_i$, and hence $t(a_{i+1})\neq 0$. Notice that $t(a_0)=0$, and therefore we must have a glob of some $k$ zeroes at the start. We can ignore them and treat the subsequent terms as a sequence with length at most $n-k$ shifted by $k$, which completes the induction.

Strong induction on $n$, with the base cases being manually verifiable. Evidently $a_0=0$, which remains eternally fixed. If $a_1=1$, then $1 \leq t(a_i) \leq i+1$ for $i \geq 1$: the right inequality is obvious, and the left inequality is true for $i=1$ and must also be true for $i>1$, else $a_i=0=1$ which is absurd. In this case, we can thus imply inductive hypothesis to $t(a_1)-1,\ldots,t(a_n)-1$. Otherwise, suppose we have $a_0=a_1=\cdots=a_{k-1}=0$, so $a_0,\ldots,a_{k-1}$ are eternally fixed, but $a_k \neq 0$. Then for $i \geq k$, $t(a_i)>0$, hence $t(t(a_i))\geq k$ as $t(a_i)$ can't equal $t(a_0),\ldots,t(a_{k-1})$. Since $k \geq 2$, we can imply our inductive hypothesis to $t(t(a_k))-k,\ldots,t(t(a_n))-k$. $\blacksquare$

We claim that this is true by induction. Clearly, the base case of $n = 1$ is true. Assume that it is true for $n = k-1$. Then, after $k-2$ applications of transformation $t$, $a_{0}, a_{1}, \cdots, a_{k-1}$ will be fixed. Because these integers are fixed, then after another application of transformation $t$, $a_{k}$ must also be fixed, which thus concludes the proof.

Define $s^k(A)=n-t^k(a_0),n-t^k(a_1),\dots,n-t^k(a_n).$ Consider the graph created by plotting $0,1,2,\dots,n$ as the $x$-axis and $s^k(A)$ as the $y$-axis. For any $i=0,\dots,n$ define $L_i$ to be the set of lattice points $(x,y)$ satisfying $x-y=i-s^k(a_i)$ and $x<i.$ It is easy to see that the graph of $s^{k+1}(A)$ is created by taking each marked point $(i,s^k(a_i))$ in the graph of $s^k(A)$ and moving it down by the number of unmarked points in $L_i.$ We say that a point $(i,s^k(a_i))$ is grounded if all points in $L_i$ are marked. Notice that if $(i,s^k(a_i))$ is grounded then $s^k(a_i)=s^{k+1}(a_i),$ and we can see that $(i,s^{k+1}(a_i))$ is also grounded, so $s^k(a_i)=s^{k+j}(a_i)$ for any positive integer $j.$ Next, notice that if $(i,s^k(a_i))$ is not grounded, then $s^k(a_i)-s^{k+1}(a_i) \ge 1.$ Also, notice that if $s^k(a_i)=0$ then $(i,s^k(a_i))$ is trivially grounded. Now, since all elements of $A$ are $\le n,$ after $n-1$ applications of $s$ we find that all points are either grounded, or we have $s^{n-1}(a_n)=1.$ This last case can only occur if $a_n=n$ and the point with $x$ coordinate $n$ goes down by one every time $s$ is applied. However, consider the situation before the first application of $s.$ We must have $L_n$ contains $n$ marked points, that is, there is exactly one $i$ such that $a_i \ne i.$ We have $i \ne 0,$ and we can see that if $i \ge 2$ then the points with $x$-coordinates $0,1,\dots,i-1$ are grounded, $s(a_i)=0,$ and all other points go down by one. However, after this transformation, we find that the only marked points in $L_n$ are points $(j,s(a_j))$ such that $j>i,$ and since there are less than $n-1$ of these we have that the point with $x$ coordinate $n$ goes down by at least $2$ after another transformation. Now consider if $i=1.$ We can easily check that after one transformation, all points become grounded, so we are done.

We proceed by using induction. For the base case $n=1$, note that $0 \le a_0 \le 0$ which forces $a_0$ to be $0$. Similarly, we also get that $a_1\in \left\{0,1\right\}$. If $a_1=0$, then our sequence is $(0,0)$. Note that applying $t$ on the sequence does not change it. Similarly, if $a_1 = 1$, then also applying $t$ on the sequence does it change it either. Now we assume the inductive hypothesis for some $n=k$ and we prove for the case $n=k+1$. Note that the succeeding elements after $a_i$ do not affect the value of $a_i$ in any way. We now work with the sequence whose final element is $a_{k+1}$. Then after $k-1$ applications of the function $t$ on the elements, we end up with a sequence such that if we apply $t$ once more on the sequence, the sub-sequence $a_0, a_1, \ldots, a_k$ remains invariant. Thus after the $k$th application of the function $t$, the $a_n$ element gets fixed too as the previous elements do not change, which finishes our induction.

We'll proceed induction on $n$, with base case $n=1,2$ being clear. Now assume its true on $n-1$. Claim: $t(a_i) \ge a_i$ and if $t(a_i) = a_i$, then $t(t(a_i)) = a_i$. Proof. Note that for $0 \le k \le a_i - 1$, we have $a_k \le k \le a_i-1$, so there are at least $a_i$ numbers in the sequence $(a_0, a_1, \dots, a_{i-1})$ that are different from $a_i$, so $t(a_i) \ge a_i$. Equality occurs if and only if $a_{a_i} = a_{a_i + 1} = \dots + a_{i-1} = a_i$. In that case, $t(t(a_i)) = a_i = t(a_i)$. $\blacksquare$ Call a sequence $A$ is good if $t(A) = A$. After $n-1$th transformation, assume we get a sequence $X = (x_0, x_1, \dots, x_n)$. By induction hypothesis, sequence $X' = (x_0, x_1, \dots, x_{n-1})$ is a good sequence. If, at some point, $t^k(a_n) = t^{k+1}(a_n)$, then $X$ is already good sequence. Thus $t^{k+1}(a_n) > t^k(a_n)$ for all $0 \le k \le n-2$. Shifting down, we get that $n n \ge x_n = t^{n-1}(a_n) \ge n-1 + a_n \ge n$, so $x_n = n$ and thus a sequence $X$ is good, as needed. $\blacksquare$

We use a simple strong induction on base case $n=1.$ Note that $a_0=0$ always, as there are no terms before $a_0$ for $a_0$ to be not equal to. Now, we have two cases. When there is just $a_1 \neq 0,$ then we can simply just use $t$ once, and then all terms but $a_0$ are $>0,$ so we can simply get rid of $a_0$ and subtract one from all terms, where the new sequence's $a_n$ is $a_{n+1}$ in the original sequence. When there is more than one $0$ at the beginning, we simply need to use $t$ twice in case there are any other $0$s in the sequence apart from the starting string, the length of which let's call $k.$ Then we can also just get rid of $a_0$ through $a_{k-1},$ and subtract $k$ from every other term in the sequence. This completes the induction$.\blacksquare$