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

মনে করি,  একটি ধনাত্মক পূর্ণসংখ্যা। একটি নর্ডিক বর্গ হল এমন একটি n × n বোর্ড যাতে  থেকে n² পর্যন্ত পূর্ণসংখ্যা দ্বারা এর প্রতিটি ঘর এমন ভাবে পূর্ণ করা যাতে প্রতি ঘরে কেবল একটিমাত্র সংখ্যা থাকে। একটি ঘরকে ভ্যালি বলা হবে যদি তার পাশের ঘরগুলির সংখ্যার মান ঐ ঘর এর চেয়ে বড়। একটি ঊর্ধ্বমুখী পথ হল এক বা একাধিক ঘরের ধারা যেন

1. এর প্রথম ঘরটি একটি ভ্যালি হয়।

2. পরবর্তী প্রত্যেকটি ঘর শেষ ঘরের পাশের ঘর হয়।

3. ধারা এর প্রতিটি সংখ্যা ঊর্ধক্রমে হয়।

n এর এমন একটি ফাংশন বের করো যার দ্বারা একটি নর্ডিক বর্গে নুন্যতম ঊর্ধ্বমুখী পথের সংখ্যা বের করা যায়।

আমরা প্রমান করতে চাই যে নুন্যতম ঊর্ধ্বমুখী পথের সংখ্যা 2n(n - 1) + 1।

প্রত্যেক জোড়া পাশাপাশি ঘর থেকে আমরা নিম্নমুখী পথ অনুসরণ করে একটি ভ্যালিতে পৌছাতে পারবো। তাই প্রতি জোড়া পাশাপাশি ঘরের জন্য এমন একটি ঊর্ধ্বমুখী পথ আছে যাতে ঐ দুইজোড়া ঘর ঐ পথের বৃহত্তম জোড়া হয়।

এমন পাশাপাশি ঘরের জোড়ার সংখ্যা লম্বালম্বি বরাবর n(n-1) টি এবং আড়াআড়ি বরাবর n(n-1) টি। এবং যে ঘরে 1 আছে শুধুমাত্র সেই ঘর নিয়ে আরও একটি ঊর্ধ্বমুখী পথ বানানো যাবে। তাই ঊর্ধ্বমুখী পথের সংখ্যা কমপক্ষে 2n(n - 1) + 1 টি।

এখন আমাদের এমন একটি কন্সট্রাকশন দেখাতে হবে যেখানে 2n(n - 1) + 1 টি ঊর্ধ্বমুখী পথ আছে।

আমরা প্রথমে এমন ভাবে একটি R ঘর বিশিষ্ট ট্রি  কন্সট্রাক্ট করতে হবে যাতে প্রত্যেকটি ঘর যেটি ট্রি এর অংশ নয় তা কেবল ট্রি এর কোনো ঘরের পাশাপাশি হয়।

চিত্রে n = 9 এর জন্য ট্রি কন্সট্রাক্ট করে দেখানো হয়েছে, যা থেকে খুব সহজেই 3 এর যেকোনো গুনিতক এর জন্যই ট্রি কন্সট্রাক্ট করা যায়। এবং 3 এর গুনিতক নয় এমন সব সংখ্যা এর জন্য সর্ববামের অথবা সর্বডানের কলাম বাদ দিয়ে এবং সর্ব উপরের সারি বাদ দিয়ে আমরা ট্রি কন্সট্রাক্ট করতে পারি।

এবার আমরা 1 থেকে R পর্যন্ত সংখ্যা এমনভাবে যাতে ট্রি এর যেকোনো ঘরে বসে এবং পরবর্তী প্রত্যেকটি সংখ্যা এমনভাবে ট্রি এর ঘরগুলোতে বসানো হবে যাতে তা কেবলমাত্র পূর্ববর্তী একটি সংখ্যা এর পাশাপাশি হয়।

এবং R+1 থেকে n² পর্যন্ত সংখ্যাগুলোকে যেকোনো ভাবে বাকি ঘরগুলিতে বসাতে হবে। আমরা জানি যে প্রত্যেক জোড়া পাশাপাশি ঘরের সংখ্যা কোনো একটি ঊর্ধ্বমুখী পথের বৃহত্তম জোড়া ।

যেহেতু প্রত্যেক জোড়া এর ছোট সংখ্যাটি ট্রি এর মধ্যে রয়েছে এবং যার থেকে কেবল একটি মাত্র নিম্নম্মুখী পথ আছে 1 পর্যন্ত পৌঁছানোর। তাই এখানে মোট 2n(n - 1) + 1 টি ঊর্ধ্বমুখী পথ আছে।