Задача 334: Пролитие фасоли
В небесах Платона существует бесконечное количество чаш в прямой линии. Каждая чаша либо содержит некоторое, либо ни одно из конечного количества бобов. Ребенок играет в игру, которая допускает только один вид движения: удаление двух бобов из любой чаши и помещение одного в каждую из двух соседних чаш. Игра заканчивается, когда каждая чаша содержит либо одну, либо никакую фасоль.
Например, рассмотрите две соседние чаши, содержащие 2 и 3 бобов, соответственно, все остальные чаши пусты. Следующие восемь ходов завершат игру:
Вам заданы следующие последовательности: t0 = 123456.
ti = ti-12 , if ti-1 is even ti-12 926252, if ti-1 is odd where ⌊x⌋ is the floor function and is the bitwise XOR operator. bi = ( ti mod 211) + 1. Первые два члена последней последовательности: b1 = 289 и b2 = 145. Если мы начнем с b1 и b2 beans в двух соседних чашках, для завершения игры потребуется 3419100 ходов.
Рассмотрим теперь 1500 соседних чаш, содержащих b1, b2, ..., b1500 бобов, соответственно, все остальные чаши пусты. Найдите, сколько ходов требуется до окончания игры.