এটি কিছুদিন আগের ঘটনা। গেছিলাম এক স্কুলে। গিয়ে দেখি দোতলায় এক বিশাল অডিটোরিয়াম। ১০০ টা বাতি আছে ওখানে। কিন্তু বাতির সুইচগুলো সেখানে নাই! মানে কী?
হেড স্যার জানালেন- ঠিকাদার ভুল করে ১০০টা বাতির সুইচ নিচতলায় সিঁড়ির ঘরে লাগিয়ে দিয়েছে।
ভাবলাম ওখানে নিশ্চয়ই নম্বর ট্যাগ লাগানো। কিন্তু নিচে গিয়ে দেখলাম কোন সুইচে কোন নম্বর লাগানো নাই।
– হায় হায়। আপনার কেমন করে কম সংখ্যক নির্দিষ্ট বাতি জ্বালান?
আমরা সব সময় সব জ্বালায় রাখি!!!
তো, অনুষ্ঠান করতে করতে আমি ভাবছিলাম কীভাবে, কতো কম কষ্টে সুইচগুলোকে বাতি অনুসারে লেবেলিং করা যায়?
প্রথম উপায় হচ্ছে। বাতিগুলোকে ১ থেকে ১০০ পর্যন্ত মার্কিং করা। তারপর নিচে গিয়ে ১টা সুইচ জ্বালানো। ওপরে এসে দেখা কত নম্বর জ্বলে। তখন নিচে গিয়ে সেটাতে ঐ নম্বর দেওয়া। তারপর আর একটা সুইচ অন করে আবার ওপরে যাওয়া। এভাবে ৯৯ বারে সব সুইচকে লেবেলিং করা হবে।
প্রশ্ন হচ্ছে – সবচেয়ে কম কতো বার দৌড়াদৌড়ি করে সব সুইচকে লেবেলিং করা যাবে?
…
…
…
ভাবনা শেষ হলে মিলিয়ে নিতে পারেন
এই সমস্যাটা বা এই ধরণের সমস্যা সমাধানের সহজ উপায় হচ্ছে একটি চিন্তা করা। কোন প্যাটার্ন খোঁজার চেষ্টা করা। আমাদের স্কুল-কলেজের সিলেবাসে একটি গুরুত্বপূর্ণ বিষয় নাই। সেটি হলো বিভিন্ন কেস ধরে আগানো। গণিত অলিম্পিয়াডের পোলাপানদের নাম্বার থিউরি করাতে গিয়ে আমরা এটা টের পেয়েছি। আর একটা দূর্বলতা হলো সমাধান যাচাই না করে “উত্তরমালা” দেখা পদ্ধতি। দুটোই আসলে আমাদের ছেলেমেয়েদের গণিতের ভিত্তি দুর্বল করে দেয়। যাচাই করার পদ্ধতি যদি ছোটবেলা থেকে শেখানো হতো তাহলে জার ইকবাল স্যারের নিউরনে অনুরণনের সমাধান বই যেমন লোকে খুঁজতো না তেমনি গণিত অলিম্পিয়াডের প্রশ্নের সমাধানেরও খোঁজ পড়তো না।
যাকগে সেসব কথা। আমরা বরং এই সমস্যার সমাধান করার চেষ্টা করি। ধরি আমাদের একটা মাত্র বাতি আর একটা মাত্র সুইচ থাকতো তাহলে আমাদের কোন সমস্যাই থাকতো না।
যদি দুইটা বাতি আর দুইটা সুইচ হতো? তাহলে তাহলেও একবারে আমরা সমাধান পেতাম। নিচে একটা সুইচ অন করে উপরে এসে দেখতাম কোন বাতিটা জ্বলে। যে সুইচটা আমি জ্বালিয়ে এসেছি সেটাই এই বাতির। অন্যটি অন্য বাতির।
এখন আমরা বাতির সংখ্যা বাড়াই। এখন আমরা বাতিগুলোকে A, B, C, D এভাবে নামকরণ করি আর সুইচগুলোকে 1,2,3,4…. এভাবে নাম্বার দেই।
ধরা যাক আমাদের বাতি আছে তিনটা (A, B, C)। তাহলে প্রথমে 1 নং সুইচ অন করে ওপরে যাবো এবং ১ নং সুইচের বাতিকে চিহ্নিত করবো। তাহলে আমাদের বাকী থাকবে দুইটা। আর দুইটা তো আমরা জানি। তার মানে তিনটে বাতির সুইচকে চিহ্নিত করতে আমাদের ২ বার ওঠানামা করতে হবে।
এবার আমরা চারটে বাতি নিয়ে আগাই। এখানেও প্রথম দুইবারে দুইটাকে চিহ্নিত করে তৃতীয়বারে বাকী দুইটাকে চিহ্নিত করে ফেলতে পারবো। তার মানে আমাদের প্যাটার্ন হবে – যতোটা বাতি, তার চেয়ে একটা কম। তাই না?
তাইলে তো আমাদের তেমন একটা উপকার হচ্ছে না। অন্য কিছু কী করা যায়? আমরা জানি ২টার সমাধান করা যায় ১ বারে। তাহলে আমরা যদি ২টার জোড়ে যেতে পারি তাহলে হয়তো ৪টার অন্য সমাধান হতে পারে।
আমরা তাহলে অন্যভাবে আগানোর চেষ্টা করি। ধরা যাক আমাদের বাতিগুলোর সঙ্গে সুইচের সম্পর্ক এরকম
| বাতি -> | A | B | C | D |
| সুইচ -> | 1 | 3 | 4 | 2 |
যা আমরা জানি না।
এখন আমরা কী করতে পারি? আমরা কী কোন প্যাটার্ন খুঁজতে পারি? যেহেতু আমরা চিহ্নিত করার কাজ করবো তাই আমরা একটা কোন চিহ্ন ব্যবহার করবো। এজন্য আমরা 0 আর 1 ব্যবহার করবো। যেমন যে সুইচ অন সেটা 1 এবং যে বাতি জ্বলে সেটা 1। উল্টোটা 0।
প্রথমে আমরা 1 ও 2 সুইচ অন করবো। বাকী দুইটা অফ থাকবে। সেখানে 0 এবং 1 দিয়ে দেই। তাহলে সেটা হবে
| সুইচ | 1 | 2 | 3 | 4 |
| লেবেল | 1 | 1 | 0 | 0 |
আমরা যেহেতু জানি কানেকশটা কাজে ওপরে গিয়ে আমরা দেখবো A ও D জ্বলে থাকবে। অন্য দুটো নেভা। এখন বাতির নিচে আমরা লেবেলিং করি-
| বাতি | A | B | C | D |
| লেবেল | 1 | 0 | 0 | 1 |
ফিরে আসবো সুইচের কাছে। আমি কিন্তু স্পষ্টতই ৪টি বাতি ও সুইচকে দুইটি জোড়ায় ভাগ করে ফেলেছি। এখন প্রতি জোড়ার জন্যএকই কাজ করবো। যেমন প্রথম দুইটি সুইচের যা অন ছিল তার একটি (অর্ধেক) অন রেখে অন্যটি অফ করে দিবো। এবং একই ভাবে অন্য জোড়ার একটি অফ রেখে অন্যটি অন করে দিবো এবারও দুইটি অন থাকবে। আগের নিয়মে সুইচের লেবেল 0 এবং 1 আগের লেবেলের পাশে নতুন 0 ও 1 যোগ করি। ধরা যাক আমরা 1 নং ও 3 নংকে অন রেখেছি।
| সুইচ | 1 | 2 | 3 | 4 |
| লেবেল | 11 | 10 | 01 | 00 |
স্পষ্টতই আমাদের A ও B জ্বলে থাকবে। কাজে বাতির লেবেল হবে
| বাতি | A | B | C | D |
| লেবেল | 11 | 01 | 00 | 10 |
ওয়াও। এখন দেখেন বাতি আর সুইচের লেবেলগুলো প্রত্যেকটি ভিন্ন। এখন যে বাতি আর সুইচের লেবেল একই তারাই পরস্পর কানেকটেড। সেটা হলো
| বাতি | A | B | C | D |
| লেবেল | 11 | 01 | 00 | 10 |
| সুইচ | 1 | 3 | 4 | 2 |
ওয়াও। দুইবারে কিন্তু আমরা এখন চারটা বাতির চারটা সুইচকে শনাক্ত করে লেবেলিং করে ফেলেছি!
এই কার্যক্রমে আমরা দেখছি আমাদের বুদ্ধি হচ্ছে অর্ধেক করে ফেলা।
এবার ধরা যাক ৮টা বাতি ও ৮টা সুইচ আছে। তাহলে এই পদ্ধতি কেমন করে কাজ করবে?
এবার আমরা ধরি আমাদের আটটা বাতির প্রকৃত কানেকশন হলো এরকম
| বাতি -> | A | B | C | D | E | F | G | H |
| সুইচ -> | 1 | 2 | 5 | 6 | 7 | 8 | 3 | 4 |
| বাতি ও সুইচের প্রকৃত কানেকশন |
এখন আমরা অর্ধেক সুইচ প্রথমে অন করবো
| সুইচ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| লেবেল | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
এই কাজের পর দোতলায় গিয়ে আমরা দেখবো A, B, G ও H বাতি জ্বলে আছে। তাহলে বাতির লেবেল হবে
| বাতি | A | B | C | D | E | F | G | H |
| লেবেল | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
এবার আবার নিচে আসবো।1 থেকে 4 নম্বর সুইচের দুইটাকে অন রেখে বাকী দুইটাকে অফ করে দেবো। আর 5 থেক 8 পর্যন্ত সুইচের দুইটাকে অফ রেখে দুইটা অন করে আবার লেবেলিং করবো।
| সুইচ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| লেবেল | 11 | 11 | 10 | 10 | 01 | 01 | 00 | 00 |
দেখা যাচ্ছে এ যাত্রায় 1,2,5 ও 6 সুইচ অন। তারমানে A, B, C ও D বাতি জ্বলে থাকবে।
| বাতি | A | B | C | D | E | F | G | H |
| লেবেল | 11 | 11 | 01 | 01 | 00 | 00 | 10 | 10 |
এখন সুইচের দিকে তাকানো যাক। দেখবেন সুইচগুলো ৪টা জোড়াতেই ভাগ হয়ে গেছে। জোড়ার সমাধান তো আমরা জানি। প্রতি জোড়ায় একটাকে অন রেখে অন্যটা অফ করে দিতে হবে। তাহলে সুইচের নতুন লেবেল কী হবে?
| সুইচ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| লেবেল | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
এখন আমাদের 1,3,5 ও 7 নং সুইচ অন করা। তার মানে A, C, E ও G বাতি জ্বলে আছে।
| বাতি | A | B | C | D | E | F | G | H |
| লেবেল | 111 | 110 | 011 | 010 | 001 | 000 | 101 | 100 |
বাহ, এখন দেখেন বাতির লেবেল ও সুইচের লেবেল কিন্তু প্রত্যেকটাই ভিন্ন। আপনি এবার বাতির লেবেল আর সুইচের লেবেল মেলালেই পেয়ে যাবেন কোন সুইচের কোন বাতি
| বাতি | A | B | C | D | E | F | G | H |
| লেবেল | 111 | 110 | 011 | 010 | 001 | 000 | 101 | 100 |
| সুইচ | 1 | 2 | 5 | 6 | 7 | 8 | 3 | 4 |
যা কিনা প্রকৃত কানেকশন!!! অর্থাৎ আমাদের সমাধান সঠিক!!
তার মানে ৮টি বাতিকে আমরা তিনবারেই চিহ্নিত করতে পারছি।
আমার মনে হয় আমরা প্যাটার্ন পেয়ে গেছি। 8 এর দ্বিগুণ 16টি থাকলে আমরা 4 বারেই সেটা করে ফেলতে পারবো। 32টা থাকলে 5 বার, 64টি থাকলে 6 বার। 128টি থাকলে 7 বার।
আমাদের বাতি আছে 100টি যা 64টি থেকে বড় কিন্তু 128 থেকে ছোট। তারমানে ৭ বারেই আমরা আমাদের সব সুইচকে শনাক্ত করে ফেলতে পারবো!!!
তাহলে আমাদের সমাধান হবে –
আমরা প্রথমে 1-50 পর্যন্ত সুইচ অন করবো। 51-100 অফ রাখবো। ওপরে এসে ৫০টি জ্বলা বাতিকে 1 এবং ৫০টি নেভা বাতিকে 0 দিয়ে চিহ্নিত করবো। ২য় ধাপে 1-50 নং সুইচের অর্ধেক অন রেখে বাকী অর্ধেক অফ করে দিবো। আর 51-100 এর অর্ধেককে অফ রেখে বাকী অর্ধেককে জ্বালিয়ে দেবো। এভাবে প্রতি বারে আমাদের ৫০টা বাতি জ্বলে থাকবে আর ৫০টি বাতি নিভে থাকবে এবং ৭ বারেই আমরা সবক’টাকে লেবেল করে ফেলতে পারবো!!!
আমার ধারণা যারা একটু উচ্চতর গণিতের ধারণা রাখেন তাদের জন্য সমাধান হবে Log2 (n)। কাজে যে কোন সংখ্যক বাতির জন্য আপনি বের করতে পারবেন। আর যারা প্যাটার্নটা আসলে শেষ পর্যন্ত কিসের সঙ্গে মিললো, সেটাও অনেকেই নিশ্চয়ই বুঝে ফেলেছেন।
সবার সেকেন্ড ডিফারেন্সিয়াল নেগেটিভ হোক।
(এই ধরণের আরো আর্টিকেল পড়তে চাইলে এখানে ক্লিক করুন।)
লেখক: মুনির হাসান (ইমেইল: munir.hasan@bdosn.org)