আন্তর্জাতিক গণিত অলিম্পিয়াড – ২০২৩ (সমস্যা ৫-এর সমাধান)

প্রিয় গণিত ইশকুলের বন্ধুরা, আশাকরি সবাই ভালো আছো। তোমরা জানো এবছর জাপানের চিবায় ৬৪ তম আন্তর্জাতিক গণিত অলিম্পিয়াড অনুষ্ঠিত হয়। সেখানে মোট ৬ টি সমস্যা সমাধান করার জন্য দেওয়া হয়েছিল। ইতিমধ্যে তোমরা ৪ টি সমস্যার সমাধান দেখে ফেলেছ। আজকের পর্বে আমরা ৫ম সমস্যার সমাধান দেখব।

মনে করি, n একটি ধনাত্মক সংখ্যা। একটি জাপানি ত্রিভুজ সমবাহু ত্রিভুজ আকৃতির 1 + 2 + ... + n টি বৃত্ত দিয়ে সাজানো আছে যেন প্রত্যেক i = 1, 2, ... , n এর জন্য  i-তম সারিতে i টি বৃত্ত থাকে। প্রতি সারিতে একটি বৃত্তকে লাল রং করা হয়েছে।

একটি নিনজা পথ হল n টি বৃত্তের একটি সিকোয়েন্স যেখানে সব থেকে উপরের বৃত্ত থেকে শুরু করে প্রতি ধাপে আগের বৃত্তের ঠিক নিচের  দুটি বৃত্তের যে কোন একটা নির্বাচন করা হয়। এভাবেই শেষ সারি পর্যন্ত যাওয়া হয়। নিচে n = 6 এর জন্য জাপানি ত্রিভুজ দেখান হলো এবং একটি জাপানি পথে ২টি লাল বৃত্ত রয়েছে।

সব থেকে বড় সংখ্যা k বের কর যেন n সারি বিশিষ্ট জাপানি ত্রিভুজে k টি লাল বৃত্ত বিশিষ্ট একটি পথ সবসময়ই থাকে।

আমরা প্রমাণ করব যে, k = ⌊log₂n⌋ + 1।

আমরা উপর থেকে i-তম সারিকে সারি i বলব। যদি n+1–i তম সারির 2i – 1 (mod n + i – 1) তম বৃত্তকে লাল রং করি, তবে একটি নিনজা পথে সর্বোচ্চ [log₂n] + 1 লাল বৃত্ত থাকা সম্ভব। ধরি, f(n) = ⌊log₂n⌋ + 1।

এখন দেখাতে হবে যে, f(n) টি লাল বৃত্ত বিশিষ্ট নিনজা পথ সবসময়ই থাকবে।

যদি সবথেকে উপরের বৃত্ত থেকে A লাল  বৃত্ত পর্যন্ত সর্বোচ্চ m টি লাল বৃত্ত বিশিষ্ট নিনজা পথ থাকে, তবে A এর পাওয়ার m ।

Claim–1: লাল বৃত্ত A ও B এর পাওয়ার একই হলে A কে সবার উপরে রেখে যে সাব ত্রিভুজ তৈরি করা হয়, তার মধ্যে B থাকবে না এবং বিপরীতভাবে সত্য।

প্রমাণ: A কে সবার উপরে রেখে যে সাব ত্রিভুজ তৈরি করা হয়, তার মধ্যে B থাকলে B এর পাওয়ার কমপক্ষে A এর পাওয়ার থেকে 1 বেশি হবে।

Claim–2: i পাওয়ার বিশিষ্ট সর্বোচ্চ 2ⁱ টি বৃত্ত আছে।

প্রমাণ:  i = 1 হলে এটি অবশ্যই সত্য। ধরি, i = 1, 2, ... , t এর জন্য এটি সত্য। তাহলে t অথবা তার কম পাওয়ার বিশিষ্ট বৃত্তের সংখ্যা সর্বোচ্চ (2^t – 1)। অতএব, (t + 1) পাওয়ার বিশিষ্ট একটি লাল বৃত্ত আছে যেটি 2^t তম অথবা তার উপরের কোন সারিতে আছে। এই লাল বৃত্তটিকে সবার উপরের বৃত্ত ধরে যে sub-triangle টি বিদ্যমান,  তার মধ্যে কোন (t + 1) পাওয়ার বিশিষ্ট লাল বৃত্ত থাকবে না।

তাই এমন সর্বোচ্চ (2^{t + 1} – 1) টি হেলান লাইন রয়েছে যার মধ্যে (t + 1) পাওয়ার বিশিষ্ট লাল বৃত্ত আছে। একটি হেলান লাইনে সর্বোচ্চ একটি (t + 1) পাওয়ার বিশিষ্ট লাল বৃত্ত থাকবে  অতএব, সর্বোচ্চ 2^t+1 টি (t + 1) পাওয়ার বিশিষ্ট লাল বৃত্ত আছে ।

Claim 2 থেকেই বলা যায়, কমপক্ষে একটি f(n) পাওয়ার বিশিষ্ট লাল বৃত্ত আছে।