নিশ্ছেদ সাবসেটের অস্তিত্ব প্রমাণে পায়রাখোপ নীতি

আমরা আজকে পায়রাখোপ নীতির সাহায্যে একটি আইএমও সমস্যা সমাধান করব। এ নীতির সাহায্যে সমস্যা সমাধানের আগে প্রথমেই জেনে নিই-এ নীতি কী বলে।

এ নীতির নামটা যতটা অদ্ভুত মনে হচ্ছে, নীতিটা ততটাই সহজ। এ নীতি বলে মনে করো, তোমার কাছে (n + 1) সংখ্যক পায়রা আছে, আর এদের তুমি n সংখ্যক খোপে রাখতে চাও, সে ক্ষেত্রে অবশ্যই তোমাকে একটি খোপে একাধিক পায়রা রাখতে হবে, কারণ সব কটি খোপে একটি করে পায়রা রাখলেও শেষে একটি পায়রা বাকি থাকে।

এখন চলো এ সহজ নীতি ব্যবহার করে ১৯৭২ সালের আইএমও প্রথম সমস্যা  সমাধান করা যাক। প্রথমেই সমস্যাটি দেখে নিই।

সমস্যা: তোমাকে 100-এর চেয়ে ছোট 10টি ধনাত্মক পূর্ণসংখ্যার সেট দেওয়া আছে। প্রমাণ কর যে এই সেটের এমন দুটি অশূন্য নিশ্ছেদ সাবসেট আছে, যাদের উপাদানগুলোর যোগফল সমান।

সমস্যাটি দেখে ভয় পাওয়ার কিছু নেই। আমরা ধাপে ধাপে সমস্যাটি সমাধান করব। প্রথমেই কয়েকটি বিষয় সম্পর্কে ধারণা নিই।

সমাধান: যেহেতু আমরা পায়রাখোপ নীতির সাহায্যে এ সমস্যা সমাধান করব, তাই আমাদের প্রথমেই পায়রা আর খোপ খুঁজে বের করতে হবে। সমস্যাটি ভালো করে লক্ষ্য করি, এখানে দুইটি নিশ্ছেদ সেটের উপাদানগুলোর যোগফল সমান দেখাতে বলেছে। তাই আমরা প্রদত্ত সেটটির (10টি ধনাত্মক পূর্ণসংখ্যার সেট) সাবসেটকে পায়রা এবং এদের উপাদানগুলোর সম্ভাব্য যোগফলকে পায়রার খোপ ধরব।

আমরা জানি, কোনো সেটের উপাদানসংখ্যা n হলে, ওই সেটের সাবসেট সংখ্যা 2ⁿ। প্রদত্ত সেটে 10টি সংখ্যা আছে, তাই এর সাবসেট সংখ্যা 2¹⁰ = 1024টি।

আবার বলা হয়েছে ওই 10টি উপাদানের সবকটি 100 থেকে ছোট। তাই এর সবচেয়ে বড় সাবসেটটি হতে পারে {99, 98, 97, 96, 95, 94, 93, 92, 91, 90}। এর উপাদানগুলোর যোগফল = 99 + 98 + 97 + 96 + 95 + 94 + 93 + 92 + 91 + 90 = 945। আবার সবচেয়ে ছোট সাবসেটটি হলো ফাঁকা সেট, যার যোগফল 0। তাই প্রদত্ত সেটের যেকোনো সাবসেটের উপাদানগুলোর যোগফল হবে 0 থেকে 945-এর মধ্যে যেকোনো একটি পূর্ণসংখ্যা। আমরা যেহেতু সাবসেটের উপাদানগুলোর সম্ভাব্য যোগফলকে পায়রার খোপ ধরেছিলাম, তাই এখানে খোপ আছে = (945 - 0) + 1 = 946টি। আর প্রদত্ত সেটটির সব সেট তথা পায়রা সংখ্যা ছিল 1024টি।

এখন দেখা যাচ্ছে পায়রার সংখ্যা 1024টি এবং খোপ সংখ্যা হলো 946টি। অর্থাৎ পায়রাখোপ নীতি অনুসারে 1টা খোপে 2টা পায়রা থাকবেই। অর্থাৎ এমন দুটি সাবসেট আছে, যাদের উপাদানগুলোর যোগফল সমান। কিন্তু আমাদের সমাধান এখনো শেষ হয়নি!

সমস্যায় বলা ছিল সাবসেট দুটি নিশ্ছেদ এবং অশূন্য হতে হবে। প্রথমে নিশ্ছেদের বিষয়টি সমাধান করি। ধরি, আমরা যে দুইটি সাবসেট পেলাম (যাদের উপাদানগুলোর যোগফল সমান), তাদের মধ্যে একটি সাধারণ উপাদান আছে। কিন্তু ওই সাধারণ উপাদানটি বাদ দিলেও ওই দুই সাবসেটের উপাদানগুলোর যোগফল সমান থাকবে।

যেমন ধরি একটি সেট A = {1, 4, 5} এবং আরেকটি সেট B = {1, 7, 2}। A ও B সেটের সাধারণ উপাদান হলো 1। এখন A সেটের উপাদানগুলোর যোগফল = 1 + 4 + 5 = 10 এবং B সেটের উপাদানগুলোর যোগফল = 1 + 7 + 2 = 10। অর্থাৎ দুটি সেটের উপাদানগুলোর যোগফল সমান। এখন আমরা এদের সাধারণ উপাদান 1 বাদ দিয়ে দিই। তাহলে A সেটের উপাদানগুলোর নতুন যোগফল = 7 + 2 = 9 এবং B সেটের ক্ষেত্রে নতুন যোগফল = 4 + 5 = 9। অর্থাৎ দেখা যাচ্ছে দুটি নিশ্ছেদ নয় এমন সেটের যোগফল সমান হলে, ওই দুটি সেট থেকে যদি তাদের সাধারণ উপাদান বাদ দিই, তাহলেও  যোগফল একই থাকবে। নিশ্ছেদ প্রমাণ করা শেষ!

এখন লক্ষ্য কর যে সাধারণ উপাদান বাদ দেওয়ার পর কোনো সাবসেট ফাঁকা হয়ে যেতে পারে না; কারণ, যদি দুটি সাবসেট ফাঁকা হয়ে যায়, তাহলে প্রথমেই সাবসেট দুটি একই ছিল কিন্তু তা অসম্ভব। আবার, শুধু একটা সাবসেট ফাঁকা হলে ওই সাবসেটের উপাদানগুলোর যোগফল শূন্য, যেখানে অপর সাবসেটের উপাদানগুলোর যোগফল ধনাত্মক। সে ক্ষেত্রে তাদের যোগফল সমান হতে পারে না। যেমন: A = {1, 4, 5} এবং B = {1, 7, 2} এ সেট থেকে তাদের সাধারণ উপাদান অর্থাৎ 1 বাদ দিলে কখনো তারা ফাঁকা সেটে পরিণত হবে না। একমাত্র যখন A = {1, 2, 3} = B = {1, 2, 3} হবে তখন এদের সাধারণ উপাদান 1, 2 ও 3 বাদ দিলে এরা ফাঁকা সেটে পরিণত হবে। কিন্তু একটা সেটের দুইটা সাবসেট কখনো একই হতে পারে না।

তাহলে আমরা প্রদত্ত সেটের দুটি অশূন্য নিশ্ছেদ সাবসেট পেয়ে গেলাম, যাদের উপাদানগুলোর যোগফল সমান। প্রমাণ শেষ!