Пионер 1987-09, страница 55
м SPC Двадцать спичек и монетаСережа с Чипом играли в увлекательную игру «Двадцать спичек и монета». Кладутся подряд 20 спичек и 21-й — монетка. Дальше играющие по очереди берут спички рассчитывая так чтобы послед ним ходом забрать монетку. Надо только соблюдать два правила: во-первых, монетку нельзя брать первым ходом, а, во-вторых, если противник взял сколько-то спичек, то следующим ходом ты не можешь взять больше, чем это удвоенное число. Например, если он взял 5 спичек, то ты не можешь взять больше 10. Сережу этой игре научил Чип и потому все время давал ему первый ход как новичку. И тем не менее каждый раз Сережа проигрывал, хотя он обычно хорошо играл в такие игры. Кое-какие секреты игры он понял: например, что невыгодно брать много спичек первым ходом, а если возьмешь больше 6, то противник берет монетку ответным ходом. Сережа брал по одной спичке, и в ответ Чип брал по одной, иногда по 2. Но выигрывал почему-то все время Чип! — А знаешь, что делает в таком случае программист? — сказал Чип после 15-го выигрыша подряд.— Если он не может понять, как работает программа с большими числами, он проверяет ее на маленьких. — Знаю, ты мне это уже говорил,— сердито буркнул Сережа — Только при чем тут программа? Это же игра, а не алгоритм. — Это алгоритмическая игра: существует алгоритм выигрыша независимо от хода противника. Но самое удивительное, что выигрывает не тот, кто первым начинает! Так что ты ни в чем не виноват: я заманил тебя в ловушку. — Как это, начинающий обязательно проигрывает? Так не может быть, у него же лишний ход. — Ты был бы прав, если бы этим лишним ходом он мог не взять ни одной спички. Тогда он поставил бы противника в свое положение. Но по правилам он обязан в каждый ход сколько-то спичек взять, и как только он это сделает, он уходит от спасительного числа Фибоначчи — 21. А до следующего числа Фибоначчи — тринадцати — ему не дотянуть, тогда противник возьмет монетку ответным ходом. — Что это еще за числа Фибоначчи? — О-о, это замечательные числа: 1, 1, 2, 3, 5, 8, 13, 21, 34... Они тянутся до бесконечности, причем каждое следующее получается сложением двух предыдущих. Они так хорошо служат программистам — хотя средневековый итальянский математик Фибоначчи вряд ли мог на это рассчитывать,— что один неизвестный компьютерный поэт прославил числа Фибоначчи в стихах. — Интересно было бы послушать,— вежливо сказал Сережа, хорошо зная, что Чипа хлебом не корми, а дай почитать свои стихи, которые он обычно приписывал неизвестным авторам. — Ты знаешь печальную историю о Карле и Кларе? — Это что, «Карл у Клары украл кораллы, а Клара у Карла украла кларнет»? — Да, это про них. Грустно, когда друзья ссорятся. Так вот, они решили помириться, и первый шаг сделала Клара. Однажды Клара подарила Ему коробку из-под мыла; Подумав, Карл послал в ответ Пустой кулек из-под конфет. Тогда смягчившаяся Клара Послала 2 воздушных шара, А Карл послал ей, подобрев, 3 новых карты масти треф. И с благодарностью от Клары Пришли 5 варежек без пары; Как символ дружбы, Карл в ответ Шлет 8 разных сандалет. Растрогавшись, послала Клара 13 труб для самовара, И, прослезившись, Карл послал 21 коленный вал.. Говорят, они стали добрыми друзьями и все время шлют друг другу подарки. И каждый из них, не желая уступить другому в щедрости прибавляет к своему последнему числу подарков последнее число подарков, полученных от друга. Так и получаются числа Фибоначчи. — Замечательное стихотворение, Чип, но я все-таки не понимаю, как ты меня обыгрывал с помощью этих чисел Фибоначчи. — Предположим для начала, что у нас 2 спички и монетка. Тогда начинающий проигрывает, согласен? Он не может сразу взять монетку, и ему приходится брать 1 спичку, после чего противник одним ходом берет оставшуюся спичку вместе с монеткой. Вот мы и нашли первое спасительное число 3. Если ты оставил противнику это число, он проиграл. — Ага. а если было 4 предмета— 3 спички и монетка, то можно убрать 1 спичку, и противник проиграет,— подхватил Сережа,— ведь он не сможет взять больше двух спичек. — Правильно, значит 4 не спасительное число, если я дам его противнику, он может выиграть. Идем дальше: если начинать с 5, то первым ходом можно взять только одну спичку, иначе противник сможет ответным ходом дотянуться до монетки. Но если ты возьмешь 1 спичку, то ты тоже проиграешь, потому что противник может, взяв 1, оставить тебе проигрышную позицию, которую мы только что разобрали. — Значит, 5 — спасительное число. Действительно, получаются числа Фибоначчи, но пока я не уловил общего правила— как надо играть, чтобы всегда выигрывать, даже если ты дал противнику спасительное число Фибоначчи. Например, против- ANS В Н М |
