Математические игры и головоломки — страница 7

  • Просмотров 5145
  • Скачиваний 600
  • Размер файла 1019
    Кб

запрещены такие переходы, при которых нарушаются те или другие законы сохранения. Есть такой закон и в игре «15». Чтобы объяснить его, мысленно заполним пустое место фишкой с номером 16. Тогда каждый ход — сдвиг фишки — будет состоять в том, что эта фишка меняется местами с фишкой 16. Операцию, при которой какие-то две фишки (не обязательно соседние!) меняются местами, так и назовем — обменом; математический термин для таких операций

— транспозиция. Очевидно, что из любой расстановки 16 фишек можно не более чем за 15 обменов получить правильную позицию — обозначим ее S0 — и вообще любую другую расстановку. При этих обменах не запрещается вынимать фишки из коробки. Например, можно сначала поставить на свое место фишку 1, обменяв ее с той фишкой, которая это место занимает, затем точно так же поставить на место фишку 2 и т. д. Последними мы обменяем фишки 15 и 16 — при

этом сразу обе встанут правильно. Конечно, не исключено, что по ходу дела какие-то фишки автоматически попадут на свои места, и их трогать не придется, при этом число обменов окажется меньше 15. Можно расставлять фишки по этой же системе, но в другом порядке, скажем 16, 15, 14, .... или совсем иначе, и тогда число обменов может оказаться другим. Однако, каким бы способом ни выбрать последовательность обменов, превращающую одну заданную

расстановку фишек в другую, четность числа обменов в этой последовательности всегда будет одной и той же. Это очень важное и неочевидное докажем ниже. Оно позволяет дать следующее определение: расстановка называется четной, если ее можно превратить в правильную позицию с помощью четного числа обменов, и нечетной в противном случае. В математике обычно говорят не «расстановка», а «перестановка»; к этому мы еще вернемся. Сама

правильная расстановка S0 всегда четная, а ловушка Лойда L нечетная. Но почему они не переводятся друг в друга? Как выше уже сказано, каждый ход в игре «15» можно рассматривать как обмен фишки с одной из соседних. Следовательно, при каждом ходе четность расстановки 16 фишек меняется: если до хода расстановку можно было упорядочить за N обменов, то после него — за N+1 обменов (взяв этот ход назад), а числа N и N+1 — разной четности. В обеих

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