খারাপ প্রতিবেশী
চ্যালেঞ্জ
একটি রাস্তার ধারে এমন কিছু লোক বাস করে যারা পাশাপাশি থাকতে পারে না। যদি সেখানে ১০টি বাড়ি থাকে, তবে কত উপায়ে এই লোকদের মধ্যে কয়েকজন সেই বাড়িগুলিতে এমনভাবে থাকতে পারে যাতে কোনো দুটি প্রতিবেশী বাড়িতে এই লোকেরা না থাকে? সমস্ত বাড়ি খালি থাকাকেও একটি সম্ভাবনা হিসাবে ধরুন।
অন্বেষণ
১৫টি বাড়ি থাকলে কতগুলি উপায় আছে? এমন একটি প্যাটার্ন খুঁজুন যা আপনাকে আরও বেশি সংখ্যক বাড়ির জন্য বিভিন্ন উপায় দ্রুত গণনা করতে সাহায্য করবে।
নোট
চ্যালেঞ্জ ও অন্বেষণ
অন্যান্য অনেক ধাঁধার মতোই, এটি শেখার সেরা উপায় হলো সহজ উদাহরণ অনুশীলন করে প্যাটার্ন খুঁজে বের করা। খালি জায়গার জন্য E এবং খারাপ প্রতিবেশীর জন্য B ব্যবহার করুন।
- ১টি বাড়ি – ২টি উপায়: E অথবা B
- ২টি ঘর – ৩টি উপায়: EE, BE, EB
- ৩টি ঘর – ৫টি উপায়: EEE, BEE, EBE, EEB, BEB
- 4টি ঘর – 8টি উপায়: EEEE, BEEE, EBEE, EEBE, EEEB, BEBE, BEEB, EBEB
দেখে মনে হচ্ছে এগুলো ফিবোনাচ্চি সংখ্যা। চলুন এর একটি ভালো কারণ খুঁজে বের করি।
n টি ঘর পূরণ করার উপায় সংখ্যা বের করতে, E অথবা B দিয়ে শুরু করুন।
- যদি আপনি একটি E দিয়ে শুরু করেন, তাহলে সেই প্রথম বাড়িটিকে উপেক্ষা করে পরবর্তী n-1 টি বাড়ি পূরণ করা যেতে পারে।
- যদি আপনি B দিয়ে শুরু করেন, তাহলে পরের ঘরটি অবশ্যই E হতে হবে। এই দুটির পরে, প্রথম দুটি ঘর উপেক্ষা করে পরবর্তী n-2 টি ঘর পূরণ করা যেতে পারে।
সুতরাং, n টি ঘর পূরণ করার উপায় সংখ্যা, n-1 টি ঘর পূরণ করার উপায় সংখ্যা এবং n-2 টি ঘর পূরণ করার উপায় সংখ্যার যোগফলের সমান। ফিবোনাচ্চি সংখ্যা গণনা করার নিয়মটি হুবহু এটাই। যেহেতু আমরা ২ এবং ৩ দিয়ে শুরু করি, তাই এই নিয়মটি এরপরের বাকি সংখ্যাগুলোকেও একই হতে বাধ্য করবে।
প্রথম দশটি সংখ্যা হবে: ২, ৩, ৫, ৮, ১৩, ২১, ৩৪, ৫৫, ৮৯, ১৪৪।