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.

2014 UMO (Problems • Answer Key • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6
All UMO Problems and Solutions

Page

Toolbox

Search

2014 UMO Problems/Problem 4

Problem

Solution

See Also