Юный техник 1958-03, страница 51

бывший депутатом в годы игорной эпидемии.

Содержатели увеселительных заведений лоежо исг.оль-?овали эту мчнию и устраивали большие игорные турниры За решение задач назначались огромные премии.

Сам изобретатель игры Са-муэль Ллойд предложил издателю нью-йоркской газеты опубликовать одну из таких задач с премией в тысячу долларов за ее правильное решение. Неисчислимое количество людей бросилось на поиски решения Штурманы из-за игры сажали на мель свои суда; машинисты проводили поезда мимо станции; фермеры ; абрасывали свои плуги.

Всеобщий ажиотаж прекратили математики. Они доказали неразрешимость ряда задач и в том числе премиальной.

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

Но всегда ли возможно, не переставляя шаики, перевести их из любого начального поло

жения в порядок возрастающих номеров? А если нет, то существует ли короткий алгоритм, позволяющий сразу определить, разрешима зецача или нет? Или это можно обнаружить, только перепробовав все комбинации? Эти вопросы заинтересова/.и ма^тематиков, занявшихся исследованием теории игры в «Пятнадцать».

Заметим прежде ecei о, что сомчи простой на первый взгляд алгоритм — это перебор всех возможных позиций для пятнадцати шашек

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

Если бы ма^тематмки не нашли более короткий алгоритм для обнаружения неразрешимых задач, еще много-много лет продолжалась бы бессмысленная погоня за премией.

Как же быстро обнаружить неразрешимость задачи? Надо, оказывается- просто вынимать шашки из коробки и менять их местами до тех пор, пока они расположатся по возрастающим номерам. Если таких перестановок окажется четное число, то задачу можно решить и путем передвижения шашек. Если же число перестановок нечетно — задача неразрешима.

51*