Numbers game
Given a sequence of \(n\) integers \(a_1,\ldots,a_n\), we map it to \(|a_1-a_2|,\ldots,|a_{n-1}-a_n|,|a_n-a_1|\). We repeat this process again and again until all numbers become zero. For what \(n\) is this process guaranteed to stop?
Solution:
Interestingly parity (not me!) plays a central role here. It turns out all sequences terminate if and only if all \(0-1\) sequences do. Why? If all \(0-1\) sequences terminate then any integer sequence eventually becomes an all-even sequence, and it doesn't harm to divide every number by \(2\), and the process repeats. Note that the maximum number in the sequence never goes up, and goes down by half each time they are divided by \(2\), so this process clearly will not go on forever than hence must stop.
So for what \(n\) could all \(0-1\) sequences terminate? It is not hard to show that if \(k\) qualifies, then \(2k\) does too, so all powers of two qualify. Clearly an odd \(n\) does not qualify, because unless initially all numbers in the sequence are equal, the second to the last step is obtain the alternating sequence \(0,1,\ldots,0,1\), which doesn't exist for odd \(n\).
What about an even \(n\) not a power of two? Here comes the most fun part. If \(n=(2k+1)2^m\), divide the sequence into \(2k+1\) blocks, each of length \(2^m\). Let each block starts with either \((0,\ldots,0)\) or \((1,0,\ldots,0)\). With the same argument used to show that \(2k\) qualifies if \(k\) does, we can show that after a cycle a block becomes \((1,0,\ldots,0)\) if either itself or the subsequent block is \((1,0,\ldots,0)\), and \((0,\ldots,0)\) if it is identical to the subsequent block. So, its behavior is identical to \(n=2k+1\) if \((1,0,\ldots,0)\) is considered \(1\) and \((0,\ldots,0)\) is \(0\). Since an odd \(n\) does not qualify, neither does \(n=(2k+1)2^m\).
Solution:
Interestingly parity (not me!) plays a central role here. It turns out all sequences terminate if and only if all \(0-1\) sequences do. Why? If all \(0-1\) sequences terminate then any integer sequence eventually becomes an all-even sequence, and it doesn't harm to divide every number by \(2\), and the process repeats. Note that the maximum number in the sequence never goes up, and goes down by half each time they are divided by \(2\), so this process clearly will not go on forever than hence must stop.
So for what \(n\) could all \(0-1\) sequences terminate? It is not hard to show that if \(k\) qualifies, then \(2k\) does too, so all powers of two qualify. Clearly an odd \(n\) does not qualify, because unless initially all numbers in the sequence are equal, the second to the last step is obtain the alternating sequence \(0,1,\ldots,0,1\), which doesn't exist for odd \(n\).
What about an even \(n\) not a power of two? Here comes the most fun part. If \(n=(2k+1)2^m\), divide the sequence into \(2k+1\) blocks, each of length \(2^m\). Let each block starts with either \((0,\ldots,0)\) or \((1,0,\ldots,0)\). With the same argument used to show that \(2k\) qualifies if \(k\) does, we can show that after a cycle a block becomes \((1,0,\ldots,0)\) if either itself or the subsequent block is \((1,0,\ldots,0)\), and \((0,\ldots,0)\) if it is identical to the subsequent block. So, its behavior is identical to \(n=2k+1\) if \((1,0,\ldots,0)\) is considered \(1\) and \((0,\ldots,0)\) is \(0\). Since an odd \(n\) does not qualify, neither does \(n=(2k+1)2^m\).
post by Shen-Fu Tsai