1
$\begingroup$

Link to the problem here but will restate the essence in the question anyway, for completeness. https://adventofcode.com/2020/day/15

So, the Elves are playing a game where they take turns saying numbers. First, they say the numbers in a given finite starting sequence of nonnegative integers. Let's say the starting sequence is "1, 2, 3".

After that, they take turns as follows:

  • Consider the last number that was said.
  • If that number hasn't ever been said before, say "0" and end your turn.
  • If the number has been said before, say the number of turns between the last occurrences.

So in our example, the numbers said start with 1, 2, 3.

Now, 3 has never been said before, so for the next turn the elf says "0". For the next turn, "0" has never been said before, the next elf says "0" as well.

Now for the next turn, the last number said was 0. It has been said before just 1 turn before that, so the elf says "1".

Now we're at 1, 2, 3, 0, 0, 1.

So the next number to be said is "5", because that's the distance between the 1s.


The coding challenge is to find the 300000000th number. Brute force is entirely possible by just applying those rules. But I wondered if there could be shortcut by finding a cycle. If we knew that the sequence from a given turn onward repeats.

I have a strong feeling that the answer is "no", and that there is in fact no cycle, but I have a hard time proving it. Some observations I had so far:

  • Due to the special rule for "0", no cycle can ever contain the number "0", because the second time around the number that caused "0" to be said wouldn't be "new", so it wouldn't be followed by 0.
  • If there was a cycle of length N, the largest number it can contain is N.
  • A cycle of length N cannot consist of N distinct numbers; otherwise they'd all have to be "N" (contradiction).
  • There is one trivial cycle: If your starting sequence is "1, 1" then it will just repeat "1" forever. However, that is only possible if you actually start with "1, 1". You cannot get there any other way. The reason for this is that, if you see "1, 1" in the sequence, you can uniquely go backwards: The second 1 means the preceding number was seen before, just one turn away. Well, the preceding number is 1. So we know the next number to the left must have also been a one. Ad infinitum.

I think the last part is generally true: If we have a sequence that goes on forever "to the right" it also must go on forever to the left. That means if there's a cycle, we must have started with that cycle. Together with the first observation (no 0s in a cycle) means that we can definitely give a somewhat weaker result: As soon as you find a "0" during your game, you know that you will never hit a cycle.

Okay, but what about the even stronger result that even without 0s you can never hit a (non-trivial) cycle? There I'm quite lost, and probably approaches this in too elementary a fashion. Any hints or suspicions of what one could try? Maybe there's some general results that the sequence is unbounded (unless trivial)? Or some elegant proof by contradiction?

$\endgroup$

1 Answer 1

1
$\begingroup$

If the sequence is bounded, then it must be eventually periodic.

Let your sequence be $a_n, n\ge 0$. Suppose the sequence is bounded by $N$. After some point, all numbers that will ever appear have appeared, and then to determine the next number you just have to look at the previous $N+1$ numbers, i.e. $a_{n+1} = f(a_{n-N}, a_{n-N+1}, \ldots, a_n)$ for a certain function $f:\{1,\ldots, N\}^{N+1} \to \{1,\ldots, N\}$. Now since there are only a finite number ($N^{N+1}$) of possible $(N+1)$-tuples of numbers in $\{1,\ldots, N\}$, eventually one has to recur: $(a_m, \ldots, a_{m+N}) = (a_n, \ldots, a_{n+N})$ for some $n > m$. And then we must have $a_{m+k} = a_{n+k}$ for all $k \ge 0$, i.e. the sequence is eventually periodic with period $n-m$.

EDIT: Another important fact is that if the sequence is eventually periodic, then it must be periodic. I claim that if $a_{n+k} = a_{m+k}$ for all $k \ge 0$, where $n < m$, then also $a_{n-1} = a_{m-1}$. To see this, take the least $r \ge 0$ such that $a_{m+r} = a_{m-1}$ (we know such $r$ exist, since $a_{2m-n-1} = a_{m-1}$). Then $a_{m+r+1} = r+1$, so also $a_{n+r+1} = r+1$, but then that says $a_{n-1} = a_{n+r} = a_{m+r} = a_{m-1}$.

In particular, since we know cycles can't contain $0$, and our sequence starting $1,2,3$ does contain $0$, our sequence must be unbounded.

$\endgroup$
1
  • $\begingroup$ Thanks! And if the sequence is unbounded, then of course it cannot be periodic. So now how do we tell if, for a given set of starting numbers, our sequence is bounded or unbounded? $\endgroup$
    – Lagerbaer
    Commented Dec 21, 2020 at 23:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .