কবুতরের খোপ নীতি

খোপে কবুতর। এখানে m = ৯ টি খোপে n = ১০ টি কবুতর রয়েছে। ১০ যেহেতু ৯ এর চেয়ে বড়, তাই কবুতরের খোপ নীতি বলে যে, কমপক্ষে একটি খোপে একাধিক কবুতর রয়েছে। (উপরের বাম খোপে ২টি কবুতর রয়েছে।)

কবুতরের খোপ নীতি বা পিজনহোল নীতি হলো বিচ্ছিন্ন গণিতের একটি নীতি। এই নীতি অনুযায়ী যদি m সংখ্যক বাক্সে n সংখ্যক জিনিস রাখা হয়, যেখানে n>m, তাহলে কমপক্ষে একটি বাক্সে অবশ্যই একের অধিক জিনিস থাকবে। উদাহরণস্বরূপ, তিনটি অবিপরীতযোগ্য হাতমোজার মধ্যে অবশ্যই দুইটি ডান হাতের অথবা অবশ্যই দুইটি বাম হাতের হবে; কারণ এখানে যদিও তিনটি জিনিস রয়েছে কিন্তু হাতমোজার কেবল দুইটি ধরণই বিদ্যমান এবং এদেরকে এই দুইটি ধরণের মধ্যেই বিন্যস্ত করতে হবে। এটি আপাতদৃষ্টিতে খুবই সাধারণ গণনা যুক্তি মনে হতে পারে কিন্তু এটি অনেক ক্ষেত্রে অপ্রত্যাশিত ফলাফল দিতে পারে। উদাহরণস্বরূপ- ধরা যাক বলা আছে যে, একজন মানুষের মাথায় চুলের সংখ্যার চেয়ে এক একক বা তার বেশি সংখ্যক মানুষ হলো ঢাকার জনসংখ্যা। কবুতরের খোপ নীতি অনুযায়ী, অবশ্যই ঢাকাতে কমপক্ষে এমন দুইজন মানুষ থাকবে যাদের মাথায় চুলের সংখ্যা সমান।

১৬২৪ সালে জিন লিউরেচন রচিত একটি বইয়ে সর্বপ্রথম কবুতরের খোপ নীতির উল্লেখ পাওয়া যায়। কিন্তু ১৮৩৪ সালে পিটার গুস্তাভ লেজেউন ডিরিচলেট কর্তৃক এই নীতির সংশোধনের পর এটি ডিরিচলেট বাক্স নীতি বা ডিরিচলেট ড্রয়ার নীতি নামে ব্যাপক পরিচিতি লাভ করে। কেননা ডিরিচলেট Schubfachprinzip শব্দটি ব্যবহার করেছিল যার অর্থ হচ্ছে "ড্রয়ার নীতি" বা "শেলফ নীতি"।

নীতিটির বেশ কয়েকটি সাধারণীকৃত রুপ রয়েছে এবং বিভিন্ন উপায়ে এটি বর্ণনা করা যেতে পারে। গাণিতিকভাবে: সকল স্বাভাবিক সংখ্যা k এবং m এর জন্য, যদি n = km + 1 বস্তুগুলি m সেটের মধ্যে বিতরণ করা হয়, তবে কবুতরের খোপ নীতি অনুযায়ী সেটগুলির মধ্যে অন্তত একটিতে কমপক্ষে k + 1 বস্তু থাকবে। যেকোনো n এবং m জন্য, এটি সাধারণীকৃত রূপ হচ্ছে- $k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil$

যেখানে $\lfloor \cdots \rfloor$ এবং $\lceil \cdots \rceil$ যথাক্রমে মেঝে এবং ছাদ ফাংশন নির্দেশ করে।

যদিও নীতিটির সবচেয়ে সরল প্রয়োগ হলো সসীম সেটে (যেমন কবুতর এবং বাক্স), তবুও এটি অসীম সেটেও ব্যবহৃত হয় যেখানে এক-এক মিল নেই। সিগেলের লেমার মতো উচ্চতর গাণিতিক প্রমাণগুলি এই নীতির সাধারণ ধারণার উপর ভিত্তি করে তৈরি হয়েছে।

উদাহরণসমূহ

মোজা বাছাই

ধরা যাক, একটি ড্রয়ারে কতগুলো কালো মোজা এবং নীল মোজার রয়েছে, যার প্রত্যেকটি যেকোনো পায়ে পরা যেতে পারে। না তাকিয়েই ড্রয়ার থেকে বেশ কয়েকটি মোজা বের করা হলো। তাহলে, একই রঙের এক জোড়া মোজা নিশ্চিতভাবে পাওয়ার জন্য ন্যূনতম কতগুলো মোজা বের করতে হবে? কবুতরের খোপ নীতি ( m = ২, প্রতি রঙের জন্য একটি করে খোপ ব্যবহার করে) অনুযায়ী, এটি হবে তিনটি ( n = ৩ ) মোজা। হয় একই রঙের তিনটি মোজা পাওয়া যাবে অথবা একটা রঙের দুটি এবং আরেকটি রঙের একটি মোজা পাওয়া যাবে।

করমর্দন

যদি n সংখ্যক লোক একে অপরের সাথে করমর্দন করে (যেখানে n > 1 ), তাহলে কবুতরের খোপ নীতি বলে যে এক্ষেত্রে অবশ্যই দুইজন লোক থাকবে যারা একই সংখ্যক লোকের সাথে করমর্দন করেছে। এখানে, প্রতিটি খোপ হচ্ছে একজন লোক কতজন লোকের সাথে করমর্দন করেছে তার সংখ্যা। যেহেতু প্রতিটি লোক ০ থেকে n − ১ সংখ্যক পর্যন্ত লোকের সাথে হাত মেলাতে পারে, সেহেতু n সংখ্যক সম্ভাব্য খোপ রয়েছে। অপরদিকে, হয় "০" চিহ্নিত খোপ বা "n − ১" চিহ্নিত খোপ, অথবা উভয়ই খালি হতে হবে। কেননা, যদি n > 1 হয়, তবে একজন লোকের পক্ষে সকল লোকের সাথে করমর্দন করা সম্ভব নয় যেখানে অপর একজন লোক কারো সাথেই করমর্দন করেনি। তাই, n সংখ্যক লোককে সর্বাধিক n − ১ সংখ্যক অশূন্য খোপে স্থাপন করা সম্ভব।

করমর্দনের এই উদাহরণটি 'একাধিক শীর্ষবিন্দুবিশিষ্টযেকোনো গ্রাফে যেখানে অন্তত এক জোড়া শীর্ষবিন্দু রয়েছে যাদের ডিগ্রি একই' -এর অনুরূপ। প্রতিটি লোকের সাথে একটি শীর্ষবিন্দুকে এবং প্রতিটি প্রান্তকে একটি করমর্দনের সাথে তুলনা করে দেখা যেতে পারে।

চুল গণনা

এই নীতি থেকে দেখানো যায় যে, ঢাকায় অবশ্যই অন্তত দুইজন লোকের মাথায় একই সংখ্যক চুল থাকবে। যেহেতু একজন স্বাভাবিক মানুষের মাথায় গড়ে প্রায় ১৫০,০০০ টি চুল থাকে; তাই এটা ধরে নেওয়া যুক্তিসঙ্গত (ঊর্ধ্বসীমা হিসাবে) যে, কারো মাথায় ১,০০০,০০০ টির বেশি চুল নেই (m = ১০ লক্ষ খোপ)। ঢাকায় ১,০০০,০০০-এর বেশি সংখ্যক লোক রয়েছে ( তাহলে n হলো ১০ লক্ষের চেয়ে বড়ো সংখ্যা)। যদি একজন ব্যক্তির মাথার প্রতিটি চুলের জন্য একটি করে কবুতরের খোপ বরাদ্দ করা হয় এবং তাদের মাথার চুলের সংখ্যা অনুযায়ী লোকেদেরকে কবুতরের খোপে দেওয়া হয় তাহলে ১,০০০,০০১তম বারে একই কবুতরের খোপে কমপক্ষে দুজন ব্যক্তি অবশ্যই থাকবে (কারণ হয় তাদের মাথায় একই সংখ্যক চুল রয়েছে অথবা, n > m )। ঢাকার জনসংখ্যা ২ কোটি ১০ লাখ ধরে নিলে, এই নীতি অনুযায়ী বলা যায় যে কমপক্ষে বাইশজন ঢাকাবাসীর সমান সংখ্যক চুল রয়েছে, কারণ ১০ লাখ কবুতরের খোপের প্রতিটিতে একুশজন ঢাকাবাসী রয়েছে ২১০ লাখ লোকের জন্য।

জন্মদিনের সমস্যা

জন্মদিনের সমস্যা জিজ্ঞাসা করে, n এলোমেলোভাবে নির্বাচিত ব্যক্তিদের একটি সেটের জন্য, তাদের মধ্যে কিছু জোড়ার একই জন্মদিন হওয়ার সম্ভাবনা কত? সমস্যাটি নিজেই প্রধানত কাউন্টারইন্ট্যুটিভ সম্ভাব্যতার সাথে সম্পর্কিত, তবে আমরা কবুতর হোল নীতির দ্বারা এটিও বলতে পারি যে 367 জনের মধ্যে, কমপক্ষে এক জোড়া লোক রয়েছে যারা 100% সম্ভাবনার সাথে একই জন্মদিন ভাগ করে নেয়, কারণ শুধুমাত্র 366 জন সম্ভাব্য জন্মদিন রয়েছে থেকে চয়ন করুন

দলের টুর্নামেন্ট

সাতজন লোকের কল্পনা করুন যারা দলগুলির একটি টুর্নামেন্টে খেলতে চায় (n = 7 টি আইটেম), শুধুমাত্র চারটি দল (m = 4 হোল) থেকে বেছে নিতে হবে। কবুতরের নীতি আমাদের বলে যে তারা সবাই বিভিন্ন দলের হয়ে খেলতে পারে না; সাতজন খেলোয়াড়ের মধ্যে অন্তত দুজনকে সমন্বিত অন্তত একটি দল থাকতে হবে:

$$\left\lfloor {\frac {n-1}{m}}\right\rfloor +1=\left\lfloor {\frac {7-1}{4}}\right\rfloor +1=\left\lfloor {\frac {6}{4}}\right\rfloor +1=1+1=2$$

উপসেট যোগফল

S = {1,2,3,...,9} সেট থেকে ছয় আকারের যেকোনো উপসেটে অবশ্যই দুটি উপাদান থাকতে হবে যার যোগফল 10। পায়রার ছিদ্রগুলিকে দুটি উপাদান উপসেট {1,9}, {2,8}, {3,7}, {4,6} এবং সিঙ্গলটন {5}, সব মিলিয়ে পাঁচটি কবুতর হোল দ্বারা লেবেল করা হবে৷ যখন এই কবুতরের মধ্যে ছয়টি "কবুতর" (আকার ছয় উপসেটের উপাদান) স্থাপন করা হয়, তখন প্রতিটি কবুতর যে কবুতরের গহ্বরে যায় তার লেবেলে থাকে, অন্তত একটি কবুতরের মধ্যে একটি দ্বি-উপাদানের উপসেটের লেবেলযুক্ত পায়রার মধ্যে দুটি থাকবে। এতে পায়রা

হ্যাশিং

কম্পিউটার বিজ্ঞানে হ্যাশিং হল একটি নির্বিচারে বৃহৎ ডেটা n থেকে m নির্দিষ্ট আকারের মানগুলিকে ম্যাপ করার প্রক্রিয়া। এটিতে ক্যাশিং -এর অ্যাপ্লিকেশন রয়েছে যার মাধ্যমে বৃহৎ ডেটা সেটগুলি তাদের প্রতিনিধি মানগুলির (তাদের "হ্যাশ কোড") একটি রেফারেন্স দ্বারা দ্রুত স্মরণের জন্য একটি "হ্যাশ টেবিলে" সংরক্ষণ করা যেতে পারে। সাধারণত, একটি ডেটা সেট n এ অনন্য বস্তুর সংখ্যা উপলব্ধ অনন্য হ্যাশ কোডের সংখ্যার চেয়ে বড় হয় m, এবং pigeonhole নীতিটি এই ক্ষেত্রে ধরে রাখে যে সেই বস্তুগুলিকে হ্যাশ করা স্বতন্ত্রতার কোন গ্যারান্টি নয়, যেহেতু আপনি যদি সমস্ত বস্তু হ্যাশ করেন ডেটা সেট n, কিছু অবজেক্ট অগত্যা একই হ্যাশ কোড শেয়ার করতে হবে।