Хорошая задачка

[graf]

Одна из очень красивых на мой взгляд задач c projecteuler.net (Problem 301).



Рассмотрим игру "Ним" с тремя кучами: есть три кучи, из a, b и с камней. Каждым ходом можно взять любое количество камней из одной любой кучи. Играют двое, проигрывает тот, кто не может сделать ход (к началу его хода взяты все камни). Назовем позицию (a,b,c) проигрышной, если при правильной игре тот кто начинает проигрывает.
Вопрос: сколько есть проигрышных позиций вида (n, 2n, 3n) при n <= 2^30 (2 в тридцатой степени).

Красота заключается в том, что нужно использовать несколько существенно разных идей и (главное, на мой взгляд) эта задача решается на бумажке вообще без использования компьютера за достаточно небольшое время. (В основном в задачах projecteuler комп все-таки требуется).

Кстати, если комп есть, можно пробрутфорсить n < 2^k для маленьких k и легко угадать ответ. Собственно и без компа можно брутфорсить, но сложнее. И да, я горд тем, что все сделал аналитически и сам. Правда я знал заранее, какие позиции в Ниме проигрышные (спасибо alexandret_kio, но я думаю я сам быстро догадался бы), и еще один необщеизвестный, видимо, факт о биномиальных коэффициентах. Заодно в процессе решения осознал новое его доказательство.

Comments

[burivykh.livejournal.com]

Хм, а при чём тут биномиальные коэффициенты? Вроде же мы хотим, чтобы сумма и ним-сумма n и 2n совпадали, то есть чтобы не было переносов при суммировании, то есть чтобы в n не было двух единиц подряд -- а это уже числа Фиббоначи? Или я чего-то не учёл?
Кстати, в тему об играх и ним-сумме: дубнинские записки курса Пьера Деорнуа -- http://www.mccme.ru/dubna/2009/notes/dehornoy/Notes.pdf :)
(Надо будет наконец сесть и добить вычитку их русского перевода, там совсем чуть-чуть осталось -- и будет ещё одна брошюрка. :) )

[graf-vk.livejournal.com]

Ты просто слишком умный. Я понял, что мне нужны числа, в двоичной записи которых нет двух единиц подряд, нашел их количество (как сумму биномиальных коэффициентов C_{n-i}^{i}), а про эту сумму я уже знал, что она равна соотв. числу Фибоначчи.