Хорошая задачка
Jan. 31st, 2011 03:40 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
grafОдна из очень красивых на мой взгляд задач c projecteuler.net (Problem 301).
Рассмотрим игру "Ним" с тремя кучами: есть три кучи, из a, b и с камней. Каждым ходом можно взять любое количество камней из одной любой кучи. Играют двое, проигрывает тот, кто не может сделать ход (к началу его хода взяты все камни). Назовем позицию (a,b,c) проигрышной, если при правильной игре тот кто начинает проигрывает.
Вопрос: сколько есть проигрышных позиций вида (n, 2n, 3n) при n <= 2^30 (2 в тридцатой степени).
Красота заключается в том, что нужно использовать несколько существенно разных идей и (главное, на мой взгляд) эта задача решается на бумажке вообще без использования компьютера за достаточно небольшое время. (В основном в задачах projecteuler комп все-таки требуется).
Кстати, если комп есть, можно пробрутфорсить n < 2^k для маленьких k и легко угадать ответ. Собственно и без компа можно брутфорсить, но сложнее. И да, я горд тем, что все сделал аналитически и сам. Правда я знал заранее, какие позиции в Ниме проигрышные (спасибо![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
alexandret_kio, но я думаю я сам быстро догадался бы), и еще один необщеизвестный, видимо, факт о биномиальных коэффициентах. Заодно в процессе решения осознал новое его доказательство.
Рассмотрим игру "Ним" с тремя кучами: есть три кучи, из a, b и с камней. Каждым ходом можно взять любое количество камней из одной любой кучи. Играют двое, проигрывает тот, кто не может сделать ход (к началу его хода взяты все камни). Назовем позицию (a,b,c) проигрышной, если при правильной игре тот кто начинает проигрывает.
Вопрос: сколько есть проигрышных позиций вида (n, 2n, 3n) при n <= 2^30 (2 в тридцатой степени).
Красота заключается в том, что нужно использовать несколько существенно разных идей и (главное, на мой взгляд) эта задача решается на бумажке вообще без использования компьютера за достаточно небольшое время. (В основном в задачах projecteuler комп все-таки требуется).
Кстати, если комп есть, можно пробрутфорсить n < 2^k для маленьких k и легко угадать ответ. Собственно и без компа можно брутфорсить, но сложнее. И да, я горд тем, что все сделал аналитически и сам. Правда я знал заранее, какие позиции в Ниме проигрышные (спасибо
alexandret_kio, но я думаю я сам быстро догадался бы), и еще один необщеизвестный, видимо, факт о биномиальных коэффициентах. Заодно в процессе решения осознал новое его доказательство.
