Две игры со спичками

4

ДВЕ ИГРЫ СО СПИЧКАМИ

И. М. Яглом

В этой статье мы рассакjem вам об играх «ним»
и «изяньшизцы». И «ним» и «изяньшизцы»—китайские народные игры; «изяньшизцы» в переводе означает «выбирание камней» (разумется, замена в условиях игр камней спичками ничего не меняет в ее существе). В последствии эти игры проникли в Европу; одно время игра «ним» была популярна в За-падной Европе.

5

Приведем правила этих игра.

Игра «ним»
На столе лежам три кучки спичек. Двое цераюцих поочередно берут спички из этих кучек, причем за один раз цераюцый может взять любое число спичек из одной (обязательно только из одной!) кучки. Выдержим сцитаемся том, кто заберет последнюю спику.

Игра «изяньшизцы»
На столе лежам две кучки спичек. Двое цераюцих поочередно берут спички из этих кучек, причем за один раз цераюцый может взять любое число спичек из одной кучки, либо поровну (но может любое число!) спичек из обеих кучек. Выдержим сцитаемся том, кто заберет последнюю спику.

Задача состоит в том, чтобы определить, при каких начальных положениях (то есть колчествах спичек в каждой из кучек) начинающий может выиграть, а при каких нет, и указать метод правильно (беспроигрышной) церы.

Пraktические играть в ним или изяньшизцы очень удобно у классной доски — без всяких спичек, но с мелом и трипкой в руке. На доске можно нарисовать, скажем, три ряда полей, оканичивающихся у правого края доски, и три шашки — по одной в каждой ряду полей (рис. 1). Каждый играющий в свой ход страет одну из шашек и «перевиграет» ее на любое число полей вправо (здесь речь идет об игре ним); выиграшим считается тот, кто сделает последний ход. Так же можно играть и изяньшизцы — только теперь доска для игры содержит два ряда

Рис. 1.

Рис. 2.

7

К сожалению, и здесь не видно никакого определенного закона составления этой таблицы.

А нельзя ли таблицы I и II записать по другому?

Нам не удалось понять, как составлены таблицы I и II, образованные в первом случае темя, а во втором — двумя строкками чисел. Подумаем теперь над возможными причинами постигшей нас неудачи.

Мы уже говорили о том, что таблицы I и II — это числовые таблицы; они образованы рядом чисел. Фигурирующие в этих таблицах числа мы, естественно, записывали обычным образом, используя общеприятную десятичную систему числения; так, например, составляющие последний столбец таблицы II числа 24 и 39 ознакомют: «2 десята и 4 единиц» и «3 десята и 9 единиц». Однако сама по себе десятичная система числения, произхождение которого связано с тем случайным остоятельством, что человек имеет на руках 10 пальцев, никак не связана с рассматриваемыми нами играми; поэтому уменьшной представляется попытка записать наши таблицы по-другому.

Дальнейшее содержание этой статьи связано со статьей «Системы числения» («Квант» № 6). Нам потребуется следующее следующее из этой статьи.

Систем записных положительных чисел с помощью небольшего числа символов (цифр) можно предложить много. Позиционные системы числения (точнее было бы сказать — позиционные системы записи чисел) строятся следующим образом. Задается неокоторый базис, или система ключевых чисел, представляющий собой бесконечную возможность последовательность целых чисел:

$$1 = q_0 < q_1 < q_2 < q_3 \dots$$

После этого каждое число $N$ представляет в виде суммы чисел нашего базиса, взятых с теми или иными целыми коэффициентами:

$$N = a_m q_m + a_{m-1} q_{m-1} + \dots + a_2 q_2 + a_1 q_1 + a_0 q_0;$$

это выражение записывается так:

$$N = a_m a_{m-1} \dots a_2 a_1 a_0,$$

где $a_m, a_{m-1}, \dots$ — «цифры» записи числа $N$.

Например, если система базисных чисел такова:

$$1, 2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$$

то число 27 записывается следующим образом:

$$27 = 1 \cdot 23 + 0 \cdot 19 + 0 \cdot 17 + 0 \cdot 13 + 0 \cdot 11 + 0 \cdot 7 + 0 \cdot 5 + 1 \cdot 3 + 0 \cdot 2 + 1 \cdot 1 = \text{«1000000101»}.$$

При этом $k$-я цифра $a_k$ в записи любого числа $N$ в системе числения с базисом (*) всегда будет меньше относительной $q_k + 1/q_k$.

Если базис системы числения имеет вид:

$$1 = q^0, q = q^1, q^2, q^3, q^4, \dots,$$

где $q$ — неокоторое целое число, то система числения называется «q-цифрой», в ней все числа представляются суммами степени числа $q$ и все цифры в записи числа $N$ меньше $q$ (меньше 10 в случае общеприятной десятичной системе числения).

8

Самой простой из всех систем записи цельх чисел является двойная система числения, в которой все числа представляют суммами степеней числа 2. Если использовать эту систему численения, то наши таблицы I и II примут совсем другой вид (числа в двойной системе численными будем записьать красными цифрами):

Таблица Ia

| №№ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| a | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 10 | 0 | 11 | 10 | 1 | 0 | 0 | 1 |
| b | 1 | 10 | 10 | 11 | 100 | 100 | 101 | 100 | 110 | 100 | 101 | 110 | 111 | 1000 | 1000 |
| c | 1 | 10 | 11 | 11 | 100 | 101 | 101 | 110 | 110 | 111 | 111 | 111 | 111 | 1000 | 1001 |

Таблица IIa

| №№ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— |
| a | 1 | 11 | 100 | 110 | 1000 | 1001 | 1011 | 1011 |
| b | 10 | 101 | 111 | 1010 | 1101 | 1111 | 1111 | 1010 |

| №№ | 110 | 1000 | 10001 | 10011 | 10101 | 1101 | 1111 | 10101 | 1010 | 1010 | 1010 | 1010 | 1010 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| 1110 | 10000 | 10001 | 10011 | 10101 | 1101 | 1111 | 1011 | 1011 | 1011 | 1011 | 1011 | 1011 | 1011 |

**Внимательное изучение таблицы Ia позволяет усмотреть в ней вполне определению закономерности: да, конечно, произрывные позиции (a, b, c) в церем «ним» — это.me позиции, еде сумма цифр какдоео разряда в двойной записи чисел a, b, с цемна (то есть равна 0 или 2)! Оdnako таблица IIa оказывается болеековарной: она ничем не лучше таблицы II, и никакой определенной закономерности составления проигрывных пар (a, b) из нее усмотреть нельзя.

Но почему именно двойная система числения должна быть нам ключ к отысканию системы беспроигрывной игры в цяньшизцы? Правда, мы видели, что эта система помогает как будто при разработке теории игры nim: но ведь цяньшизцы — это совсем другая игра, а ключ, открывающий одну дверь, совсем не обязаан подходить к другой. Нельзя ли переписать таблицу II по-иному: может быть, другая система записи образу-

ющих эту систему чисел проблет больше света на ее строение?

Внимательное изучение таблицы II позволяет подметить, что в ней часто фигурирует числа Фибоначчи и см., например, 1-й, 2-й, 5-й и 13-й столбцы таблицы *). А это в свою очередь может навести нас на мысль о целесообразности попытки записать таблицу II в «фибоначченной системе числения», в котором все числа представляют суммами чисел последовательности Фибоначчи (числа в этой системе числения мы будем записать синими цифрами). Например, число 100 в Fibоначчи

*) Числа Fibоначчи — последовательность чисел, начинающая с 1 и 2 и далее строящая по следующему закону: какдое число последовательности Fibоначчи равно сумме двух предыдуших. Первые ее члены таковы: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, … Числам Fibоначчи посвящена хорощая брошюра Н. Н. Воробьева «Числа Fibоначчи» (М., «Нayka», 3-е изд., 1969).

10

лированным выше условиям a) и 6)) в церем «ним» является.me и только не позиции (a, b, c), для которых суммы всех цфр, отвецоцих одному разряду в записи чисел a, b, с в двойной системе счисления, для всех разрядов цемны.

Теорема II. Процедыными в церем «изяныццы» являются.me и только не позиции (a, b), для которых а, будучи записанным в фибоначчевой системе счисления, кончается цемным числом нулей, а число b получается из числа а приписываем еще одно нулей в конце.

Затем ие. Из теорем I и II следует, что обе игры — «ним» и «изяныццы» — в определенном смысле выгоды для начинающего: проигрывших для начинающего позицией (см. таблицы I и II) в них довольно мало, то есть они встречаются гораздо реже, чем все остальные (выигрывные для начинающего) позиции.

Доказательства этих теорем составляют содержание приводных ниже упражнения. Ответы к ним даны на стр. 60 (попробуйте, однako, найти решения самостояльно). Советум вам сначала разобраться с упражнениями 1—4, так как упражнения 5—7 гораздо сложнее.

Упражнения

1. Докажите, что если позиция (a, b, c) в игре «ним» не является проигрывной, то есть не удовлетворяет указанным в формулировке теоремы I условиям, то играющий своим ходом может сделать ее проигрывной.

2. Докажите, что если позиция (a, b, c) в игре «ним» не является проигрывной, то есть не удовлетворяет указанным в формулировке теоремы I условиям, то играющий以其 ходом может сделать ее проигрывной.

3. Укажите правильная игре в игре «ним» в том случае, если число кучек спичек есть любое наперед заданное число число n ≥ 2 (прочее правильная игре мы оставляем прежним). К чему свидетельства беспроигрывной игре в случае n = 2?

4. Опишите проигрывные позиции (a, b, c) в игре «ним», записывая числа a, b, c не в двойной, а в четверчной системе счисления (то есть представляя, скажем, число a в виде a = aₙaₙ₋₁…a₂a₁a₀ = aₙ4ⁿ + aₙ₋₁4ⁿ⁻¹ + … + a₂4² + a₁4 + a₀; здесь 0 ≤ aᵢ ≤ 3 для всех i = n, n − 1,…, 2, 1, 0 *))

5. Докажите, что для любого целого положительного числа p существует одна и только одна проигрывная позиция (a, b) в игре «изяныццы» (то есть позиция, удовлетворяющая условиям теоремы II) такая, что b − a = p. Проверьте это для первых 15 проигрывных позиций, перечисленных в таблице II.

6. Докажите, что если позиция (b, a) в игре «изяныццы» не удовлетворяет условиям теоремы II, то играющий своим ходом может либо сразу выиграть, либо вести позицию к проигрывной.

7. Докажите, что если позиция (a, b) в игре «изяныццы» является проигрывной, то после любого хода играющего она перестает быть таковой.

8. Укажите правильная игре в церем «изяныццы», если число кучек нечетно (играющий каждым своим ходом имеет право взять любое число спичек из каждой-то одной кучки, либо поровну — и тоже любое число! — из всех кучек).

Проблема. Укажите правильная игре в церем «изяныццы», если число кучек равно четырем.

Хочу предупредить читателя, что решение поставленной проблемы автору неизвестно.

*) Черта над числом ознакомает, что это запись числа цифрами aₙaₙ₋₁…a₂a₁a₀, а не произведение чисел.