And game ( или nk game ) — это обобщение комбинаторной игры крестики-нолики на более высокие измерения. [1] [2] [3] Это игра, в которую играют 2 игрока на гиперкубе . [1] [2] [4] [5] Если один игрок создает строку длиной n своего символа (X или O), он выигрывает игру. Однако, если все n d мест заполнены, игра завершается вничью. [4] Крестики-нолики — это игра, в которой n равно 3, а d равно 2 (3, 2). [4] Qubic — это игра (4, 3) . [4] Игры ( n > 0, 0) или (1, 1) тривиально выигрываются первым игроком, поскольку имеется только одно пространство ( n 0 = 1 и 1 1 = 1 ). Игра с d = 1 и n > 1 не может быть выиграна, если оба игрока играют хорошо, поскольку фигура противника заблокирует одномерную линию. [5]
Учитывая ширину доски для игры в крестики-нолики, каково наименьшее измерение, при котором X гарантирует выигрышную стратегию?
Игра является симметричной комбинаторной игрой .
В игре имеется общее количество выигрышных линий . [2] [6]
Для любой ширины n в некотором измерении d (благодаря теореме Хейлса-Джеветта ) всегда будет существовать выигрышная стратегия для игрока X. Никогда не будет выигрышной стратегии для игрока O из-за аргумента о краже стратегии, поскольку n d игра симметрична .
