Магистр Игры в гостях у «Кванта»

36

Магистр Игры
в гостях
у «Кванта»

Кандидат физико-математических наук
В. Л. ГУТЕНМАХЕР

Мы пригласили в редакцию Магистра Игры*), известного специалиста по теории игры — он знает много старинных игры и придумывает новые.

— Уважаемый Магистр, расскажите нам, пожалуйста, об целях.

Магистр. Начнем с простейшей игры, которую мы будем называть.

Игра для начинающих. На столе лежат 66 бусинок. Первый игрок может взять себе от 1 до 9 бусинок, второй игрок берет от 1 до 9 бусинок из оставшихся и так далее. Выигравает тот, кто заберет последние бусинки.

Игра называна «Игрой для начинающих» — в этом есть двоякий смысл. Во-первых, игра простая и на ее примере удобно показать способы рассужdenей начинающим математикам. Во-вторых, в этой игре, если правильно играть, выигравает начинающий игрок — тот, кто ходит первым.

— Как Вы будете церать, если Вы начинаете?

Магистр. Я возьму 6 бусинок — останется 60. Как бы ни пошел противник, следующим ходом я могу сделать так, что останется 50 бусинок, затем — 40, затем 30 и так далее, пока не останется 0 бусинок. Я выиграл.

Если же начну игра не я, то выиграет противник, знающий описанный способ игры. Поэтому двум магистрам достаточно бросить монетку и

*) Магистр Игры — персонаж романа Германа Гессе «Игра в бисер» (М., «Художественная литература», 1969).

37

выяснить, кто научет игру. После этого они могут и не играть — и так ясно, кто победит.

— Что делать, если противник начал первым церру, но не знает, как правильно церть?

Магистр. Нам же известны «выигрышие позиции» — когда число бусинок, которое остается после хода, кратно 10. Вот и нужно, как только представится возможность, перейти в такую позицию.

— Как Вы разгадали секрет этой церры?

Магистр. Я начал рассуждать от конца игры, а не от ее начала. Допустим, я выиграл, то есть взял последние бусинки. Я мог это сделать только в том случае, если перед этим противник оставил на столе от 1 до 9 бусинок. Что бы заставить его сделать, я должен был оставить на столе после своего предыдущего хода 10 бусинок. Это выигрыная позиция. Точно так же следующего (на самом деле — предыдущего) выигрыная позиция — оставить 20 бусинок. Выигрышие позиции дальше периодически повторяются. Самая последняя, то есть самая первая выигрыная позиция — оставить на столе 60 бусинок. Мы знаем, что попасть в нее можно первым ходом — забрав 6 бусинок.

Как видите, мои секреты очень просты: рассуждать от конца игры и нахождение выигрыные позиции. Ну и, конечно, подмечать, как они периодически повторяют.

— Спасибо, Магистр. А не предложите ли Вы нам другие церры?

Магистр. Рассмотренную игру очень легко обобщить: давайте, считать, что в начале на столе лежит N бусинок и что каждый игрок может брать от 1 до p бусинок. При конкретных N и p мы получаем различные конкретиные игры. В частности, при p=9, N=66 — это наша игра для начинающих.

— А есть ли правила, которое годилось бы для любой такой церры?

Магистр. Да, есть. Если число N не делится на p+1, при правильной

38

ингре начнающий выиграет. Он должен сначала взять столько бусинок, чтобы оставшееся число делилось на $p+1$ (то есть взять $r$ бусинок, где $r$ — остаток от деления $N$ на $p+1$), а затем применять эту тактику и дальше.

Если же число $N$ делится на $p+1$ (скажем, $N=k (p+1)$), то выигравает игрок, который ходит вторым. Как бы ни начал его противник, он сможет все время попадать в выиграшные позиции: $(k-1)(p+1), (k-2)(p+1)$ и т. д.

— Может ли еще как-нибудь изменить «Неру для начинающих»?

Магистр. Да, например, есть игра «Побеждает чет». В этой игра два игрок тоже берут поочередно от 1 до $p$ бусинок из кучки, в котором в начале имеет нечетное число бусинок. Побеждает на этот раз тот, кто в игге, когда стол опустет, наберет четное число бусинок. Эта игра горздо интереснее — выиграть в ней значительное сложнее.

— Правда ли, что тем не менее Вы и в ней всегда выиграете?

Магистр. Если мне предоставлено право выбирать, начинаю ли я игру или ходу вторым, то я всегда выиграю. Я знаю теорему — в играх такого типа*), как эти, у одного из игроков есть выиграшная стратегия. Этот замечательный факт теории игри придал мне уверенность, и, готовясь к игре, я нашел секрет выиграша**).

Приведу по этому поводу стих моето приятель Магистра Игры Изефа Кнехта:

Ты пишешь на листе, и смысл ознакомен И закреплен блуждаями пера,
Для следующего до конца проразчен:
На правильах поконтся игра***

*) Речь идет об играх, которые специализми называют «конечные игры безничных с полной информацией». О них можно прочитать в книге Е. С. Вентцель «Элементы теории игри» (М., «Наука», 1959) или в «Кванте», 1981, № 1, с. 12.

**) Этот секрет разгадали также ребята из Малой Академии наук Крыма. «Квант» найдется вскоре вернуть к этой игре.

***) Из упомянутой книги Германа Гессе «Игра в бисер» (перевод стихов С. Аверинцева).