O’yinchoq 3 ta qoziqdan iborat bo’lib, ulardan birida bir nechta halqalar – kattadan kichikgacha, pastdan yuqoriga bog’langan. Vazifa barcha halqalarni boshqa qoziqqa o’tkazish edi, lekin bir nechta shartlar bilan: bitta harakatda faqat bitta halqani o’tkazish mumkin, tepada har doim kichikroq diametrli halqa bo’lishi kerak, halqalarni chetga surib bo’lmaydi – faqat oraliqda. qoziq. Har qanday o’yin singari, uning afsonasi va go’zal nomi bor edi – Xanoy minorasi.

Afsonaga ko’ra, Xanoy shahrida Brahma xudosining ibodatxonasi bor. Unda uchta olmosli tayoqchali plita mavjud. Dunyo yaratilishida Brahma bir tayoqqa piramida shaklidagi 64 ta oltin diskni bog’ladi va uni Brahma minorasi deb atadi. Eng kattasi pastda yotar, keyingisi esa kichikroq va kichikroq edi. Agar siz ma’lum shartlarga rioya qilgan holda barcha disklarni boshqa tayoqqa o’tkazsangiz, ma’bad changga aylanadi va dunyo unutiladi. Va endi, aziz mutaxassislar, bir savolga e’tibor bering: agar ruhoniylar disklarni, aytaylik, soniyasiga 1 dona o’tkazsalar, qachondan keyin oxirat keladi?

Algoritm

Bu vazifa shunchaki qiziqarli o’yin emas, balki aql va fikrlash funktsiyasini sinab ko’rishdir. Uni hal qilishning bir necha yo’li mavjud, biz 5 ta halqali algoritmni ko’rib chiqamiz. Uning qoidalarini tushunganimizdan so’ng, biz uni istalgan sonli halqalarga qo’llashimiz va apokalipsis qachon kelishini aniqlashimiz mumkin. Shunday qilib, bizda uchta qoida mavjud:

• Bitta harakat – bitta qo’ng’iroq
• Ko’proq har doim kamroqdan past bo’ladi
• Disklarni bir chetga surib qo’ymang, faqat boshqa novda

https://youtube.com/watch?v=4zqIgAYYmrc%3Ffeature%3Doembed

Bizda chapdan o’ngga 3 ta tayoq bor – A, B va C. A novdasida pastdan yuqoriga 1, 2, 3, 4 va 5 halqalar mavjud. Oddiy yechim – eng past halqadan tashqari, butun piramidani o’tkazish, qo’shni novdaga:

1. 5-halqani C novdasiga o’tkazing
2. 4 — B
3. 5 – B
4. 3 – C
5. 5 — A
6. 4 – C
7. 5 – C
8. 2 — B
9. 5 – B
10. 4 — A
11. 5 — A
12. 3 – B
13. 5 – C
14. 4 — B
15. 5 – B

Bu erda biz ikkinchi novda eng katta halqaga qo’shimcha ravishda piramidaga egamiz. Keyinchalik, biz bazani – 1 ta eng uzoq novda – C ga o’tkazishimiz kerak, so’ngra 15 ta harakatda piramidaning qolgan qismini bu novdaga o’tkazamiz.

1. 1 – C
2. 5 — A
3. 4 – C
4. 5 – C
5. 3 — A
6. 5 – B
7. 4 — A
8. 5 — A
9. 2 – C
10. 5 – C
11. 4 — B
12. 5 – B
13. 3 – C
14. 5 — A
15. 4 – C
16. 5 – C

Shunday qilib, harakatlar soni X minus 1 kuchiga 2 ga teng, bu erda X – halqalar soni. Keling, tekshiramiz: 2 dan beshinchi darajaga = 32, 32 – 1 = 31 harakat! Ma’lum bo’lishicha, Brahma ibodatxonasidagi rohiblar 2 dan 64 gacha siljishlar va minus birni qilishlari kerak: 18 446 744 073 709 551 615. Agar siz bir soniyada bir harakat qilsangiz, bu 18 kvintilyon 446 kvadrillion 744 ni tashkil qiladi. trillion 73 milliard 709 million 551 ming 615 soniya yoki 584,9 milliard yil.