17.1. Ханойськi башти (рекурсія)

1. Нехай {i₀, i₁, i₂} — множина номерів стержнів. У тексті умови задачі це {1, 2, 3}. Для того, щоб перемістити оптимальним чином верхні n дисків зі стержня i₂ на стержень i₀, потрібно послідовно:

   • перемістити оптимальним чином верхні (n – 1) диск зі стержня i₂ на стержень i₁;
   • перемістити n-ий диск зі стержня i₂ на стержень i₀;
   • перемістити оптимальним чином верхні (n – 1) диск зі стержня i₁ на стержень i₀.

2. Позначивши через a_n шукану кількість переміщень за оптимальним планом, маємо таке рекурентне задання послідовності {a_n}:

   a₁ = 1,     a_{n + 1} = 2a_n + 1.

   Методом математичної індукції можна довести, що a_n = 2ⁿ – 1.

17.2. Трикутники (геометрія + оптимізований перебір переста­новок)

1. Два трикутники можливо склеїти в один тоді й лише тоді, коли:

   • трикутники мають по одному внутрішньому куту з загальною сумою π, тобто з протилежними косинусами;

   • до цих внутрішніх кутів у трикутниках прилягають сторони однієї довжини.

2. Три трикутники можливо склеїти в один тоді й лише тоді, коли їх можна склеїти так, щоб:

   • два з них можна склеїти в один, який можна склеїти з іншим трикутником;

   • вони мали спільну вершину, що є внутрішньою точкою результату склеювання.

3. Чотири трикутники можна склеїти в один, якщо справджується одне з таких висловлювань:

   • дані трикутники можна послідовно по одному склеювати у трикутники;

   • дані трикутники можна розбити на пари, які можна склеювати у трикутники, які у свою чергу також можна склеїти;

   • серед даних чотирьох трикутників можна вибрати такий, до сторін якого можна доклеїти решту трикутників таким чином, щоб вершини вибраного трикутника належали сторонам результату склеювання;

   • спільна вершина трьох трикутників є внутрішньою точкою результату їхнього склеювання, який можна склеїти з четвертим трикутником;

   • два трикутники можна склеїти в один, який має спільну вершину з рештою трикутників, яка є внутрішньою точкою результату склеювання всіх чотирьох початкових трикутників;

   • серед даних чотирьох трикутників можна вибрати такий, до сторін якого можна доклеїти решту трикутників таким чином, щоб вершини вибраного трикутника лежали всередині результату склеювання;

   • серед даних чотирьох трикутників можна вибрати три такі, що їх можна склеїти в опуклий чотирикутник, внутрішня точка сторони якого є спільною вершиною цих трьох трикутників. Доклеювання четвертого трикутника до отриманого чотирикутника дає трикутник.

Зауважимо: всі перестановки 2-, 3- чи 4-елементної множин, які потрібно використати, щоб перевірити всі варіанти можливого склеювання, можна задати сталими масивами, а не обчислювати.