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)$ .

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