На засіданні шахового клубу містер Бішоп запропонував наступну задачу.
Містер Бішоп. Як поміняти позиції чорних і білих коней за найменше число ходів?
Один з членів клубу зробив 2 перших ходу так, як показано на діаграмі. Переставити білих коней в верхні кути дошки, а чорних - в нижні він зумів за 24 ходу.
Іншому члену клубу вдалося вирішити задачу містера Бішопа за 20 ходів.
Але нікому не вдавалося вирішити задачу менш ніж за 18 ходів, поки не з'явилася Фанні Фіш.
Міс Фіш. Є ідея! Я знаю, як вирішити задачу за 16 ходів, і можу довести, що її не можна вирішити за менше число ходів.
Перш ніж приступити до пояснення, Фанні накреслила діаграму, на якій відрізками прямих зображені можливі ходи кожного коня.
Міс Фіш. Уявіть собі, що відрізки прямих - це нитки, а вісім клітин нанизані на них, як намистини, і їх можна розташувати по колу.
Міс Фіш. Кожен хід на дошці відповідає цілком певному ходу на окружності. Щоб поміняти позиції коней, їх необхідно перемістити по колу, рухаючи в одному напрямку.
Містер Бішоп. Ви абсолютно праві, Фанні. Щоб перейти на нову позицію, кожен з 4 коней повинен зробити по 4 ходи. Таким чином, завдання можна вирішити за 16 ходів, а більш економного рішення не існує.
Фанні замінила одного з білих коней червоним і задала членам шахового клубу нову задачку: як поміняти місцями білого і червоного коня за найменше число ходів?
Як, по-вашому, чому Фанні посміхалася, пропонуючи цю задачку?
Шахові коні і зірчасті фігури
Фанні вирішила шахову задачу, звівши її до изоморфной задачі, допускала просте (хоча і далеко не тривіальне!) Рішення. Поставлену Фанні завдання можна вирішити тим же методом. Поєднавши нитками клітини, зайняті кіньми, і розгорнувши вийшло «намисто» в коло, ми побачимо, що коні нанизані на нитки в наступному порядку: чорний, чорний, червоний, білий. Фанні посміхалася, так як розуміла, що переставити червоного і білого коней неможливо: вони слідують один за одним в незмінному порядку, тому що ні один кінь не може перестрибнути через іншого коня, якщо вони обидва рухаються по колу (в обидва напрямки) і обгін заборонений . Чи зрозуміло вам чому?
При русі по колу за годинниковою стрілкою білий кінь завжди слід безпосередньо за червоним. Якби білий і червоний коні могли помінятися полями, які вони займали на дошці з самого початку, то порядок проходження був би змінений на зворотний і червоний кінь рухався б по колу безпосередньо за білим. Ясно, що таке перестроювання неможливо. Дійсно, воно означало б, що один з коней (або білий, або червоний) перестрибнув через двох чорних коней. Звівши міні шахову задачу до топологічної задачі про розташування чотирьох точок на простий замкнутої кривої, ми отримали можливість досить просто довести, що рішення вихідної задачі не існує. Отримати доказ «неіснування» іншим способом було б надзвичайно важко. Спробуйте, і ви переконаєтеся в цьому самі.
Вам сподобалася завдання про перестановку шахових коней? Ось ще одна така задача, за складністю навіть перевершує обидві попередні. Розглянемо позицію на шахівниці 3? 4, зображену на рис. 5. Як і раніше, трьох чорних і трьох білих коней потрібно поміняти місцями так, щоб білі коні виявилися на верхній горизонталі, а чорні зайняли нижню горизонталь, причому виконати перестановку за найменше число ходів.
У цьому випадку, як видно на рис. 6. ізоморфний граф складніший. Цей граф являє собою діаграму, на якій показані всі можливі ходи коней, Припустивши, що вершини нашого графа - гудзики або намистини, а ребра - нитки, ми виявимо, що розгорнути його в коло, як у попередній задачі, неможливо, але наш граф з ниток і гудзиків нам вдасться укласти так, як показано на рис. 7. Числа на цьому малюнку відповідають номерам клітин на рис. 4 і 5.
Ясно, що завдання про перестановку шахових коней на цьому графі ізоморфна вихідної задачі, але вирішується незрівнянно легше. Чи вдасться вам знайти мінімальне рішення в 18 ходів?
Метод ниток і гудзиків дозволяє проаналізувати одну старовинну гру. Для неї нам знадобиться особлива «дошка» - зірчастий граф, зображений на рис. 8. і сім монет або невеликих фішок.
Гра полягає в наступному. Поклавши монету на будь-яку вершину графа, ви можете зрушити її уздовж чорної ламаної лінії (ребер графа) в будь-яку іншу вершину. Після того як хід закінчений, торкатися до монеті і переміщати її в іншу вершину забороняється.
Потім ви кладете другу монету на будь-яку незайняту вершину графа і пересуваєте її уздовж ребер в будь-яку іншу незайняту вершину. Так ви продовжуєте діяти до тих пір, поки всі сім монет не займуть своє місце на вершинах графа.
Дуже скоро ви виявите, що розставити всі сім монет вдається, якщо діяти за ретельно продуманим планом: найменша недбалість призводить до позиції, яка не дозволяє досягти в грі успіху. Чи не могли б ви вказати, яких правил слід дотримуватися при розстановці і переміщенні монет, щоб вам незмінно супроводжував успіх?
Зірчастий граф можна повністю «розкрити» подібно графам в двох перших завданнях про перестановку шахових коней, його вдається розгорнути в коло. Після того як це зроблено, сім монет неважко розташувати на окружності і проаналізувати, як вони можуть рухатися. Справитися з цим завданням можна багатьма способами. Одна з найбільш простих виграшних стратегій полягає в тому, щоб робити будь-який хід першою монетою, а все такі монети ставити і пересувати завжди так, щоб після закінчення ходу вони зайняли вершину, яку займала в початковому положенні попередня монета.
Запропонуйте зіграти в цю гру своїм друзям. Лише дуже мало хто з них зможуть розставити всі сім монет, навіть якщо ви один раз швидко продемонструєте їм, як слід грати.
Придивіться уважніше до цієї картинці. Що художник намалював неправильно?
Погляньте на меч в руці лицаря: його неможливо вкласти в піхви.
Ці два меча (якщо тільки вони не мають потовщень) можна вкласти в піхви відповідної форми. Чи можете ви придумати ще якусь форму для меча і парних йому піхов?
Всі права захищеності booksonline.com.ua