Головоломка «Ханойська вежа», в загальному, не потребує представлення.
Є три стержня: A, B і C. На стрижень A надіті 8 кілець (дисків), нагорі найменше, кожне наступне більше попереднього, а внизу найбільше. Два інших стрижня порожні. Необхідно перенести всі кільця зі стрижня A на стрижень C, користуючись стрижнем B як допоміжним. В результаті кільця на стрижні C повинні бути в тому ж порядку, в якому вони початково перебували на стрижні A. Брати за один хід кілька кілець можна. Крім того, ніколи не можна класти більше кільце поверх меншого.
Це класична версія головоломки. Наша ж задача відрізняється від класики всього однією деталлю:
Забороняється переносити кільця між стрижнями A і C безпосередньо. За один хід перенести кільце можна тільки або з A на B (або назад з B на A), або з B на C (або назад).
Скільки ходів потрібно для перенесення вежі з 8 кілець з A на C?
Підказка 1
Порахуйте ходи для невеликого числа кілець - спочатку одного, потім двох і трьох.
Підказка 2
Нехай у вежі k кілець. Скільки ходів потрібно зробити перед тим, як вдасться зрушити зі свого місця саме нижнє кільце на стрижень B? А скільки потім ходів потрібно буде зробити перед тим, як його вдасться зрушити з B на C?
Почнемо з позначень. Нехай H (k) - найменше число ходів, за яке вдається вирішити нашу задачу для перенесення k кілець. Якщо ви скористалися порадою з першої підказки, то вже знаєте, що H (1) = 2, H (2) = 8, а можливо, зуміли акуратно порахувати і H (3) = 26.
А тепер давайте відповімо на питання, задані в підказці 2. Перед перенесенням нижнього (k -го) кільця з нього потрібно зняти всю верхню частину вежі з (k - 1) кільця. Для цього нам буде потрібно H (k - 1) ходів, і ніяк не менше. В результаті всі ці кільця виявляться на стрижні C, що і дасть можливість перенести нижнє кільце з A на B (за 1 хід). Після цього, на жаль, доведеться все раніше зроблену повторити в зворотну сторону: щоб звільнити для нижнього кільця стрижень C, ми повинні з нього всю верхню частину вежі прибрати на стрижень A. Це вимагає ще H (k - 1) ходів. Потім (за 1 хід) переносимо нижнє кільце з B на C, і ще раз повторюємо H (k - 1) хід для того, щоб зібрати верхню частину на стержні C заново. Разом нам було потрібно три рази по H (k - 1) і ще два окремих ходу. Чи могли ми отримати результат швидше? Ні. А повільніше? Як це не дивно - теж немає, хіба що ми б в якийсь момент повернули назад той хід, який зробили тільки що.
Який проміжний підсумок у нас вийшов? А ось який:
Такі співвідношення, в яких наступний член послідовності лінійно (тобто за допомогою лінійної функції) виражений через попередній (один або кілька), називаються лінійними рекуррентамі. Найпростіший приклад - спосіб завдання арифметичної прогресії: ak + 1 = ak + d. Трохи складніший (але теж дуже відомий) приклад - числа Фібоначчі: fk + 2 = fk + 1 + fk.
Що робити далі? Адже не застосовувати ж загальні формули - це як стрільба з гармат по горобцях.
Для восьми кілець можна просто порахувати відповідь «в лоб» послідовними обчисленнями з поступовим зниженням рекуррентной формулою. Він виявиться рівним 6560. Однак є спосіб красивіше.
Додамо до H одиничку: H '(k) = H (k) + 1. Тоді для H' (k) справедлива така формула:
Отже, H '(k) - геометрична прогресія зі знаменником 3. Так як при цьому H' (1) = 2 + 1 = 3, то H '(k) = 3 k. звідки
Післямова
Зверніть увагу, що у відповіді виходить формула, дуже схожа на формулу для числа ходів в класичній головоломці про Ханойські вежі, тільки у нас замість 2 варто 3. Це не випадково - і причини цієї невипадковість будуть пояснені трохи нижче.
Ще одна чудова наслідок з отриманого нами результату полягає в тому, що в процесі перекладання кілець зустрінуться всі допустимі розташування кілець на трьох стрижнях, так би мовити, «всі позиції». Чому це можна стверджувати? Тому, що загальне число позицій дорівнює 3 k (щоб задати позицію, ми для кожного з k кілець повинні вибрати той з трьох стрижнів, на якому воно в цій позиції знаходиться - а порядок кілець на стрижні жорстко заданий їх розмірами), і з тієї простої причини, що ніяка позиція не зустрічається в процесі перекладання двічі (інакше процес можна було б скоротити). А оскільки ми змушені робити саме (3 k - 1) ходів, щоразу отримуючи неповторним позиції, то все позиції будуть отримані.
А тепер - невеликий екскурс в історію.
В одному з храмів індійського міста Бенареса встановлена бронзова плита з трьома алмазними стрижнями. При створенні світу верховний індуїстський бог Брахма помістив на перший стрижень 64 диска з чистого золота, в порядку зменшення їх розмірів, і велів ченцям перемістити їх на третій стрижень, заборонивши при цьому за один раз переносити більше одного диска і поміщати більший диск на менший. З тих пір ченці день і ніч, змінюючи один одного, працюють над цим завданням. Як тільки завдання буде вирішено, храм розсиплеться на порох і завершиться життя Брахми. Потім народиться новий Брахма, і все повториться.
Щоб самому вирішити головоломку, зовсім не потрібно купувати її в магазині або завантажувати комп'ютерну версію з Інтернету. Для маленьких дітей ідеально підійде набір дитячих формочок:
Втім, за допомогою дорослих головоломку можна виготовити і з найнесподіваніших «деталей»:
Втім, повернемося до математичної частини завдання. У ній було показано, що шлях від вихідного (всі кільця зібрані на лівому стрижні) до кінцевого (всі кільця зібрані на правому з трьох стрижнів) стану проходить абсолютно через все допустимі позиції. Нам залишилося тільки осмислити, як саме це відбувається. Для цього давайте покажемо всі можливі позиції гри у вигляді графа:
На рис. 4 показані графи H1 -H4 веж з числом кілець від 1 до 4. Ходи по сторонам найменших трикутничків відповідають переносу самого маленького кільця, ходи між такими трикутниками (але всередині трикутника наступного розміру) - перенесення наступного кільця, і т. Д. Це в стандартної головоломці, коли всі перенесення дозволені. А що виходить в нашій версії, коли між стрижнями A і С нічого переносити не можна?
Картинка із зображенням графа, який виходить з H3. приведена на рис. 5:
Спробуємо зрозуміти, чому граф «обрізається» саме так, як показано на цій картинці. Для цього «укрупнити» зображення точок на вихідному графі і помістимо на них інформацію про те, яким розташуванню кілець відповідає дана точка (рис. 6):
Тут «cbb», наприклад, означає, що найменше кільце знаходиться на стрижні C, а обидва інших - на стрижні B. При цьому можна або перенести маленьке кільце (в стандартному графі - на будь-який з стрижнів A або B, тобто отримати abb або bbb), або перенести наступне кільце на вільний стрижень (тобто отримати cab). У нашій версії переноси з A на C і з C на A заборонені, так що рівно один з цих трьох ходів виявляється неможливим, - а це означає, що кожна позиція, крім першої та останньої, має рівно дві сусідніх. Тим самим весь шлях по графу виявляється однією довгою ламаною лінією без всяких відгалужень. Власне, саме про це і була наша задача.
Цікаво, що побудований нами шлях по графу (точніше, його літерна запис виду aaa - baa -. - ccc) зустрічається в дуже багатьох серйозних математичних (і не тільки математичних) дослідженнях і носить спеціальну назву - код Грея. Головна особливість кодів Грея полягає в тому, що сусідні значення в послідовності «кодових слів» відрізняються тільки в одному розряді.
Основне призначення кодів Грея в наш час - захист інформації від перешкод і помилок при передачі по каналах зв'язку. Використовують коди і розробники електронних пристроїв. Наприклад, в статті про графічних планшетах розказано, як це робилося в 1960-і роки в графічних пристроях фірми RAND. Забавно, що винахідником графічного планшета вважають Елішу Грея - а «батько» коду Френк Грей, судячи з усього, навіть не родич Еліша, а всього лише однофамілець.
Втім, у цих кодів є і більш кумедні застосування. Уявіть собі, що ви намагаєтеся підібрати ключ до кодовому замку (наприклад, на вокзальної камери схову або на ремені, яким ви минулого літа прив'язали свій велосипед до стінки сараю; рис. 7). Якщо перебирати всі коди по порядку, то в процесі перебору нерідко доведеться крутити замок занадто довго. Наприклад, для переходу від 999 до 1000 потрібно обертати всі чотири розрядних коліщатка.
Однак якщо ви користуєтеся для підбору «секрету» кодом Грея (тільки не двійковим, який описаний в статті Вікіпедії за посиланням, і не потрійним, який вище побудували ми, а десятковим!), То перебір в режимі «один маленький поворот в секунду» займе у вас рівно стільки часу, скільки всього є кодів, тому що кожен наступний код буде виходити з попереднього рівно одним поворотом. Те естьвсего 9999 секунд. Це, звичайно, все одно близько трьох годин, але все-таки не так довго, як при стандартному переборі.
До речі, про час. Якщо в класичній легенді Люка про вежі Брахми і «кінець світу» настання кінця світу очікується після (2 64 - 1) ходів, то в нашій версії головоломки монахам б знадобилося (3 64 - 1) ходів. Спробуйте подумки припустити, у скільки разів це більше. Хоча б по одному величини - в 100? У 1000 ° У 10 000? Я впевнений, що правильний порядок не вгадає майже ніхто. Наша відповідь більше класичного більш ніж в 10 11 разів.
І раз ми вже торкнулися теми часу, не можу не згадати в цьому зв'язку чудовий розповідь Еріка Френка Рассела «Гра на виживання». У ньому жорстокі інопланетяни-гомбарійци прирікають головного героя-землянина на страту, але їх звичай дозволяє йому перед стратою зіграти в будь-яку настільну гру. Результат поєдинку нічого не вирішує, але поки гра не закінчиться, бранець буде жити. Як ви думаєте, яку гру вибирає герой?