К вопросу со звёздочкой: давайте я немного поговорю про игру "ним".

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

Игра на одной кучке тривиальна; игра на двух кучках решается симметричной стратегией — если в кучках одинаковое число камней, выигрывает второй игрок, а иначе начинающий (берущий столько, чтобы в кучках стало поровну). А что будет для игры с тремя кучками камней?

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

Игра же на трёх кучках превращается уже в трёхмерную таблицу или доску. Давайте ограничим число камней в кучках — пусть в каждой кучке их меньше N.

Вопрос: как выглядит множество проигрышных клеток внутри куба NxNxN? Скажем, если этот куб затем сжать в N раз, чтобы он стал единичным, после чего клетки станут этакими "пикселями" (ну, или "вокселями", потому что они трёхмерные).

Если вы никогда этого не делали — попробуйте разобраться, что происходит для N=8. Игру можно разбирать "по слоям": сначала раскрасить доску 8x8, отвечающую позициям (i,j,k) с k=0. Собственно, тут это уже разобранный случай двух кучек.
Потом — с k=1 (учтя возможность хода "вниз"). Потом с k=2,3,... . И ответ сам по себе начнёт "проявляться"!

Математические байки

Математические байки

У него есть естественный аналог: тетраэдр Серпинского. - Начинаем с правильного тетраэдра X_0 с вершинами A_1, A_2, A_3, A_4; - а дальше на каждом шаге заменяем имеющуюся фигуру X_n на объединение X_{n+1} её образов T_1(X_n), T_2(X_n), T_3(X_n), T_4(X_n)…

К вопросу со звёздочкой: давайте я немного поговорю про игру "ним".

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

Игра на одной кучке тривиальна; игра на двух кучках решается симметричной стратегией — если в кучках одинаковое число камней, выигрывает второй игрок, а иначе начинающий (берущий столько, чтобы в кучках стало поровну). А что будет для игры с тремя кучками камней?

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

Игра же на трёх кучках превращается уже в трёхмерную таблицу или доску. Давайте ограничим число камней в кучках — пусть в каждой кучке их меньше N.

Вопрос: как выглядит множество проигрышных клеток внутри куба NxNxN? Скажем, если этот куб затем сжать в N раз, чтобы он стал единичным, после чего клетки станут этакими "пикселями" (ну, или "вокселями", потому что они трёхмерные).

Если вы никогда этого не делали — попробуйте разобраться, что происходит для N=8. Игру можно разбирать "по слоям": сначала раскрасить доску 8x8, отвечающую позициям (i,j,k) с k=0. Собственно, тут это уже разобранный случай двух кучек.
Потом — с k=1 (учтя возможность хода "вниз"). Потом с k=2,3,... . И ответ сам по себе начнёт "проявляться"!

hottg.com/mathtabletalks/4361

2.6K viewsVictor Kleptsyn, Nov 23, 2023 at 08:40