Conjecture বা অনুমান হচ্ছে এমন ধারণা যার প্রমাণিত নয়। এ ধরনের অনুমান করা হয় উপলব্ধ তথ্যের উপর ভিত্তি করে। জার্মান গণিতবিদ Christian Goldbach একটি conjecture দেন ১৭৪২ সালে। সেটি ছিলো,
“যেকোনো জোড় সংখ্যাকে আমরা দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।”
সেসময় 1 কে ও মৌলিক সংখ্যা হিসেবে ধরা হতো। তাই পরবর্তীকালে এই conjecture কে পরিবর্তন করে বলা হয়,
“2 থেকে বড় যেকোনো জোড় সংখ্যাকে আমরা দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।”
যেমন, 4 = 2 + 2, 6 = 3 + 3, 8 = 5+ 3 ইত্যাদি। এই conjecture কে বলা হয় Goldbach’s strong conjecture. এই conjecture এর উপর ভিত্তি করে আরও একটি conjecture রয়েছে। সেটি হলো,
“5 থেকে বড় যেকোনো বিজোড় সংখ্যাকে আমরা তিনটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।”
এই conjecture টি Goldbach’s strong conjecture এর উপর ভিত্তি করে দেওয়া হয়েছে, তাই এটিকে Goldbach’s weak conjecture বলা হয়। খেয়াল করলে দেখবো, 5 থেকে বড় যেকোনো বিজোড় সংখ্যা n এর জন্য n-3 অবশ্যই 2 থেকে বড় জোড় সংখ্যা হবে। তাহলে আমরা n-3 কে তো দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতেই পারছি। এরপর শুধু ওই যোগফলের সাথে 3 যোগ করে দিলেই তো আমরা n পেয়ে যাচ্ছি।
এবার আমরা এ সম্পর্কিত কিছু সমস্যা দেখবো।
উদাহরণ সমস্যা ১
উৎস: Codeforces Round #324 (Div. 2), Problem D
সমস্যার Link: https://codeforces.com/problemset/problem/584/D
একটি বিজোড় সংখ্যা n ( 3 <= n <= 1e9 ) দেওয়া আছে। একে তিন বা তার কম সংখ্যক মৌলিক সংখ্যার যোগফল হিসেবে প্রকাশ করতে হবে।
n যদি মৌলিক সংখ্যা হয়, তবে একে আর ভাঙার দরকার হবে না। তাই শুরুতে আমরা যাচাই করে নিবো n মৌলিক সংখ্যা কিনা।
এবার n যদি মৌলিক সংখ্যা না হয়, তাহলে এটি অবশ্যই 9 বা তার চেয়ে বড় হবে। কারণ 3, 5, 7 এরা সবাই মৌলিক সংখ্যা। আমরা 3 কে আউটপুটের একটি মৌলিক সংখ্যা হিসেবে ধরে নিবো।
এখন (n-3) হচ্ছে একটি জোড় সংখ্যা এবং 6 <= (n-3) <= 1e9. একটু আগেই তো Goldbach এর conjecture থেকে আমরা দেখলাম এই সীমার মধ্যে জোড় সংখ্যাগুলোকে আমরা দুটি মৌলিক সংখ্যার যোগফল আকারে লিখতে পারি। তাহলে আমরা একটি লুপ চালিয়েই মৌলিক সংখ্যা দুটি বের করতে পারি।
সমাধান link: https://codeforces.com/contest/584/submission/150913786
অনুরূপভাবে আমরা Timus 1356 সমস্যাটির সমাধান করে ফেলতে পারি।
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন