টাওয়ার্স অফ হ্যানয়, অব্যাহত

যখন তিনটি ডিস্কের জন্য টাওয়ার্স অফ হ্যানয় সমাধান করা লাগবে, তখন একদম নিচের ডিস্কটি অর্থাৎ ডিস্ক 3 টি সামনে নিয়ে আসা লাগবে, যেন ডিস্ক 3 টি লাঠি A থেকে সরিয়ে লাঠি B তে নিয়ে আসা যায়। ডিস্ক 3 টি সামনে নিয়ে আসার জন্য আমাদের প্রথমেই 1 এবং 2 ডিস্ক দুইটিকে সরিয়ে অতিরিক্ত যে লাঠিটি রয়েছে অর্থাৎ লাঠি C তে সরিয়ে নিয়ে যেতে হবে:

Wait a minute—it looks like two disks moved in one step, violating the first rule. But they did not move in one step. You agreed that you can move disks 1 and 2 from any peg to any peg, using three steps. The situation above represents what you have after three steps. (Move disk 1 from peg A to peg B; move disk 2 from peg A to peg C; move disk 1 from peg B to peg C.)

এখানে আরও বলা যায়, ডিস্ক 1 এবং 2 কে লাঠি A থেকে লাঠি C তে সরানোর মাধ্যমে ছোট একটি সমস্যার সমাধানও আমরা করে ফেলেছি: ডিস্ক 1 কে লাঠি A থেকে লাঠি C তে সরিয়ে নেওয়া হল $n-1$‍ ধাপের মাধ্যমে (এখানে মনে রাখা দরকার যে $n=3$‍)। আমরা যদি এই ছোট সমস্যাটি সমাধান করতে পারি তাহলে, আমরা ডিস্ক 3 টি লাঠি A থেকে লাঠি B তে সরিয়ে নিতে পারবো:

এখন সবশেষে আমাদের ডিস্ক 1 কে $n-1$‍ ধাপে লাঠি C থেকে লাঠি B তে নিয়ে আসার ছোট সমস্যাটি সমাধান করতে হবে। আবার আমরা এখানে একমত হচ্ছি যে আমরা এই কাজটি তিনটি ধাপে এই কাজটি সম্পন্ন করতে পারবো। (ডিস্ক 1 কে লাঠি C থেকে সরিয়ে লাঠি A তে নিয়ে আসতে হবে; ডিস্ক 2 কে লাঠি C থেকে সরিয়ে লাঠি B তে নিয়ে আসতে হবে; এরপরে ডিস্ক 1 কে লাঠি A থেকে লাঠি B তে সরিয়ে নিয়ে আসতে হবে।) আর তাহলেই আমাদের কাজ শেষ হয়ে যাবে:

আর—আমরা সকলেই জানি, এই প্রশ্নটি আমাদের কাছে আসছে যে—ডিস্ক 1 থেকে ডিস্ক 3 পর্যন্ত সরানোর ক্ষেত্রে কোন বিশেষ লাঠি আছে কিনা? আমরা এই ডিস্কগুলো যেকোনো লাঠি যেকোনো থেকে যেকোনো লাঠিতে সরিয়ে নিতে পারি। উদাহরণস্বরূপ, লাঠি B থেকে লাঠি C তে:

আমরা 1 থেকে 3 পর্যন্ত থাকা ডিস্কগুলো যেকোন লাঠি থেকে যেকোন লাঠিতে সরিয়ে নিতে পারি, ডিস্কগুলো সাতবার সরানোর মাধ্যমে। এখানে লক্ষ্য করলে তুমি দেখবে যে প্রতিটি ডিস্ক তিনবার করে পৌনঃপুনিকতা ব্যবহার করার মাধ্যমে সর্বমোট দুইবার ডিস্কগুলো সরানোর মাধ্যমে ডিস্ক 1 এবং ডিস্ক 2 সরানোর ছোট সমস্যাটি সমাধান করতে পারছ, আর এর সাথে আরও একটি ধাপ যুক্ত হবে ডিস্ক 3 সরানোর জন্য।

তাহলে যখন $n=4$‍ হবে তখন কি হবে? 1 থেকে 3 পর্যন্ত থাকা ডিস্কগুলো যেকোনো লাঠি থেকে যেকোনো লাঠিতে বার বার সরানোর মাধ্যমে আমরা যেহেতু এই সমস্যাটি সমাধান করতে পারব, তাহলে $n=4$‍:

এই সমাধানে ডিস্কগুলো আমরা 15 বার (7 + 1 + 7) সরিয়েছি এবং আমরা 1 থেকে 4 পর্যন্ত থাকা ডিস্কগুলো যেকোন লাঠি থেকে যেকোন লাঠিতে সরিয়ে নিতে পারি।

এই পর্যায়ে এসে আমরা এখানে দুইটি প্যাটার্ন লক্ষ্য করছি। প্রথমেই পৌনঃপুনিকতা ব্যবহার করে আমরা টাওয়ার্স অফ হ্যানয় সমস্যার সমাধান করতে পারি। যদি $n=1$‍ হয়, তাহলে আমাদের শুধুমাত্র ডিস্ক 1 টি সরাতে হবে। অন্যথায়, যখন $n\ge 2$‍ হবে, তখন আমরা সমস্যাটি তিনটি ধাপে সমাধান করতে পারি:

Second, solving a problem for $n$‍ disks requires $2^n-1$‍ moves. We've seen that it's true for:

If you can solve a problem for $n-1$‍ disks in $2^{n-1}-1$‍ moves, then you can solve a problem for $n$‍ disks in $2^n-1$‍ moves. You need:

If you add up the moves, you get $2^n-1$‍.

Back to the monks. They're using $n=64$‍ disks, and so they will need to move a disk $2^{64}-1$‍ times. These monks are nimble and strong. They can move one disk every second, night and day.

How long is $2^{64}-1$‍ seconds? Using the rough estimate of 365.25 days per year, that comes to 584,542,046,090.6263 years. That's 584+ billion years. The sun has only about another five to seven billion years left before it goes all supernova on us. So, yes, the world will end, but no matter how tenacious the monks may be, it will happen long before they can get all 64 disks onto peg B.

বিশ্বের সমাপ্তির সময় অনুমান করা ছাড়া এই অ্যাপ্লিকেশনটি আমরা আর কি কি কাজে ব্যবহার করতে পারি? উইকিপিডিয়ার তালিকা কয়েকটি মজাদার অ্যাপ্লিকেশন।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।