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

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

(Created page with "==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 <math...")
 
(→‎Solution)
 
(2 intermediate revisions by one other user not shown)
Line 13: Line 13:
 
<math>(0,0, 0, 2) \longrightarrow (3, 0,1) \longrightarrow (1, 1, 0, 1) \longrightarrow (1, 3) \longrightarrow \cdots </math>
 
<math>(0,0, 0, 2) \longrightarrow (3, 0,1) \longrightarrow (1, 1, 0, 1) \longrightarrow (1, 3) \longrightarrow \cdots </math>
 
If instead he started with <math>(0, 0)</math>, he would write down:
 
If instead he started with <math>(0, 0)</math>, he would write down:
−
<math>(0, 0) \longrightarrow  (2) \longrightarrow (0; 0; 1) \longrightarrow (2; 1) \longrightarrow \cdots</math>
+
<math>(0, 0) \longrightarrow  (2) \longrightarrow (0, 0, 1) \longrightarrow (2, 1) \longrightarrow \cdots</math>
 
If Joel starts out with an arbitrary list of nonnegative integers and then continues this process, there
 
If Joel starts out with an arbitrary list of nonnegative integers and then continues this process, there
 
are certain lists <math>(m, n)</math> of length two that he might end up writing an infinite number of times. Find
 
are certain lists <math>(m, n)</math> of length two that he might end up writing an infinite number of times. Find
 
all such pairs <math>(m, n)</math>.
 
all such pairs <math>(m, n)</math>.
  
 +
== Solution ==
 +
<b>Answer:</b>
 +
<i>All</i> pairs of <math>(m, n)</math> work.
  
 +
<b>Proof:</b>
 +
First, note that <math>(2, 2)</math> repeats forever:
 +
<cmath>(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)</cmath>
 +
Now suppose we have <math>m\ne n</math>. Let <math>M =\max(m, n)</math> We get
 +
<cmath>(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)</cmath>
 +
Otherwise, <math>m=n</math>. If <math>n > 1</math> then
 +
<cmath>(n, n)\to (0, 0, \dots, 0, 2)\to (n, 0, 1)\to (1, 1, 0, \dots, 0, 1)\to (n-2, 3)</cmath>
 +
If <math>n=5</math> we get
 +
<cmath>(3,3)\to (1,3) \to \text{Apply (2)} \to (2, 2)</cmath>
 +
Otherwise we get
 +
<cmath>(n-2, 3)\to\text{Apply (2)} \to (2, 2)</cmath>
 +
Our final case is if <math>n = 1</math>. Then we have
 +
<cmath>(1, 1)\to (0, 2)\to (0, 0, 1)</cmath>
 +
which we know repeats from <math>(1)</math>.
  
−
== Solution ==
+
Therefore, for all <math>(m, n)</math> it will repeat forever.
  
 
== See Also ==
 
== See Also ==
 
{{UMO box|year=2014|num-b=3|num-a=5}}
 
{{UMO box|year=2014|num-b=3|num-a=5}}
 +
 +
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 15:45, 12 February 2020

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"