Навчання / Бібліотека / Головоломки
Досяжні стани відер
відра вміщують і літрів. Обидва спочатку порожні. Дозволені лише операції: наповнити одне відро до країв із крана, повністю вилити одне відро або перелити з одного відра в інше, доки джерело не стане порожнім чи цільове відро не наповниться. Станом називаємо пару поточних об’ємів (літри у відрі на літрів, літри у відрі на літрів). Скільки різних станів, враховуючи початковий, можна отримати певною послідовністю операцій?
Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.
Підказка
Усі об’єми кратні одному спільному числу, а після кожної операції принаймні одне відро повне або порожнє.
Розв’язок
- Кожен об’єм кратний , тож мале відро містить , або літрів, а велике — , , чи , що дає кандидатів у пари.
- Після будь-якої операції одне відро повне або порожнє, тому пари (, ) і (, ) неможливі, і лишається щонайбільше пар.
- Пошук від порожньої пари показує, що кожна з решти пар досяжна, наприклад (, ) через наповнення великого відра, переливання в мале, вилиття малого й нове переливання.
- Отже, кількість досяжних станів дорівнює .
Відповідь: