IMO 2021 Problem 1

সমস্যাঃ ধরি n \ge 100 একটি পূর্ণসংখ্যা। ইভান n, n+1, n+2,..., 2n পর্যন্ত সংখ্যাগুলো ভিন্ন ভিন্ন কার্ডের উপরে লিখলো। এবার সে এই n+1 টি কার্ড এলোমেলো করে সবগুলো কার্ড দুই ভাগে ভাগ করলো। প্রমাণ করো যে, দুই ভাগের যেকোন এক ভাগে এমন দুইটি কার্ড আছে যাদের সংখ্যা দুটো যোগ করলে একটি পূর্ণবর্গ সংখ্যা পাওয়া যাবে।

4 Likes

সমাধানঃ

আমরা যদি n এবং 2n এর মাঝে এমন তিনটি পূর্ণসংখ্যা বের করতে পারি যাদের মধ্যে যেকোন দুটির যোগফল একটি পূর্ণবর্গসংখ্যা, তাহলেই আমাদের প্রমাণ হয়ে যাবে। কেননা, এই তিনটি পূর্ণসংখ্যার মধ্যে কমপক্ষে দুটি পূর্ণসংখ্যা অবশ্যই একটি ভাগে থাকবেই।

ধরি এই তিনটি সংখ্যা হলো x<y<z , এবং এদের মধ্যে যেকোন দুটি নিয়ে যোগ করলে আমরা যে তিনটি পূর্ণবর্গসংখ্যা পাবো তা হলো যথাক্রমে x+y=(2a-1)^2 , x+z=(2a)^2 , y+z=(2a+1)^2
x,y,z এর জন্যে আমরা সমাধান করে পাই x= \frac{(2a-1)^2 + (2a)^2 - (2a+1)^2}{2} = 2a^2 - 4a, y=\frac{(2a-1)^2 + (2a+1)^2 - (2a)^2}{2}=2a^2+1 এবং z=\frac{(2a+1)^2 + (2a)^2 - (2a-1)^2}{2}= 2a^2 + 4a

n=100 এর জন্যে আমরা a=9 একটি সমাধান পাই। অর্থ্যাৎ, x=126, y=163, z=198

এবার, n এর যেকোন মানের জন্যেই যে এটি সত্য তা আমরা আরোহ পদ্ধতি (induction) দিয়ে প্রমাণ করবো।
আমাদের মূলত এটি দেখানো লাগবে যে যেকোন n>100 এর জন্যে আমরা সর্বদা এমন একটি a পাবো যার জন্যে n \le 2a^2-4a < 2a^2+4a \le 2n .
ধরি n=m এর জন্যে এটি সত্য। এবার আমাদের n = m+1 এর জন্যেও যে এটি সত্য তা প্রমাণ করতে হবে।
যদি m < 2a^2 -4a হয় তাহলে m+1 \le 2a^2 - 4a < 2a^2 + 4a < 2m+2 হবে (শেষের অংশটুকু সত্য কারণ আগের কেসে আমরা বলেছি 2a^2+4a \le 2m)
যদি m= 2a^2 - 4a হয় তবে আমরা a এর জায়গায় b=a+1 বসাবো। তখন x= 2a^2 -2, y= 2a^2 + 4a +3, z= 2a^2 + 8a + 6 হবে। তখন x অবশ্যই (m+1) এবং (2m+2) এর মধ্যে হবে।
y(m+1) এবং (2m+2) এর মধ্যে হবে, কারণ যদি m= 2a^2 -4a হয় তাহলে 2a^2 + 4a < 2m \Rightarrow 2a^2 +4a +1 \le 2m \Rightarrow 2a^2 +4a +3 \le 2m+2.
এখন যদি আমরা z=2a^2 +8a + 6 \le 2m+2 প্রমাণ করতে পারি, তাহলে আমাদের প্রমাণ শেষ।
এখানে, m= 2a^2 -4a, সুতরাং 2m+2 = 4a^2 - 8a +2. তাহলে আমাদের শুধুমাত্র প্রমাণ করতে হবে যে 2a^2 +8a + 6 \le 4a^2 - 8a +2 \Rightarrow 2a^2 \ge 16a +4 \Rightarrow a^2 \ge 8a+2. শেষের অসমতাটি সকল a \ge 9 এর জন্যে সত্য হবে। আর আমাদের a এর সর্বনিম্ন মানও 9, অর্থ্যাৎ আমাদের প্রমাণ শেষ।

11 Likes