Задача о перестановки кружков


Задача


Эта задача впервые была опубликована в разделе "Математические развлечения" в журнале Scientific American. Эта маленькая задача на самом деле очень трудная для решения.


Имеется 5 кружков, 3 черных и 2 белых, последовательность расположения которых чередуется через одного, как показано на этом рисунке.



Начальное расположение кружков


А нужно эти кружки расположить так, чтобы сначала были вместе 3 черных, а затем вместе 2 белых, как показано на рисунке ниже. Причем, нужно определить, за какое минимальное количество перемещений можно перейти от расположения кружков на верхнем рисунке к расположению на нижнем рисунке.



Конечное расположение кружков


При этом условия перемещения кружков следующие:

  • За один раз можно перемещать только 2 кружка одновременно. Причем, можно перемещать только такие 2 кружка, которые соприкасаются друг с другом и имеют два разных цвета.
  • При этом порядок следования цветов перемещенных кружков должен сохраниться таким же, каким был этот порядок первоначальным. И оба перемещенных кружка должны по прежнему соприкасаться друг с другом.
  • Перемещать эти два кружка можно на любое свободное место на линии, в том числе и на некоторое расстояние от других кружков. Под свободным местом на линии понимается такое место, где могут поместиться, минимум, два кружка.
  • В процессе таких перемещений могут образовываться разрывы в цепи кружков с пустыми местами, но, после окончания всей процедуры перемещений, никаких разрывов остаться не должно. Все 5 кружков снова должны соприкасаться друг с другом, как на картинке.
  • Номера кружков (их первоначальный порядок) не имеют значения. В окончательном построении порядок следования номеров кружков может быть любым.


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



Решение задачи


Всего требуется 4 перемещения:

  1. Кружки 3 и 4 перемещаем направо. Но между кружками 5 и 3 оставляем место для двух кружков.
  2. Кружки 1 и 2 перемещаем направо за 4-й кружок так, чтобы между кружками с номерами 1 и 4 не оставалось пустого места.
  3. Кружки 4 и 1 перемещаем в просвет для двух кружков между кружками 5 и 3. (Этот просвет образовался на первом перемещении.)
  4. Кружки 5 и 4 перемещаем в просвет для двух кружков между кружками 3 и 2. (Это тот самый просвет, откуда на 4-м перемещении забрали кружки 4 и 1.)



Этапы перемещения кружков


Если не подглядывать в эту картинку, то решение этой задачи найти очень непросто.



Легкий вариант задачи


У этой задачи есть более легкий вариант. Всё то же самое, только дополнительно можно перемещать еще и два кружка одного и того же цвета.


Подсказка: Это можно сделать всего за 3 перемещения. Попробуйте найти эти три перемещения.



------------------

Автор статьи: Евгений Миронов.


---------------

Вы дочитали статью до конца? Если да, то Вы молодец!
Эта статья может Вам ещё пригодиться (или весь этот сайт).
Быстро и удобно можно сохранить ссылку на эту статью через эти кнопочки социальных сетей.

Сохрани ссылку на эту статью в своей любимой социальной сети!

Комментарии к этой заметке больше не принимаются.




август 2015
пн вт ср чт пт сб вс
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31