graf: (Default)
[personal profile] 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] alexandret_kio, но я думаю я сам быстро догадался бы), и еще один необщеизвестный, видимо, факт о биномиальных коэффициентах. Заодно в процессе решения осознал новое его доказательство.

Date: 2011-01-31 05:16 pm (UTC)
From: [identity profile] endagorion.livejournal.com
Да, симпатично. Простенько и со вкусом. =)

Date: 2011-01-31 06:00 pm (UTC)
From: [identity profile] burivykh.livejournal.com
Хм, а при чём тут биномиальные коэффициенты? Вроде же мы хотим, чтобы сумма и ним-сумма n и 2n совпадали, то есть чтобы не было переносов при суммировании, то есть чтобы в n не было двух единиц подряд -- а это уже числа Фиббоначи? Или я чего-то не учёл?
Кстати, в тему об играх и ним-сумме: дубнинские записки курса Пьера Деорнуа -- http://www.mccme.ru/dubna/2009/notes/dehornoy/Notes.pdf :)
(Надо будет наконец сесть и добить вычитку их русского перевода, там совсем чуть-чуть осталось -- и будет ещё одна брошюрка. :) )

Date: 2011-01-31 06:03 pm (UTC)
From: [identity profile] graf-vk.livejournal.com
Ты просто слишком умный. Я понял, что мне нужны числа, в двоичной записи которых нет двух единиц подряд, нашел их количество (как сумму биномиальных коэффициентов C_{n-i}^{i}), а про эту сумму я уже знал, что она равна соотв. числу Фибоначчи.

Profile

graf: (Default)
graf

April 2011

S M T W T F S
     1 2
3456789
10111213141516
17181920212223
24252627282930

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 24th, 2017 08:48 am
Powered by Dreamwidth Studios