এশিয়া প্যাসিফিক গণিত অলিম্পিয়াড-২০২২ (সমস্যা ৪–এর সমাধান)

প্রিয় গণিত ইশকুলের বন্ধুরা, ইতিমধ্যে তোমরা এশিয়া প্যাসিফিক গণিত অলিম্পিয়াড-২০২২–এর ৩টি সমস্যার সমাধান দেখে ফেলেছ। আজকে তোমাদের জন্য থাকছে সমস্যা ৪-এর সমাধান।

ক্যাথি n সংখ্যক মার্বেল ও k সংখ্যক বাক্স নিয়ে একটি খেলা খেলছে, যেখানে n , k ধনাত্মক পূর্ণসংখ্যা। এই nটি মার্বেল 1 থেকে n পর্যন্ত সংখ্যা দ্বারা লেবেল করা আছে এবং খেলার শুরুতে সব কটি মার্বেল একটি বাক্সেই ছিল। খেলার প্রতি চালে ক্যাথি একটি অশূন্য বাক্স নেয় এবং ওই বাক্সের মধ্যে থাকা ক্ষুদ্রতম লেবেলযুক্ত মার্বেলটি, (ধরে নিই সেই মার্বেলের লেবেল i) নির্বাচন করে সেই মার্বেলকে একটি খালি বাক্সে অথবা i+1 যেই বাক্সে আছে, সেখানে রাখে। খেলতে খেলতে কখনো যদি একটি বাক্সে শুধু n লেবেল যুক্ত মার্বেলটি থাকে, তাহলে ক্যাথি খেলায় জিতে যাবে।

(n, k) এর কোন কোন মানের জন্য ক্যাথি খেলায় জিততে পারবে?

একটু চিন্তা করলেই দেখবে যদি ক্যাথি কোনোভাবে (n , k) এর ক্ষেত্রে জিততে পারে, তাহলে সে (n-i , k) , (n , k+i) এর ক্ষেত্রেও জিততে পারবে, যেখানে i ≥ 0 । কারণ, সেই ক্ষেত্রে আমাদের কাছে অতিরিক্ত খালি বাক্স থাকবে।

প্রমাণের পূর্বে আমরা এই খেলার কিছু বৈশিষ্ট্য সম্পর্কে একটু জেনে নেব।

লেমা-১: খেলার যেকোনো মুহূর্তে প্রতিটি বাক্সে মার্বেলগুলোর লেবেল ক্রমিক পূর্ণসংখ্যা হবে।

যদি এই বৈশিষ্ট্য সত্যি না হয়, তাহলে নিশ্চয়ই খেলতে খেলতে কোনো একপর্যায়ে একটি চালের আগে প্রতিটি বাক্সে লেবেলগুলো ক্রমিক ছিল কিন্তু ওই চাল দেওয়ার ফলে সেই বৈশিষ্ট্য নষ্ট হয়েছে। মনে করি, সেই চালে ক্যাথি i লেবেল যুক্ত মার্বেলটির ওপর চাল দিয়েছে। যদি i লেবেলযুক্ত মার্বেলটি আগে থেকেই এমন একটি বাক্সে ছিল, যাতে চাল দেওয়ার আগে i , i+1 , … … , l  পর্যন্ত মার্বেল ছিল (এখানে l > i), তাহলে চাল দেওয়ার পর i কে একটি খালি বাক্সে রাখা হয়েছে। তখন ওই আগের বক্সে i+1 , … , l পর্যন্ত মার্বেলগুলো ক্রমিক হিসাবেই থাকবে। আর যদি চালের আগে i এমন বক্সে থাকত, যেখানে কেবল i ই আছে, তবে হয় i আরেকটি খালি বাক্সে যাবে, যাতে আমাদের এই শর্তের কোনো সমস্যা হয় না, আর যদি i মার্বেলটি এমন একটি বাক্সে যায়, যেখানে i+1 , … … , l পর্যন্ত মার্বেলগুলো ছিল, তবে i যাওয়ার পর সেখানে i , i+1 , … … , l পর্যন্ত মার্বেল হবে।

আবার একটু চিন্তা করলেই দেখবে যে ক্যাথির প্রতিটি চাল আবার উল্টো করা যায়। এবার মূল সমস্যায় ফেরা যাক।

লেমা-২: যদি n = 2ⁱ হয় তবে k–এর যেই সর্বনিম্ন মানের জন্য ক্যাথি জিততে পারবে, তা হলো k = i + 1 । এবং সেই মুহূর্তে 2ⁱ লেবেলযুক্ত মার্বেলটিকে আর চাল দেওয়া যাবে না।

এই লেমাটি প্রমাণের জন্য যে পদ্ধতিটি ব্যবহার করব, তা হলো গাণিতিক আরোহ পদ্ধতি বা Induction। i = 0 এর জন্য প্রমাণ করা খুবই সহজ। এবার যদি আমাদের লেমাটি i = m এর জন্য সত্যি হয়, তবে আমরা প্রমাণ করব তা i = m+1 এর জন্যও সত্যি। এখন যেহেতু i = m এর জন্য k_min = m+1 তাই i = m+1 এর জন্য k_min = m+1 । k = m+1 এর ক্ষেত্রে হাইপোথিসিস অনুযায়ী আমরা 2^m লেবেল যুক্ত মার্বেলটি চাল দিতে পারি না তাই 2^m, 2^m+1, … … , 2^m+1 মার্বেলগুলোও ক্যাথি চাল দিতে পারবে না, তাই সে জিততে পারবে না। যখন k = m+2 তখন আমরা m+1টি বাক্স ব্যবহার করে একটি বক্সে 2^m, … , 2^m+1 আনতে পারব। এবার শেষ খালি বক্সে 2^m লেবেল যুক্ত মার্বেলটি রাখব। এখন যেহেতু ক্যাথির সকল চাল আবার উল্টো করা যায়, তাই প্রথম বাক্সটি বাদ রেখে বাকি m+1টি বাক্স ব্যবহার করে 2^m এর বক্সে 1, 2, 3, … … , 2^m এর সব কটি মার্বেল নিতে পারি। এবার আমরা বাকি m+1টি বাক্স ব্যবহার করে 2^m+1, 2^m+2, … …, 2^m+1 এই 2^mটি মার্বেলের মধ্যে এমনভাবে চাল দিতে পারব, যেন একটি বক্সে 2^m+1 থাকে।

এখন আমরা প্রমাণ করব এই 2^m+1 মার্বেলটিকে আর চাল দেওয়া যায় না। যদি এই মার্বেলটিকে চাল দিতে হয়, তবে এটিকে আরেকটি খালি ঘরে সরাতে হবে। কিন্তু যদি 1, 2, 3, … …, 2^m এর বাক্সে আর কোনো নতুন মার্বেল যোগ না হয়, তবে হাইপোথিসিস অনুযায়ী আমরা বাকি m + 1 বাক্সের মধ্যে 2^m+1 কে চাল দিতে পারব না। তাই খেলার কোনো একপর্যায়ে এটি বক্সে 1, 2, 3, … …, 2^m, 2^m+1 থাকতে হবে। কিন্তু সেই কাজের জন্য আমরা 2^m+1 যুক্ত বাক্সটি ব্যবহার করতে পারব না। কারণ, সেটি ব্যবহারের জন্য আমাদের সব মার্বেলকে আবার প্রথম অবস্থায় ফেরত নিতে হবে। তাই 2^m+1 মার্বেলটির ওপর চাল দেওয়া সম্ভব নয়। আর আমাদের লেমাটি সত্যি।

এখন যেহেতু ক্যাথি (n , k) এর জন্য জিতলে (n-i , k) এর জন্যও জিতবে। তাই যদি n ≤ 2^k-1 হয়, তবে ক্যাথি জিতবে।