# Difference between revisions of "2014 UMO Problems/Problem 4"

## Problem

Joel is playing with ordered lists of integers in the following way. He starts out with an ordered list of nonnegative integers. Then, he counts the number of $0$’s, $1$’s, $2$’s, and so on in the list, writing the counts out as a new list. He stops counting when he has counted everything in the previous list. Then he takes the second list and applies the same process to get a third list. He repeats this process indefinitely.

For example, he could start out with the ordered list $(0, 0, 0, 2)$. He counts three $0$’s, zero $1$’s, and one $2$, and then stops counting, so the second list is $(3, 0, 1)$ In the second list, he counts one $0$, one $1$, zero $2$’s, and one $3$, so the third list is $(1, 1, 0, 1)$. Then he counts one $0$ and three $1$’s, so the fourth list is $(1, 3)$. Here are the first few lists he writes down: $(0,0, 0, 2) \longrightarrow (3, 0,1) \longrightarrow (1, 1, 0, 1) \longrightarrow (1, 3) \longrightarrow \cdots$ If instead he started with $(0, 0)$, he would write down: $(0, 0) \longrightarrow (2) \longrightarrow (0, 0, 1) \longrightarrow (2, 1) \longrightarrow \cdots$ If Joel starts out with an arbitrary list of nonnegative integers and then continues this process, there are certain lists $(m, n)$ of length two that he might end up writing an infinite number of times. Find all such pairs $(m, n)$.

## Solution

Answer: All pairs of $(m, n)$ work.

Proof: First, note that $(2, 2)$ repeats forever: $$(2, 2)\to (0, 0, 2)\to (0, 0, 1)\to (2, 1)\to (0, 1, 1)\to (1,2)\to (0, 1, 1)\qquad (1)$$ Now suppose we have $m\ne n$. Let $M =\max(m, n)$ We get $$(m, n)\to (0, 0, \dots, 0, 1, 0, \dots, 0, 1)\to (M-1, 2)\to \cdots \to (M-2, 2) \to \cdots \to (2, 2)\qquad (2)$$ Otherwise, $m=n$. If $n > 1$ then $$(n, n)\to (0, 0, \dots, 0, 2)\to (n, 0, 1)\to (1, 1, 0, \dots, 0, 1)\to (n-2, 3)$$ If $n=5$ we get $$(3,3)\to (1,3) \to \text{Apply (2)} \to (2, 2)$$ Otherwise we get $$(n-2, 3)\to\text{Apply (2)} \to (2, 2)$$ Our final case is if $n = 1$. Then we have $$(1, 1)\to (0, 2)\to (0, 0, 1)$$ which we know repeats from $(1)$.

Therefore, for all $(m, n)$ it will repeat forever.