Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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.

See Also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_UMO_Problems/Problem_4&oldid=117718"