Игра «Определитель»

27

В. Переяславский

Игра
«Определенель»

Два варианта одной игры
В 1978 году «Квант», рассказывая о IX празднике юных математиков в Батуми (см. № 10), предложил своим читателем придумать выигрышную стратегию для следующего игры:

Играот двое. Они по очереди выcisвалиот в таблицу 3×3 числа от 1 до 9 (каждое число должно быть использовано). Коеда таблица заполнена, подсчитывают две суммы: сумму $S_1$ произведений по стольцам и сумму $S_2$ произведений по строкам. Если $S_1 > S_2$, выцрывает начинающий церру; если $S_1 < S_2$, выцрывает второй церрок.

В 1971 году эта игра в несколько другой форме была популярина среди студентов механико-математического факультета МГУ (а узнали они о ней от студентов Пермского университета). Назывался эта игра «Определенель» и выглядела так:

Итерают двое. Они по очереди выcisвалиот в таблицу 3×3 числа от 1 до 9 (каждое число должно быть использовано). Коеда таблица заполнена, подсчитывают две суммы: сумму $S_1$ произведений по стольцам и сумму $S_2$ произведений по строкам. Если $S_1 > S_2$, выцрывает начинающий церру; если $S_1 < S_2$, выцрывает второй церрок.

Тут, конечно, мы должны обязывать вам, что определенелем таблицы $T$ (рис. 1) называется число
$$d = x_1 x_5 x_9 + x_2 x_6 x_7 + x_3 x_4 x_8 - x_3 x_5 x_7 - x_1 x_6 x_8 - x_2 x_4 x_9.$$
В том, что эти две игры по существу совпадают, мы предлагаем вам убедиться самостояльно. Дальше мы будем рассматривать варинт, предложенный в «Кванте».

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

$$T = \begin{bmatrix} x_1 & x_2 & x_3 \\ x_4 & x_5 & x_6 \\ x_7 & x_8 & x_9 \end{bmatrix}$$

Рис. 1.

28

несложные выигрышение стратегии, сложные — все остальные. Повидимому, игра «Определитель» является сложной. Сложность — непреемное условие популяристии игры. Например, в шахматы и в крестики-nоликки на беконечном листе клетчатой бумаги все играют с увлечением, а в крестики-nоликки на доске «3×3» — разве что младшие школьники.

Решим задачу, которая поможет нам играть в «Определитель»: найдем наименьшее значения применим к теме ее слагаемым неравенство о среднем арифметической и среднем геометрической («Квант», 1980, № 3, с. 23):

$$\frac{x_1 x_2 x_3 + x_4 x_5 x_6 + x_7 x_8 x_9}{3} \geq \sqrt[3]{x_1 x_2 \cdot \dots \cdot x_9} = \sqrt[3]{9!} = \sqrt[3]{70 \cdot 72^2} > 71.$$

Отсюда $S > 213$ и, поскольку $S$ — целое число, $S \geq 214$. Но $2 \cdot 5 \cdot 7 + 1 \cdot 8 \cdot 9 + 3 \cdot 4 \cdot 6 = 70 + 72 + 72 = 214$; значит, искомое наименьшее значение равно 214.

Для нахождения наименьшего значения нашей суммы воспользоваться следующей леммой (доказателье!) : если числа $a, b, c, d$ положительные, $ab = cd$ и $|a - b| > |c - d|$, то $a + b > c + d$.

Образуем новую сумму $S'$ так: последнее слагаемое $x_7 x_8 x_9$ оставим без изменения, первое слагаемое $x'_1 x'_2 x'_3$ составим из трех самых маленьких чисел множества $\{x_1, x_2, \dots, x_6\}$, а второе слагаемое $x'_4 x'_5 x'_6$ — из остальных чисел этого множества. Тогда по лемме $S \leq S'$, причем знак равенства будет лишь в том случае, когда каждое из чисел $x_1, x_2, x_3$ больше (или меньше) каждой из чисел $x_4, x_5, x_6$. Отсюда получаем, что значение суммы $S$ будет наименьшим, если все компоненты первого слагаемого меньше всех компонентов второго слагаемого, а те в свою очередь меньше всех компонентов третього слагаемого. Таким образом, искомое наименьшее равно $1 \cdot 2 \cdot 3 + 4 \cdot 5 \cdot 6 + 7 \cdot 8 \cdot 9 = 6 + 120 + 504 = 630$.

Подведем итог: сумма $S$ принимает наименьшее значение, когда ее слагаемые максимально близки (и равны, следовательно, примерно 71), наиболее значение — когда они максимально различны. Отсюда практический совет играющему: стремясь к тому, чтобы слагаемые противника были примерно одинаковы (и равны 71), а собственные слагаемые — максимально различны!

Стратегия «71» для первого игрока

Допустим, что после вашего первого хода противник написал свое число в одном столбце или в одной строке с вашим числом. Тогда мы предлагаем вам следующее стратегию «71»:

Определим для каждой заполненной строки и каждой заполненного столбца таблицы число

$$m = \begin{cases} \frac{\Pi}{71}, \text{ если } \Pi \geq 72, \\ 71/\Pi, \text{ если } \Pi \leq 71, \end{cases}$$

где $\Pi$ — произведение чисел, написанных в данной строке или данном столбце.

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

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

Рис. 2.

29

в котором на соответствующем ходе вписано данное число. Убедимся, что в партии $3_55_81_24_66_47_72_98_19_3$ начинающий игру пользовался стратегей «71» (на первый ход стратегия ограниченной не накладывает).

После первых двух ходов (рис. 3, а) первый игрок по стратегии должен поставить в клетку № 2 число, дающее максимальное возможное m. В данном случае максимум m может быть либо ход 1$_2$, при котором произведение чисел второго столбца равно 15, либо ход 9$_2$, дающий произведение 135. Так как 71/15 > 135/71, в клетку № 2 нужно поставить 1, что и было сделано.

После хода 4$_6$ (рис. 3,6) в клетку № 4 нужно поставить число, дающее минимум m, а именно 6$_4$, и т. д.

Два частных случая

1. Если у цераюцезо есть произведение $1 \times 2 \times 3$, или $1 \times 2 \times 4$, или $6 \times 8 \times 9$, или $7 \times 8 \times 9$, то он выйрывает независяimo от того, как в таблице расположены остальные числа.

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

$$\frac{x_2x_5x_8+x_3x_6x_9}{2} \geq \sqrt{x_2x_5x_8x_3x_6x_9} = \sqrt{3 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9} > 212.$$

Значит, $S_1 \geq 1 \cdot 2 \cdot 4 + 425 = 433$.

С другой стороны, значение суммы $S_2$ максимально, когда числа $x_2$ и $x_3$ меньше, чем $x_5$ и $x_6$, а $x_5$ и $x_6$ меньше, чем $x_8$ и $x_9$. Таким образом, $S_2 \leq 1 \cdot 3 \cdot 5 + 2 \cdot 6 \cdot 7 + 4 \cdot 8 \cdot 9 = 387$, то есть $S_1 > S_2$, что и утверждалось.

2. Иного при игре удается использовать идею «цугшанга» — отсутствия разумных ходов у противника. Например, в ситуации, изобранной на рисунке 5, начинающий при любом ходе второго игрока может (и должен) поставить числа 1, 2 в один столбец, а 8, 9 — в другой. Просчитав разные варианты, легко проверить, что это обеспечит начинанное ему выигрыш.

Попытка перебор

На первый взгладигra «Определитель» кажется не очень сложной: соперники делают всего девять ходов и для каждой хода есть не более девяты вариантов — просчитаем все варианты и выберем нужный. Беда в том, что различных партий черезчур много.

В самом деле, для первого хода есть 81 варианта (одно из девяты чисел в одну из девяты клеток); для второго хода — 64 варианта и т. д. (рис. 6) — всего $9^2 \cdot 8^2 \cdot 7^2 \cdot \ldots 2^2 \cdot 1^2 = (9!)^2 \approx 1,3 \cdot 10^{11}$ различных партий. Разумеется, определить результат игры таким перебором невозможно даже с помощью ЭВМ.

Правда, этот перебор слишком «груб», а оценка слишком завышена: ведь наша игра имеет симметрию. Например, все первые ходы в разных клетки одним и тем же числом равноправны; поэтому нужно рассматривать не 81, а только 9 вариантов первого хода. Восемь осталось для второго хода клеток можно разделить на три класса так, что ходы одним и тем же числом в клетки одного класса будут равноправны (на рисунке 7 клетки разных классов закрашены в разных цвета); поэтому нужно рассматривать не 64, а 8 \cdot 3 = 24 варианта второго хода. Так нам удалось сизить верхнюю оценку числа партий до числа $9 \cdot 24 \cdot 7^2 \cdot 6^2 \cdot \ldots \cdot 2^2 \cdot 1^2 \approx$

30

≈ 5 · 10^9, которое, однako, по-прежнему очень велико. Нужна новая идея, сокращаюшая перебор вариантов. Такая идея нашлась.

Чем может помочь мудрец?

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

Мудрец все партии начинает одинаково; мы же должны попробовать игру с ним все 24 варианта второго хода. В каждой позиции второго хода мудрец однозначно делает третьий ход; мы же перебираем все 36 вариантов четверого хода и т. д. (рис. 8). Всего нужно сыграть 24 · 6^2 · 4^2 · 2^2 = 55296 партий, проверяющих мудреца.

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

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