П. 3. Крестики-нолики на бесконечном поле

o	´	´

´
	o
o		´

o	´
	´

Ответ на задание 3. Ответы на все вопросы положительные. Слева показаны следующие позиции, в которых соответственно: 1) второй игрок форсированно выигрывает; 2) второй игрок заставляет выиграть первого игрока; 3) первый игрок заставляет выиграть второго игрока.

Теперь понятно, что после того, как новички научатся отвечать на крестик в углу, нужно начинать игру с крестика на стороне: в дереве ходов гораздо больше позиций, где первый игрок форсированно выигрывает, на ветке с первым крестиком на стороне.

	o
o	´	o
	o

	o
o	´	o

´
	´
		´

´
	´

´	´	´

´	´

o	´

o	´	o

·	·	·

Ответ на задание 4. Первый игрок ставит крестик в центр, а затем либо выигрывает следующим ходом, либо ставит симметрично тот же знак, что и второй игрок. Некоторые варианты нарисованы справа, последний из которых не доведен до конца. В безумных поддавках при правильной игре никто не выигрывает: каждому игроку гарантирована ничья.

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

Задание 5. Докажите, что в крестиках-ноликах Силвермана побеждает тот, кто выстраивает ряд из трех знаков независимо от очередности хода.

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

На компьютере есть старинная игра го-моку — крестики-нолики на ограниченном квадратном поле 19 ´ 19.

Задание 6. Выиграйте крестиками в го-моку у компьютера. Ноликами.

Обобщение крестиков-ноликов на бесконечном поле и игры Go-moku — игра Lines (линии), придуманная, как и тетрис, в России. В этой игре на поле 9 ´ 9 нужно выстраивать в один или несколько рядов 5 или более шариков одного цвета.

Обобщение игры Lines — игра Balls (шарики), в которой, в зависимости от варианта игры, нужно собирать из шариков одного цвета разные геометрические фигуры. Lines — просто один из вариантов этой игры, где фигурой является одна или больше линий из 5 или более шариков.

Морской бой

Всякая игра есть прежде всего и в первую голову свободная деятельность.

Йохан Хейзинга. Homo Ludens.

П. 1. Правила

	А	Б	В	Г	Д	Е	Ж	З	И	К
					´

У нас будут такие правила. У каждого из двух игроков есть две таблицы 10 ´ 10. Строки таблиц обозначаются цифрами, столбцы — буквами (см. рис.). Тогда каждая клетка таблицы однозначно определяется буквой и цифрой (метод координат).

Каждый игрок на одной из таблиц расставляет свой флот: один линкор — 4 клетки подряд по вертикали или по горизонтали; два крейсера — по 3 клетки; три двуклеточных эсминца и четыре одноклеточных подводных лодки. При этом корабли не должны иметь общих точек. Расположение кораблей — военная тайна игрока, однако честный игрок посылает противнику запечатанный пакет с копией расстановки своих кораблей, вскрываемый после игры (см. рис.).

Затем игроки по очереди обмениваются выстрелами. Каждый ход — выстрел по одной из клеток таблицы противника. При этом противник отвечает «мимо», если эта клетка не является частью одного из его кораблей, «попал» в противном случае, и добавляет «убил», если это была последняя неубитая клетка одного из кораблей. Если выстрел «мимо», право выстрела переходит к противнику, иначе игрок продолжает стрелять. Выигрывает тот, кто первым потопит весь флот противника (с учетом первого хода).

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

Чем может помочь математика игроку в морской бой?

Задание 1.

На доске 10 ´ 10 расположен один линкор. По скольким клеткам надо нанести удары, чтобы наверняка попасть в линкор?

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

Придумайте план из наименьшего числа выстрелов n, т.е. докажите: 1) данный план гарантирует попадание в линкор, где бы он ни находился в таблице; 2) не существует такого плана с числом выстрелов n – 1.

п. 2. Как попасть в линкор?

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

Но 100 выстрелов — это слишком много. Интуиция подсказывает, что выгодней стрелять по диагоналям, расположенным как можно дальше друг от друга, но чтобы при этом линкор не мог втиснуться между этими диагоналями. Поэтому раскрасим диагонали доски четырьмя красками, как на рисунке справа. Имеем четыре плана стрельбы: по клеткам с вертикальной штриховкой, горизонтальной, белым или серым. На доске всего 25 клеток с вертикальной штриховкой, 25 — с горизонтальной, 26 белых и 24 серых.

Все планы гарантируют попадание в линкор: где бы он ни находился, он занимает ровно одну клетку каждого цвета; поэтому, стреляя, например, по серому плану, мы не более чем за 24 выстрела попадем в линкор.

А теперь докажем, что не существует плана из 23 выстрелов. На рисунке справа расставлены 24 непересекающихся линкора. Любой план из 23 выстрелов оставит, по принципу Дирихле, один из 24 линкоров без попадания. Следовательно, 23 выстрелов недостаточно.

		®				®
			®				®
®				®				®
	®				®				®
		®				®
			®				®
®				®				®
	®				®				®
		®				®
			®				®

		®				®
			®				®
	®				®				®
®				®				®
		®				®
			®				®
	®				®				®
®				®				®
		®				®
			®				®

Можно доказать, что существует всего два разных плана стрельбы из 24 выстрелов для попадания в линкор, которые изображены ниже (еще два можно получить зеркальным отражением этих двух планов).

Задание 2.

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