— Интересно, — заметил профессор, читавший курс английской литературы, — что некоторым поэтам удается написать лишь одну бессмертную строку. Все остальное в их творчестве не имеет непреходящего значения. Взять, например, Джона Уильяма Бергона.

Его поэмы настолько посредственны, что сейчас их никто не читает, а ведь именно он написал одни из самых замечательных строк в английской поэзии:

Математик, любивший надоедать своим друзьям импровизированными головоломками, задумался на минуту, затем поднял бокал и прочитал следующие стихи:

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

8. Хитроумное состязание. Три колледжа — Вашингтона, Линкольна и Рузвельта—решили провести легкоатлетический матч. В каждом из видов спорта от каждого колледжа выступал один и только один участник.

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

— Мы заняли первое место по толканию ядра, — сказала она, — но матч выиграл колледж Вашингтона. Они набрали 22 очка. Мы и колледж Рузвельта получили лишь по 9 очков.

— А как начислялись очки? — спросил отец.

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

— А по скольким видам спорта проводились соревнования?

— Честное слово, не помню, папа. Я все время смотрела толкание ядра.

— А прыжки в высоту были? — спросил брат Сьюзен.

Сьюзен кивнула.

— А кто выиграл прыжки?

Этого Сьюзен не знала.

Как ни странно, но на последний вопрос можно ответить, располагая лишь теми сведениями, которые мы уже имеем. Итак, какой колледж выиграл соревнования по прыжкам в высоту?

9. Термит и 27 кубиков. Представим себе большой куб, склеенный из 27 меньших деревянных кубиков одинакового размера (рис. 229).

Рис. 229 К задаче о термите и кубиках.

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

Может ли термит прогрызть все 26 внешних кубиков, побывав в каждом из них лишь по одному разу, и закончить свой ход в центральном кубике? Если это возможно, покажите, каким должен быть путь термита. Если же вы считаете, что это невозможно, докажите свое утверждение.

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

Ответы

1. На рис. 230 показана игра в КВБ, закончившаяся вничью. Это изящное решение, найденное Мак-Лури, очень непросто.

Рис. 230 Ничья при игре в КВБ.

Двое читателей, перебрав все возможные случаи, показали, что оно единственно с точностью до небольших вариаций в четырех клетках доски, указанных стрелками. Каждая из этих клеток может быть любого цвета, но все четыре клетки не должны быть одного и того же цвета, а поскольку каждый игрок имеет лишь восемнадцать фишек, то две из этих четырех клеток должны быть одного цвета, а две — другого. Расположены они так, что, как бы мы ни поворачивали доску, схема их размещения с точностью до цвета остается неизменной.

Доска размером 6x6 клеток — самая большая из досок, на которых возможна ничья. Это доказал в 1960 году Роберт А. Джьюитт.

Он сумел показать, что ничья невозможна на доске размером 7x7 клеток, а поскольку все большие доски содержат подквадрат из 7x7 клеток, то ничья на них также невозможна.

При игре в КВБ на доске размером 6x6 клеток всегда можно добиться ничьей. Следуя довольно простой симметричной стратегии, второй игрок всегда может свести игру вничью. Он может в ответ на каждый ход противника ставить свою фишку на поле, расположенное симметрично вертикальной или горизонтальной оси доски, или на поле, в которое переходит при повороте на 90° вокруг центра доски клетка, занятая последней фишкой противника (во втором случае может возникнуть позиция, изображенная на рис. 230). Возможна и другая стратегия: последнюю занятую противником клетку соединить с центром доски и, продолжив отрезок прямой по другую сторону от центра, занять клетку на этой прямой, отстоящую от середины доски на то же расстояние, что и клетка противника. Все стратегии применимы к любым доскам четного порядка, а поскольку на досках, порядок которых превышает 6, ничья невозможна, эти стратегии обеспечивают победу второму игроку на всех досках четного порядка, начиная с 8. Даже при игре на доске 6x6 зеркальносимметричная стратегия (когда второй игрок «отражает» ходы первого в оси, делящей доску пополам и параллельной ее краю) заведомо обеспечивает победу, поскольку единственная позиция, при которой достигается ничья, не обладает зеркальной симметрией.

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

В 1963 году была составлена программа для игры в КВБ для компьютера ИБМ-1620. Компьютер мог играть, делая первый или второй ход, на досках порядка от 4 до 10. Если он должен был делать первый ход, то выбирал клетку случайным образом. В последующих ходах придерживался зеркальносимметричнои стратегии, но если очередная клетка «достраивала» квадрат (то есть была четвертой вершиной квадрата), то производил случайный поиск свободной клетки до тех пор, пока не обнаруживал «безопасного» поля.

Для всех квадратных досок порядка п число различных квадратов, которые можно построить из четырех клеток, равно

Вывод этой формулы, а также формулы для прямоугольных досок содержится в книге Г. Лэнгмэна «Математика в играх».[72]