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

ব্যাংক অফ অসলো দুই ধরণের কয়েন ব্যবহার করে : অ্যালুমিনিয়াম (A দ্বারা চিহ্নিত) এবং ব্রোঞ্জ (B দ্বারা চিহ্নিত)। মারিয়ান এর কাছে n টি অ্যালুমিনিয়াম কয়েন এবং n টি ব্রোঞ্জ কয়েন একটি সারিতে কোনো একটি ক্রমে সাজানো রয়েছে। পাশাপাশি থাকা এক বা একাধিক কয়েনকে একত্রে আমরা একটি চেইন বলব যদি তারা সব একই ধরণের হয়। কোন একটি নির্দিষ্ট ধনাত্নক পূর্ণসংখ্যা k ≤ 2n এর জন্য মারিয়ান এই অপারেশনটি বারবার চালাতে থাকে: সারির বামদিক থেকে k তম কয়েনটি সহ সবচেয়ে বড় চেইনটি খুঁজে বের করে এবং সেটির সবগুলো কয়েনকে নিয়ে সারির বামপাশে রেখে দেয়।

উদাহরণ স্বরুপ, n=4 এবং k=4 এর জন্য AABBBABA থেকে শুরু করলে প্রক্রিয়াটি এভাবে চলবে,

এমন সকল জোড়া (n, k) যেখানে 1 ≤ k ≤ 2n বের করো যেন সারিতে কয়েনগুলোর যেকোনো শুরুর বিন্যাসের জন্যই প্রক্রিয়াটির কোনো একটি পর্যায়ে সারির বামদিকের n সংখ্যক কয়েন সব একই ধরণের হয়ে যাবে।

এই সমাধানে আমরা X^m দ্বারা পরপর m টি X কয়েনকে বোঝাবো যেখানে m একটি ধনাত্নক পুর্ণসংখ্যা এবং X এর স্থানে A ও B এর যেকোনোটি হতে পারে। একটি চেইনকে আমরা ব্লক বলবো যদি একে কোনো দিকে আরও বড় করা না যায়। যেমন :

এছাড়াও সারির একটি বিন্যাসকে আমরা ভালো বলব যদি এর বাম দিকে n টি কয়েন সব একই ধরণের হয়।

এখন আমরা প্রমাণ করব শুধুমাত্র n ≤ k ≤ 2n - ⌊n/2⌋ হলেই সকল শুরুর বিন্যাসের জন্যই কোনো একটি পর্যায়ে মারিয়ান একটি ভালো বিন্যাসে পৌছাবে।

প্রথমত, 1 ≤ k ≤ n-1 হলে যদি শুরুর বিন্যাসটি হয়: B^n-1AⁿB,তাহলে মারিয়ান সবসময় বামদিকের B^n-1ব্লকটি নির্বাচন করবে এবং ফলে বিন্যাসটি সবসময় অপরিবর্তিত থাকবে। তাই এক্ষেত্রে মারিয়ান কখনোই ভালো বিন্যাসে পৌছাবে না।

কেননা এখানকার প্রতিটি বিন্যাসের জন্যই এর মান বাম দিকের তিনটি ব্লকের মোট দৈর্ঘ্যের চেয়ে বড়। তাই মারিয়ান প্রতি ধাপে ডানের ব্লকটিকে নিয়ে সারির বামে রাখবে এবং এই লুপ চলতে থাকবে। তাই এর এই মানের জন্যও মারিয়ান ভালো বিন্যাসে পৌছাবে না।

এখন আমরা প্রমাণ করব, n ≤ k ≤ 2n - ⌊n/2⌋ হলে যেকোনো শুরুর বিন্যাসের জন্যই মারিয়ান কোনো এক পর্যায়ে একটি ভালো বিন্যাসে পৌছাবে।

এখন আমরা সারিতে ব্লক সংখ্যার কথা চিন্তা করি। যেহেতু, মারিয়ান তার অপারেশনে একটি ব্লককে তুলে সারির শুরুতে নিয়ে আসে, তাই এর মাধ্যমে ব্লক সংখ্যা কখনোই বাড়তে পারবে না। আবার সংখ্যাটি ধনাত্নক পুর্ণসংখ্যা, তাই এটি অসীম সংখ্যক বার কমতেও পারবে না। সুতরাং কোনো একটি পর্যায়ে থেকে সারির ব্লক সংখ্যা ধ্রুব থাকবে। মনে করি ঐ পর্যায় থেকে সারির ব্লক সংখ্যা = C। এখন আমরা প্রমাণ করতে চাই C = 2 । লক্ষ করি যেহেতু এই পর্যায় থেকে C এর মান ধ্রুব থাকে, তাই এখন থেকে প্রতি অপারেশনে নির্বাচিত ব্লকের দুই পাশেই কয়েন থাকতে পারবে না। কেননা তা নাহলে দুইপাশের ব্লক দুটি অপারেশনের পর মিলিত হয়ে একটি ব্লক তৈরি করবে এবং ব্লক সংখ্যা কমে যাবে।

• k = n হলে এটি তখনই সম্ভব যদি ব্লকটি সারির বামপাশে থাকে কারণ তা নাহলে ব্লক এর দৈর্ঘ্য n এর চেয়ে বড় হতে হবে যা সম্ভব নয়। আর সেটি হওয়ার মানেই প্রথম n সখ্যক কয়েন একই ধরণের হওয়া যেটা আমরা চাই!

• n + 1 ≤ k ≤ 2n - ⌊n/2⌋ হলে, একই যুক্তিতে k তম কয়েনের ব্লকটিকে সারির সর্বডানের ব্লক হতে হবে। তাই এক্ষেত্রে প্রতি অপারেশনে মারিয়ান সর্বডানের ব্লকটিকে নিয়ে সারির বামপাশে যোগ করবে। তাই সারিতে ব্লকগুলো চক্রাকারে ঘুরতে থাকবে (উপরের ছবিতে দেখুন)।

  যেহেতু প্রতিটি ব্লককেই মারিয়ান কখনো না কখনো নির্বাচন করবে, তাই প্রতিটি ব্লক এর দৈর্ঘ্যই কমপক্ষে ⌊n/2⌋ + 1 হতে হবে (যেহেতু k ≤ 2n - ⌊n/2⌋)। আবার ব্লকের সংখ্যা এক্ষেত্রে বিজোড় হতে পারবে না কেননা তা নাহলে প্রথম ও শেষ ব্লকের কয়েন একই ধরণের হবে এবং পরবর্তী অপারেশনে তারা মিলিত হয়ে একটি ব্লক হয়ে যাবে এবং ব্লকের সংখ্যা কমে যাবে। তাই জোড় হতে হবে। এখন মনে করি, C ≠ 2, তাহলে C ≥ 4 ।

  সেক্ষেত্রে, সারিতে কয়েনের সংখ্যা ≥ ব্লকের সংখ্যা × সর্বনিম্ন ব্লকের দৈর্ঘ্য

  বা, 2n ≥ C × (n/2 + 1) ≥ 4(⌊n/2⌋ + 1)

  বা, 2n ≥ 2(⌊n/2⌋ + ⌊n/2⌋ + 1) + 2 ≥ 2(⌊n/2⌋ + ⌈n/2⌉) + 2 [∵ ⌊a⌋ + 1 ≥ ⌈a⌉]

  বা, 2n ≥ 2n + 2 [∵ ⌈n/2⌉ + ⌊n/2⌋ = n]

  কিন্তু 2n ≱ 2n + 2, সুতরাং আমরা যা ধরে নিয়েছিলাম (C ≠ 2) সেটি ভুল। সুতরাং, C ≠ 2 এবং এটিই আমরা দেখাতে চেয়েছি।

অতএব, শুধুমাত্র n ≤ k ≤ 2n - ⌊n/2⌋ হলেই সকল শুরুর বিন্যাসের জন্যই কোনো একটি পর্যায়ে সারির বামের n টি কয়েন সব একই ধরণের হবে।