Here is a problem that I've been musing over for a while, haven't found the answer to yet, and don't know its actual name in math. It regards sequences of integers, trees that can balloon to huge complexity, and infinite loops. All right, let's get started!
Pick a sequence, any sequence, preferably a short one with small numbers. For this example, I'll use the sequence 1,1. (Trailing zeroes are not allowed. For example, 1,1,0 cannot be used.)
Now, write down the number of each integer in the sequence as another sequence. This one has 0 zeroes and 2 ones, so the next sequence would be 0,2.
Repeat this process. It has 1 zero, 0 ones, and 1 two, so it would become 1,0,1, then 1,2, then 0,1,1, then 1,2, then - the sequence repeated! It gets stuck in a loop from 0,1,1 to 1,2. Here is another example.
3
0,0,0,1
3,1
0,1,0,1
2,2
0,0,2
Maybe this sequence continues forever without repeating. Let's keep going.
2,0,1
1,1,1
0,3
1,0,0,1
2,2
It went back to 2,2.
Let's map out a tree of possibilities. Each sequence points to its resulting one with an arrow (e.g. 2,2 points to 0,0,2). However, we will also backtrack. For example, the sequence 0,1,0,1 can be derived from 3,1, but 1,3 also leads to it. Those will also be on the tree. Maybe all possible sequences will be on it!
The tree begins with 1 at its base. (I am leaving out the commas for compactness.)
Pick a sequence, any sequence, preferably a short one with small numbers. For this example, I'll use the sequence 1,1. (Trailing zeroes are not allowed. For example, 1,1,0 cannot be used.)
Now, write down the number of each integer in the sequence as another sequence. This one has 0 zeroes and 2 ones, so the next sequence would be 0,2.
Repeat this process. It has 1 zero, 0 ones, and 1 two, so it would become 1,0,1, then 1,2, then 0,1,1, then 1,2, then - the sequence repeated! It gets stuck in a loop from 0,1,1 to 1,2. Here is another example.
3
0,0,0,1
3,1
0,1,0,1
2,2
0,0,2
Maybe this sequence continues forever without repeating. Let's keep going.
2,0,1
1,1,1
0,3
1,0,0,1
2,2
It went back to 2,2.
Let's map out a tree of possibilities. Each sequence points to its resulting one with an arrow (e.g. 2,2 points to 0,0,2). However, we will also backtrack. For example, the sequence 0,1,0,1 can be derived from 3,1, but 1,3 also leads to it. Those will also be on the tree. Maybe all possible sequences will be on it!
The tree begins with 1 at its base. (I am leaving out the commas for compactness.)
Now, let's go through the rules as explained before, until a loop is reached. (The images are sort of crude, as I'm not a graphic designer.)
Now, the backtracking. It is easier to simply find anagrams of existing sequences, or changing the order of the integers (e.g. 3,2 is an anagram of 2,3). Remember, zeroes are not allowed at the end. 1, 01, 11, and 02 cannot be anagrammed. 101 and 011 are anagrams of each other, and are already connected to whatever they should be. This leaves 12, which can be anagrammed as 21, meaning that it should come from 011, which is where 12 leads. This seems to be going somewhere!
Now, 21 itself can be backtracked, so the sequence that it backtracks to must have 2 zeroes and 1 one. There is only one way to write that without having a zero at the end, and that is 001.
Lastly, the only sequence that comes from that is 2.
So now, the tree is complete. It does not go any further. That was disappointing.
However, what if the tree had a base of the number 3? It turns out that the tree explodes to huge sizes very quickly. Now for the questions!
Is the tree with a base of 3 infinitely large? If not, draw the entire tree. If so, prove that it is infinite. There is a countably infinite number of sequences that do not end in a zero, and therefore the tree (if it is infinite) must have a countable number of nodes. Can you find a numbering scheme that maps exactly one positive integer to each sequence of non-negative integers that does not end in a zero?
I actually do not know the answer to this question. Maybe you can figure it out for yourself!
However, what if the tree had a base of the number 3? It turns out that the tree explodes to huge sizes very quickly. Now for the questions!
Is the tree with a base of 3 infinitely large? If not, draw the entire tree. If so, prove that it is infinite. There is a countably infinite number of sequences that do not end in a zero, and therefore the tree (if it is infinite) must have a countable number of nodes. Can you find a numbering scheme that maps exactly one positive integer to each sequence of non-negative integers that does not end in a zero?
I actually do not know the answer to this question. Maybe you can figure it out for yourself!