Ним – это игра, в которой двое участников по очереди берут камни, разложенные на несколько кучек. Каждым ходом игрок должен взять из одной кучки один или несколько камней, но хотя бы один – обязательно!

Проигрывает тот, кому камней не досталось, и кто поэтому не может сделать ход.

Мы рассмотрим наиболее популярную версию игры с тремя кучками камней.

Пусть начальная позиция описывается тройкой чисел (n1,n2,n3), где  n1,n2 и n3 - количество камней в каждой из трех кучек.

• Позиция называется выигрышной, если первый игрок, правильно выбрав стратегию, может гарантировать свою победу.
• Позиция называется проигрышной, если первый игрок при правильной игре второго всегда проигрывает.

Например, позиция (0,n,n) – проигрышная для любых n, ибо второй игрок всегда может выравнивать количество камней в двух оставшихся кучках, пока в них что-то остается. По этой же причине позиция (1,2,3) – тоже проигрышная, ибо второй игрок своим ходом всегда может создать позицию вида (0,n,n), например:

Первый игрок: (1,2,1)         Второй игрок: (1,0,1)

Первый игрок: (0,0,1)         Второй игрок: (0,0,0) – победа.

Подсчитайте, сколько существует проигрышных позиций вида (n,2n,3n), где n – натуральное число, не превышающее 10¹².

Вообразите бесконечный в оба конца ряд чаш, перенумерованных целыми числами.

В некоторых чашах лежат бобы. Разрешается делать ходы следующего вида: взять два боба из одной чаши и разложить их в две соседние. Игра заканчивается, когда сделать ход невозможно.

В примере на рисунке в две соседние чаши положили 2 и 3 боба, а остальные чаши оставили пустыми. Как видно, такую игру можно закончить за 8 ходов.

Рассмотрим последовательность целых чисел bi следующего вида:

b0 = 0, b1 = 289, b2 = 145

bi = (bi-1 + bi-2 + bi-3) mod 2013,

где x mod y означает остаток от деления x на у.

Пусть количество бобов в двух соседних чашах определяется числами b1 = 289 и b2 = 145, а остальные чаши в начальном положении пусты. В этом случае игру можно закончить за 3419100 ходов.

Подсчитайте, сколько ходов потребуется для завершения игры , если в начальном положении в чашах с номерами от 1 до 1500 лежит b1, b2, ... b1500 бобов, соответственно, а остальные чаши пусты.