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

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

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

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

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

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

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

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

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

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

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

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

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

51*

Обсуждение
Понравилось?
Войдите чтобы оставить комментарий
Понравилось?