Problem 334
Spilling the beans
In Plato’s heaven, there exist an infinite number of bowls in a straight line.
Each bowl either contains some or none of a finite number of beans.
A child plays a game, which allows only one kind of move: removing two beans from any bowl, and putting one in each of the two adjacent bowls.
The game ends when each bowl contains either one or no beans.
For example, consider two adjacent bowls containing 2 and 3 beans respectively, all other bowls being empty. The following eight moves will finish the game:
You are given the following sequences:
$t_0=123456.$
$t_i=\frac{t_{i-1}}{2}$, if $t_{i-1}$ is even
$t_i=\lfloor \frac{t_{i-1}}{2} \rfloor \oplus 926252$, if $t_{i-1}$ is odd
where $\lfloor x \rfloor$ is the floor function
and $\oplus$ is the bitwise XOR operator.
$b_i=(t_i \text{ mod } 2^11) + 1.$
The first two terms of the last sequence are b1 = 289 and b2 = 145.
If we start with b1 and b2 beans in two adjacent bowls, 3419100 moves would be required to finish the game.
Consider now 1500 adjacent bowls containing b1, b2,…, b1500 beans respectively, all other bowls being empty. Find how many moves it takes before the game ends.
放豆子
在柏拉图的天堂，有无穷只碗排成一条直线。
每个碗中或者有有限颗豆子，或者没有豆子。
有一个小孩在玩游戏，游戏只允许一种操作：从任意一个碗中取出两颗豆子，然后在其相邻的两个碗中各放一颗。
当每个碗中要么只有一颗豆子要么没有豆子时，游戏结束。
例如，考虑相邻的两个碗中分别装有2颗和3颗豆子，其它的碗中都没有豆子的情况。如下八次操作之后游戏结束：
已知以下序列：
$t_0=123456.$
$t_i=\frac{t_{i-1}}{2}$，如果$t_{i-1}$为偶数。
$t_i=\lfloor \frac{t_{i-1}}{2} \rfloor \oplus 926252$，如果$t_{i-1}$为奇数。
其中$\lfloor x \rfloor$是下取整函数
而$\oplus$是按位异或运算符
$b_i=(t_i \text{ mod } 2^11) + 1.$
上述最后一个序列的前两项分别是b1 = 289和b2 = 145。
如果我们从相邻的两个碗中分别装有b1和b2颗豆子开始，结束游戏需要3419100次操作。
现在考虑相邻的1500个碗中分别装有b1、b2、……、b1500颗豆子，其它的碗中都没有豆子的情况。求结束游戏需要多少次操作。