Читать книгу «Інформатика. Дитяча енциклопедія» онлайн.

Розв’язання задачі. Ця задача спочатку здається нерозв’язною. Але ніхто не каже в умові, що два мандрівники знаходяться на одному березі річки. Тому відповідь на запитання така: «Припустимо, два мандрівники підійшли одночасно до річки з різних боків. Спочатку переправився один, потім інший».

Виконавець «Чернець»

Існує давня індійська легенда, згідно якої в місті Бенаресі під маківкою головного храму, в тому місці, де знаходиться центр Землі, на бронзовому майданчику стоять три діамантових стрижні. У день створення світу на один із стрижнів були напнути 64 кільця. Бог доручив ченцям перенести кільця з одного стрижня на другий, використовуючи третій як допоміжний. Ченці мали виконувати дві умови:

1. Переносити за один раз тільки одне кільце.

2. Кільце можна переносити з одного стрижня на інший, тільки якщо воно має менший діаметр, ніж верхнє кільце, або стрижень вільний.

Згідно з легендою, якщо, виконуючи всі умови, ченці перенесуть всі 64 кільця, настане кінець світу (розрахунки математиків стверджують, що знадобиться 584 мільярдів років).

Надамо алгоритм розв’язання задачі для 3 кілець (стрижні 1, 2, 3):

1. 1 кільце перекласти 1–3.

2. 2 кільце перекласти 1–2.

3. 1 кільце перекласти 3–2.

4. 3 кільце перекласти 1–3.

5. 1 кільце перекласти 2–1.

6. 2 кільце перекласти 2–3.

7. 1 кільце перекласти 1–3.

Мінімальна кількість перекладань для 3 кілець дорівнює 7. Якщо кількість кілець 4, то перекладань – 15.

Розв’язуючи задачу перекладання кілець, треба пам’ятати, що коли кількість кілець парна, то треба починати перекладання зі стрижня 2, якщо кількість кілець непарна, то треба починати перекладання зі стрижня 3.

Виконавець «Переливашка»

Умова задачі переливання в загальному вигляді: Є три жбани різних ємностей. Більший з них доверху наповнено водою. Треба, не користуючись ніякими іншими жбанами, крім даних, поділити воду навпіл (зробити поділ треба за мінімальну кількість кроків).

Варіант 1. Уряд стоять три склянки, повні води, і три порожні. Як зробити так, щоб повні та порожні склянки чергувалися, якщо можна брати в руки тільки одну склянку?

Розв’язання:

Воду з другої склянки треба перелити в п’ятий стакан.

Варіант 2. Як за допомогою двох жбанів на три та п’ять літрів відлити один літр води?

Розв’язання:

1. Наповнити трилітровий жбан водою.

2. Перелити воду в п’ятилітровий жбан.

3. Наповнити трилітровий жбан.

4. Із трилітрового жбана долити води доверху в п’ятилітровий.

Таким чином, у трилітровому жбані залишиться 1 літр води.

Варіант 3. Є пісочні годинники на три та сім хвилин. Треба опустити яйце в окріп рівно на чотири хвилини. Як це зробити?

Розв’язання: