পিজনহোল প্রিন্সিপল

The pigeonhole principle

৭ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

পিজনহোল প্রিন্সিপল — যদি $n+1$টি বস্তু $n$টি বাক্সে রাখা হয়, তাহলে অন্তত একটি বাক্সে ২টি বা তার বেশি বস্তু থাকবেই।
সাধারণীকৃত রূপ — $n$টি বস্তু $k$টি বাক্সে রাখলে, অন্তত একটি বাক্সে অন্তত $\lceil n/k \rceil$টি বস্তু থাকবে।
এটি গণনা করে না কোন বাক্সে বেশি আছে — শুধু প্রমাণ করে যে এমন একটি বাক্স অস্তিত্বশীল। এটিই এই কৌশলের আসল শক্তি।
উদাহরণ: যেকোনো ১৩ জন মানুষের মধ্যে অন্তত ২ জনের জন্মমাস একই হবেই ($\lceil 13/12 \rceil = 2$)।

এই পাঠে যা শিখবেন

পিজনহোল প্রিন্সিপলের বেসিক ও সাধারণীকৃত (generalized) রূপ
কীভাবে একটি "কোনো নির্দিষ্ট উত্তর ছাড়া অস্তিত্ব-প্রমাণ" তৈরি করতে হয়
জন্মমাস উদাহরণ ও একটি Ramsey-ধাঁচের মজার ফ্যাক্ট
Python দিয়ে পিজনহোল প্রিন্সিপল সিমুলেট ও যাচাই করা

১ · বেসিক পিজনহোল প্রিন্সিপল

পিজনহোল প্রিন্সিপলPigeonhole Principleযদি $n+1$টি বস্তুকে $n$টি বাক্সে রাখা হয়, তাহলে অন্তত একটি বাক্সে অন্তত ২টি বস্তু থাকবেই। নাম এসেছে "কবুতরের বাসা"র (pigeonhole) রূপক থেকে — $n+1$টি কবুতরকে $n$টি বাসায় রাখলে অন্তত একটি বাসায় দুইটি কবুতর গাদাগাদি করতে হবে। দেখতে খুবই সহজ — প্রায় "সাধারণ জ্ঞান" মনে হয়। কিন্তু এটি গণিতের সবচেয়ে শক্তিশালী অস্তিত্ব-প্রমাণ (existence proof) কৌশলগুলোর একটি — এটি বলে দেয় কিছু একটা থাকবেই, কিন্তু কী বা কোথায় তা বলে না।

মূল বিবৃতি

$n+1$টি বস্তু $n$টি বাক্সে রাখলে, অন্তত একটি বাক্সে $\geq 2$টি বস্তু থাকবে। প্রমাণ সরাসরি বিরোধিতা (contradiction) দিয়ে হয়: যদি প্রতিটি বাক্সে সর্বোচ্চ ১টি বস্তু থাকত, তাহলে মোট বস্তু সংখ্যা সর্বোচ্চ $n$ হতো — কিন্তু আমাদের কাছে $n+1$টি বস্তু আছে, যা একটি স্ববিরোধ।

২ · সাধারণীকৃত রূপ

যদি $n$টি বস্তু $k$টি বাক্সে রাখা হয়, তাহলে অন্তত একটি বাক্সে অন্তত $\lceil n/k \rceil$টি (সিলিং ফাংশন — পরবর্তী পূর্ণসংখ্যায় রাউন্ড আপ) বস্তু থাকবে। এটি বেসিক রূপেরই একটি সরাসরি সম্প্রসারণ।

ক্লাসিক উদাহরণ: যেকোনো ১৩ জন মানুষের একটি দলে, অন্তত ২ জনের জন্মমাস একই হবেই। এখানে "বস্তু" হলো মানুষ ($n=13$) এবং "বাক্স" হলো মাস ($k=12$)। $\lceil 13/12 \rceil = 2$, তাই অন্তত একটি মাসে অন্তত ২ জনের জন্ম হবেই।

৪টি বস্তু ৩টি বাক্সে রাখলে অন্তত একটি বাক্সে অন্তত ২টি বস্তু থাকবেই — এখানে বাক্স ১।

Python

from collections import Counter

# ১৩ জন মানুষের জন্মমাস (নির্দিষ্ট, deterministic তালিকা)
months = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1]  # ১৩টি এন্ট্রি, ১২টি সম্ভাব্য মাস

counts = Counter(months)

print("প্রতিটি মাসে জন্ম নেওয়া মানুষের সংখ্যা:")
for month in sorted(counts):
    print(f"মাস {month}: {counts[month]} জন")

max_count = max(counts.values())
print("\nসর্বোচ্চ একই মাসে জন্ম নেওয়া মানুষের সংখ্যা:", max_count)
print("পিজনহোল প্রিন্সিপল সন্তুষ্ট (অন্তত একটি মাসে >= 2 জন):", max_count >= 2)

এই কোড ১৩ জনের একটি নির্দিষ্ট (deterministic) জন্মমাসের তালিকা ব্যবহার করে — যাতে Pyodide-এ প্রতিবার Run করলে একই ফলাফল পুনরুৎপাদনযোগ্য থাকে। বাস্তবে ১৩ জনের যেকোনো তালিকাতেই মাস ১-এ (অথবা অন্য কোনো মাসে) অন্তত ২ জন পাওয়া যাবে — এটিই পিজনহোল প্রিন্সিপলের নিশ্চয়তা।

৩ · একটি মজার, গভীর ফ্যাক্ট

পিজনহোল প্রিন্সিপল আরও গভীর ফলাফলেও ব্যবহৃত হয়। একটি বিখ্যাত (Ramsey থিওরির) ফ্যাক্ট: যেকোনো ৬ জনের একটি দলে, হয় ৩ জন এমন আছে যারা একে অপরকে সবাই চেনে, অথবা ৩ জন এমন আছে যাদের কেউ কাউকে চেনে না। এই ফলাফলটি ($R(3,3)=6$ নামে পরিচিত) পিজনহোল প্রিন্সিপল ব্যবহার করেই প্রমাণ করা যায় — আমরা এখানে পূর্ণ প্রমাণে না গিয়ে শুধু এটিকে একটি চমকপ্রদ তথ্য হিসেবে উল্লেখ করছি।

মূল কথা · Key takeaway

পিজনহোল প্রিন্সিপল "কোথায়" বা "কী" তা না বলেও "কিছু একটা অবশ্যই ঘটবে" প্রমাণ করার একটি অত্যন্ত সাধারণ কৌশল। পরের পাঠে (L16) আমরা দেখব যখন একাধিক সেট ওভারল্যাপ করে, তখন সঠিকভাবে গোনার জন্য ইনক্লুশন-এক্সক্লুশন প্রিন্সিপল কীভাবে কাজে লাগে — যা এই মডিউলের কাউন্টিং নিয়মগুলোর আরেকটি গুরুত্বপূর্ণ হাতিয়ার।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ একটি ড্রয়ারে ১০টি লাল ও ১০টি নীল মোজা আলাদা করা ছাড়াই রাখা আছে। অন্ধকারে হাত দিয়ে মোজা তুলতে হলে, একই রঙের একজোড়া মোজা নিশ্চিত পেতে সর্বনিম্ন কতটি মোজা তুলতে হবে?

মূল উত্তর — ৩টি। এখানে "বাক্স" হলো ২টি রঙ (লাল, নীল), আর "বস্তু" হলো তোলা মোজা। যদি ২টি মোজা তোলা হয়, সবচেয়ে খারাপ ক্ষেত্রে দুটোই ভিন্ন রঙের হতে পারে (১টি লাল, ১টি নীল) — তখনও জোড়া মেলেনি। কিন্তু ৩টি মোজা তুললে, পিজনহোল প্রিন্সিপল অনুযায়ী ($3$ বস্তু, $2$ বাক্স, $\lceil 3/2 \rceil=2$), অন্তত একটি রঙে অন্তত ২টি মোজা থাকবেই — অর্থাৎ একজোড়া নিশ্চিত।

প্র ০২ কেন পিজনহোল প্রিন্সিপল আমাদের বলে না কোন বাক্সে অতিরিক্ত বস্তু আছে, শুধু বলে যে এমন একটি বাক্স আছে? এটি কি এই কৌশলের একটি দুর্বলতা?

এটি দুর্বলতা নয়, বরং পিজনহোল প্রিন্সিপলের প্রকৃতিই এমন — এটি একটি অস্তিত্ব-প্রমাণ (non-constructive existence proof), যা প্রমাণ করে দেয় "এমন কিছু অবশ্যই আছে" বিরোধিতার মাধ্যমে, কোনো নির্মাণ (construction) ছাড়াই। বাস্তবে অনেক গাণিতিক সত্য এভাবেই প্রমাণিত হয় — অস্তিত্ব প্রমাণ করাই যথেষ্ট, নির্দিষ্ট উদাহরণ খুঁজে বের করা আলাদা (এবং প্রায়ই অনেক কঠিন) একটি সমস্যা।

প্র ০৩ একটি $8 \times 8$ চেকারবোর্ডের ৬৫টি বিন্দু (প্রতিটি বর্গের কেন্দ্রের বাইরে, যেকোনো অবস্থানে) চিহ্নিত করা হলো। কেন অন্তত দুটি বিন্দু একই বর্গে পড়বেই?

একটি $8 \times 8$ বোর্ডে মোট $8 \times 8 = 64$টি বর্গ (বাক্স) আছে। আমাদের কাছে ৬৫টি বিন্দু (বস্তু) আছে — যা বাক্সের সংখ্যার চেয়ে ১টি বেশি। পিজনহোল প্রিন্সিপলের বেসিক রূপ ($n+1$ বস্তু, $n$ বাক্স) সরাসরি প্রযোজ্য: অন্তত একটি বর্গে অন্তত ২টি বিন্দু পড়বেই, কারণ প্রতিটি বর্গে সর্বোচ্চ ১টি বিন্দু রাখলে সর্বোচ্চ $64$টি বিন্দু ধরানো সম্ভব — ৬৫টি নয়।

অনুশীলন

গণনা করুন: একটি স্কুলে ৩৭০ জন শিক্ষার্থী আছে। প্রমাণ করুন অন্তত ২ জন শিক্ষার্থীর জন্মদিন একই দিনে (মাস+দিন) হবেই (একটি বছরে সর্বোচ্চ ৩৬৬ দিন, লিপ ইয়ারসহ)।

"বাক্স" হলো বছরের সম্ভাব্য দিন ($k=366$, লিপ ইয়ারসহ), "বস্তু" হলো শিক্ষার্থী ($n=370$)। যেহেতু $370 > 366$, বেসিক পিজনহোল প্রিন্সিপল ($n+1$ বস্তু, $n$ বাক্স রূপের সম্প্রসারণ) সরাসরি প্রয়োগ করে বলা যায় অন্তত একটি দিনে অন্তত ২ জনের জন্মদিন পড়বেই ($\lceil 370/366 \rceil = 2$)।
যাচাই করুন: উপরের কোড সেলে months তালিকাটি পরিবর্তন করে ২৫ জনের একটি তালিকা বানান (মাস ১-১২ পুনরাবৃত্তি করে), তারপর Run চেপে দেখুন সর্বোচ্চ কত জনের মাস একই হয়।

২৫ জনের জন্য $\lceil 25/12 \rceil = 3$, তাই অন্তত একটি মাসে অন্তত ৩ জনের জন্ম নিশ্চিত। আপনার নির্দিষ্ট তালিকার উপর নির্ভর করে বাস্তব সর্বোচ্চ সংখ্যা এর চেয়ে বেশিও হতে পারে, কিন্তু পিজনহোল প্রিন্সিপল শুধু নিম্নসীমা (guaranteed minimum) নিশ্চিত করে, প্রকৃত মান নয়।