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, но я думаю я сам быстро догадался бы), и еще один необщеизвестный, видимо, факт о биномиальных коэффициентах. Заодно в процессе решения осознал новое его доказательство.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

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:42 am
Powered by Dreamwidth Studios