Математична теорія головоломок
Стаття написана Павлом Чайкою, головним редактором журналу «Пізнавайка». З 2013 року з моменту заснування журналу Павло Чайка присвятив себе популяризації науки в Україні та світі. Основна мета як журналу, так і цієї статті – пояснити складні наукові теми простою та доступною мовою.
Запитайте будь-якого поважаючого себе шахіста, хто такий Самуель Лойд. Він вам із задоволенням відповість, що був такий автор витончених шахових задач, багато з яких визнані класичними. І все. А між тим шахи займали в житті Лойда дуже невелике місце. Кажуть, коли цікавилися його професією, він зізнавався: майстер головоломок. З його творінь найбільший успіх випав на долю нехитрої на вигляд гри, відомої під назвою «15».
«Старожили Миру Розваг, – згадує Лойд у своїй популярній «Енциклопедії головоломок», – пам’ятають, як на початку сімдесятих років я звів весь світ з розуму маленькою коробочкою з рухомими квадратиками».
Поширеність гри багато в чому пояснювалася тим, що вона доступна кожному. Чи складно склеїти коробку і розкреслити її дно на 16 осередків? У 15 з них укладаються пронумеровані від 1 до 15 квадратики, а один осередок залишається порожнім. Суть гри: розмістивши квадратики абияк, пересувати їх, не виймаючи з коробки, поки вони розташуються по порядку номерів.
«Божевілля швидко перекинулося в Англію і Європу, – продовжує Лойд. – Мені розповідали смішні історії про торговців, поглинених забавою настільки, що забували відкривати крамниці; про священика, який цілу ніч стояв під вуличним ліхтарем, пересуваючи квадратики».
Спочатку думали, що необхідну вихідну розстановку можна отримати при будь-якому початковому розташуванні квадратиків. Але потім з’явилися математичні дослідження, в яких доводилося, що чимало розташувань не можна привести в потрібний порядок. Після цього інтерес до головоломки помітно знизився. І все-таки вона до сих пір не забута.
Цікаво, що фахівці з обчислювальної техніки знайшли в цій головоломці застосування в якості своєрідної моделі лічильно-вирішального пристрою паралельної дії. Розроблена навіть детальна математична теорія її. Однак вона може бути застосована лише для головоломок, у яких всі осередки квадратні. А тим часом успіх лойдівської гри породив масу наслідувань. У продаж випускалися десятки подібних головоломок: з квадратними осередками неоднакового розміру, з осередками з квадратів і прямокутників. Ось одна з таких видозмін.
Для такого роду головоломок теорія поки не створена. І тому знайти, чи може одна розстановка виходити з іншої, а якщо так, то яке мінімальне число пересувань, можливо лише методом проб і помилок.
Наприклад, таке завдання: перемістити квадрат 1 з кута А в кут В. В кут Б його перемістити неважко. Треба рухати пластинки в такій послідовності – 5, 4, 1, 2, 3, 4 (вниз і вправо), I, 6, 7, 8, 9, 5, 4, 1, 6, 7, 8, 9, 4 (вліво і вниз), 8, 7, 6, 2, 3, I. Це найбільш коротке рішення, воно вимагає лише 25 пересувань (поворот навколо кута теж вважається перерозподілом).
Щоб перемістити квадрат 1 з кута А в кут Г, потрібно 29 пересувань. Перші 19 – ті ж, що в першому випадку, потім 1, 3, 2, 6, 7, 8, 9, 4, 5, 1. Складніше йде справа з переміщенням цього квадрата в кут В. Найкоротше з відомих рішень складається з 55 пересувань. Якщо хочете, спробуйте відшукати його. До речі, не доведено, що це – мінімальне число переносів для даної задачі; може бути, ви знайдете більш економне рішення.
Напевно, у декого виникли сумніви: чи так вже потрібна теорія головоломок такого роду. Дуже потрібна. Наприклад, фізикам, що займаються теорією напівпровідників, доводиться мати справу з електронами, які переміщуються туди, де є порожні місця – «дірки» – розриви в електронній хмарі навколо атома. Стане в нагоді ця теорія, можливо, і космонавтам. Уявіть склад обладнання на міжпланетній станції. Місця там небагато, і тому чим щільніше воно забите, тим краще. Але тим важче діставати зі сховища потрібні предмети. Як розмістити їх, щоб без праці витягти те, що знадобиться? Тут-то і надасть допомогу теорія «неквадратних» головоломок.