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...") |
m (→Problem) |
||
| 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 | + | <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 == | == Solution == | ||
Revision as of 00:19, 14 October 2014
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 
’s, 
’s, 
’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 
. He counts three ’s, zero ’s, and one
, and then stops counting, so the second list is 
In the second list, he counts one , one ,
zero ’s, and one 
, so the third list is 
. Then he counts one and three ’s, so the fourth list
is 
. Here are the first few lists he writes down:
If instead he started with 
, he would write down:
If Joel starts out with an arbitrary list of nonnegative integers and then continues this process, there
are certain lists 
of length two that he might end up writing an infinite number of times. Find
all such pairs .
Solution
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 | ||
