051 — Pigeonhole Principle Problems¶
এবার একটা principle যেটা শুনতে এত সহজ যে প্রথমে গুরুত্ব বুঝবে না, কিন্তু এ দিয়ে এমন সব জিনিস প্রমাণ করা যায় যা গোনা প্রায় অসম্ভব। মূল কথা: n+1 টা পায়রা n টা খোপে ঢুকলে, কোনো-না-কোনো খোপে অন্তত 2টা থাকবেই — উপায় নেই। এটা গোনার সূত্র নয়, অস্তিত্বের গ্যারান্টি: "এমন কিছু অবশ্যই আছে" বলে দেয়, কোনটা না জেনেও। এই যুক্তির খেলাটাই interview-তে চমক দেখায়।
Source¶
- Original source: Classic combinatorics (pigeonhole principle)
- Platform: Classic combinatorics — https://discrete.openmathbooks.org/
- Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
- Difficulty: Medium
- Pattern: existence argument (pigeonhole)
- Basic idea inherited from: — (আলাদা শাখা: গোনা নয়, যুক্তি; আগের কোনো problem-এর সরাসরি সম্প্রসারণ নয়)
1. Problem in simple words¶
মূল principle (pigeonhole / কবুতর-খোপ):
যদি
nটা জিনিস (পায়রা)kটা খোপে রাখা হয় আরn > k, তাহলে অন্তত একটা খোপে 2টা বা তার বেশি জিনিস থাকবেই।
আরও সাধারণ রূপ: n জিনিস k খোপে হলে, কোনো খোপে অন্তত ⌈n/k⌉ টা থাকবেই (ceiling = উপরে গোল)।
এটা গোনার সমস্যা নয় — অস্তিত্ব প্রমাণের হাতিয়ার। typical problem: "প্রমাণ করো অন্তত দুজনের ... এক হবেই", বা "সবচেয়ে কম কয়টা জিনিস নিলে নিশ্চিত একটা জোড়া/মিল পাব?"
2. What is the math idea?¶
মূল idea — খোপের চেয়ে জিনিস বেশি হলে কোথাও ভিড় হবেই।
ধরো প্রতিটা খোপে বেশি-জোর 1টা করে রাখার চেষ্টা করি। তাহলে সর্বোচ্চ k টা জিনিস রাখা যায়। কিন্তু n > k মানে অন্তত একটা জিনিস "অতিরিক্ত" — তাকে কোনো-না-কোনো খোপে দ্বিতীয় হিসেবে ঢোকাতেই হবে।
পরিমাণগত রূপ (contrapositive): যদি প্রতিটা খোপে < m টা (মানে ≤ m−1) থাকত, মোট হতো ≤ k(m−1); তাই মোট > k(m−1) হলে কোনো খোপে ≥ m। বিশেষভাবে কোনো খোপে অন্তত ⌈n/k⌉।
3. Which basic idea does this inherit from?¶
এটা এই level-এর আলাদা একটা শাখা — আগের counting-formula গুলোর সরাসরি সম্প্রসারণ নয় (তাই "inherited from: —")। 039–050 ছিল "কত উপায়ে গোনা"; pigeonhole হলো "গোনা ছাড়াই কী অবশ্যই ঘটবে"।
তবে আত্মীয়তা আছে: খোপ বানানোর সময় প্রায়ই remainder/mod খোপ হিসেবে আসে (Level 2-এর ঘড়ি — mod n-এ ঠিক n টা খোপ)। আর "কতটা নিলে নিশ্চিত" হিসাবে ছোট গোনাও লাগে। কিন্তু মূল অস্ত্রটা নতুন: গণনার বদলে যুক্তি দিয়ে অস্তিত্ব প্রমাণ। পরের 052 (birthday paradox) এই খোপ-চিন্তারই সম্ভাবনা-রূপ, তাই 052 এর উপর দাঁড়ায়।
4. Real-life analogy¶
ভাবো তোমার মোজার ড্রয়ারে শুধু 2 রঙের মোজা মেশানো আছে — কালো আর সাদা (2টা "খোপ" = 2 রঙ)। অন্ধকারে রঙ না দেখে তুমি মোজা তুলছ। নিশ্চিতভাবে একটা মিলে-যাওয়া জোড়া পেতে সবচেয়ে কম কয়টা তুলতে হবে?
- 2টা তুললে? হতে পারে একটা কালো, একটা সাদা — জোড়া হলো না।
- 3টা তুললে? 3টা মোজা, 2 রঙ — pigeonhole বলছে কোনো-না-কোনো রঙে অন্তত 2টা পড়বেই → নিশ্চিত একটা জোড়া!
তাই উত্তর 3। লক্ষ করো — pigeonhole বলে না কোন রঙের জোড়া পাবে, শুধু বলে একটা জোড়া অবশ্যই আছে। এই "নিশ্চয়তা, কিন্তু কোনটা তা নয়" — principle-টার আসল চরিত্র।
5. Visual explanation¶
প্রথমে দেখো মূল ছবি — n+1 পায়রা n খোপে:
3 টা পায়রা, 2 টা খোপ:
খোপ A: [ 🕊 🕊 ] <- এখানে 2টা পড়তেই হলো!
খোপ B: [ 🕊 ]
যতই চেষ্টা করো, 3টা পায়রাকে 2 খোপে রাখলে
একটা খোপে অন্তত 2টা -> এড়ানো অসম্ভব
এবার ceiling-রূপ (n জিনিস, k খোপ → কোনো খোপে ≥ ⌈n/k⌉):
10 জিনিস, 3 খোপ -> ⌈10/3⌉ = 4
যতটা সমান ভাগের চেষ্টা: 4 + 3 + 3 = 10
^
কোনো একটা খোপে অন্তত 4 পড়বেই
(সব খোপে ≤3 হলে মোট ≤ 9 < 10 — অসম্ভব)
লক্ষ করো — সমান ভাগের সবচেয়ে ভালো চেষ্টা করেও সর্বোচ্চ খোপটা ⌈n/k⌉-এর নিচে নামানো যায় না।
6. Example input and output¶
প্রশ্ন -> উত্তর (যুক্তি)
----------------------
মিলে-যাওয়া জোড়া নিশ্চিত করতে কতটা তুলব (k রঙ)?
k=2 রঙ -> 3 (k+1)
k=5 রঙ -> 6
13 জন -> অন্তত 2 জনের জন্মমাস এক? -> হ্যাঁ (12 খোপ < 13)
12 জন -> একই গ্যারান্টি? -> না (12 = 12, প্রতি মাসে 1 সম্ভব)
guaranteed_in_one_hole(n, k) = ⌈n/k⌉:
(10, 3) -> 4 (10, 5) -> 2 (7, 7) -> 1
কতজন হলে নিশ্চিত 2 জনের mod-m remainder এক? -> m+1
m=7 -> 8
Edge case: জিনিস ≤ খোপ হলে কোনো গ্যারান্টি নেই (প্রতিটা আলাদা খোপে যেতে পারে)। "নিশ্চিত একটা মিল" পেতে লাগে খোপ + 1 টা জিনিস।
7. Brute force thinking¶
pigeonhole মূলত প্রমাণের অস্ত্র, কিন্তু "নিশ্চিত করতে কতটা লাগবে" — এটা সবচেয়ে খারাপ ক্ষেত্র (worst case) simulate করে যাচাই করা যায়:
def min_to_guarantee_pair_brute(num_colors):
# adversary সবচেয়ে দেরিতে জোড়া দিতে চায়:
# প্রথমে প্রতি রঙের 1টা করে তুলিয়ে দেয় (জোড়া এড়ায়), তারপর পরেরটায় জোড়া অনিবার্য
picked = num_colors # প্রতি রঙের 1টা: এখনো জোড়া নেই
return picked + 1 # পরের যেটাই হোক, কোনো রঙে 2টা
ভাবনাটা: "শত্রু" (adversary) যতটা সম্ভব জোড়া এড়াতে চাইলে প্রতি খোপে 1টা করে ভরবে; তার পরের জিনিসটাই জোড়া বাধাতে বাধ্য। এই worst-case গোনা pigeonhole-এর উত্তরই দেয়, আর ছোট case-এ সত্যিই বণ্টন simulate করে যাচাই করা যায়।
8. Why brute force may be slow¶
"কতটা লাগবে" উত্তর তো সরাসরি k+1 বা ⌈n/k⌉ — এর জন্য কিছু simulate করার দরকার নেই, একে একে চেষ্টা অপচয়।
আসল কথা ভিন্ন: অনেক pigeonhole প্রমাণের সমস্যায় "সব সম্ভাব্য বণ্টন check করে দেখা যে কোনোটাতেই জোড়া এড়ানো যায় না" — সেটা exponential:
n জিনিস k খোপে রাখার উপায় = k^n (বিশাল)
n=20, k=2 হলে 2^20 ≈ 10^6 বণ্টন check -> অহেতুক
pigeonhole যুক্তি: এক লাইনে "n > k তাই অসম্ভব" -> O(1)!
মানে অস্তিত্ব check-এ সব বণ্টন ঘোরা অসম্ভব, অথচ principle এক বাক্যে প্রমাণ দেয় — এটাই এর শক্তি।
9. Better thinking¶
মূল insight: গোনা বা simulate নয় — সঠিক "খোপ" সংজ্ঞায়িত করো, তারপর n > k দেখলেই গ্যারান্টি। কাজটা প্রায়ই দুই ধাপ: (১) খোপ কী? (২) পায়রা কী? — ঠিক করলে উত্তর এক লাইনে।
import math
def guaranteed_in_one_hole(n, k):
"""n জিনিস k খোপে -> কোনো খোপে অন্তত কতটা (⌈n/k⌉)।"""
if k <= 0:
raise ValueError("খোপ অন্তত 1টা লাগবে")
return math.ceil(n / k)
def min_items_to_guarantee_repeat(k):
"""k খোপে নিশ্চিত একটা খোপে 2টা পেতে কমপক্ষে কতটা = k + 1।"""
return k + 1
def min_items_for_count(k, m):
"""নিশ্চিত কোনো খোপে m টা পেতে কমপক্ষে কতটা = k(m−1) + 1।"""
return k * (m - 1) + 1
কঠিন pigeonhole-এ আসল চ্যালেঞ্জ "খোপ কী" বোঝা — যেমন remainder mod m, বা পার্থক্যের range।
10. Thinking tweak¶
আসল "আহা" মুহূর্ত: "নিশ্চিত / অবশ্যই / যেকোনোভাবেই / সবচেয়ে কম কয়টা হলে গ্যারান্টি" — এই শব্দগুলো দেখলেই pigeonhole ভাবো, আর প্রশ্ন করো: "খোপ কী, পায়রা কী?"
দুই tweak একসাথে গেঁথে নাও:
- খোপ খোঁজো: সম্ভাব্য মান কয় রকম হতে পারে? (রঙ, mod-remainder, range-bucket — এগুলোই খোপ।) খোপ সীমিত + জিনিস বেশি = মিল অনিবার্য।
- worst case ভাবো: "নিশ্চিত করতে কতটা?" = শত্রু সর্বোচ্চ এড়ালে কত লাগে = k(m−1) + 1।
এই "গোনার বদলে খোপ গুনে অস্তিত্ব প্রমাণ" চিন্তাটাই principle-টার পুরো শক্তি।
11. Step-by-step dry run¶
চলো ক্লাসিক প্রশ্ন: "কমপক্ষে কয়জন মানুষ থাকলে নিশ্চিত অন্তত 2 জনের জন্মমাস এক হবে?"
| ধাপ | চিন্তা | মান |
|---|---|---|
| 1 | খোপ কী? | জন্মমাস → 12 খোপ |
| 2 | পায়রা কী? | মানুষ |
| 3 | নিশ্চিত একটা মিল পেতে | খোপ + 1 = 12 + 1 |
| 4 | উত্তর | 13 জন |
যাচাই: 12 জন হলে প্রত্যেকে আলাদা মাসে সম্ভব (মিল নাও হতে পারে); 13তম জন যে মাসেই জন্মাক, সেটা আগের কারো সাথে মিলবেই → নিশ্চিত মিল ✓।
আরেকটা (mod): "কয়টা পূর্ণসংখ্যা নিলে নিশ্চিত 2টার পার্থক্য 7 দিয়ে ভাগ যাবে?" — খোপ = remainder mod 7 (7 রকম) → উত্তর 7+1 = 8।
12. Python solution¶
import math
from itertools import product
def guaranteed_in_one_hole(n, k):
"""n জিনিস k খোপে -> কোনো খোপে অন্তত ⌈n/k⌉ টা থাকবেই।"""
if k <= 0:
raise ValueError("খোপ অন্তত 1টা লাগবে")
return math.ceil(n / k)
def min_items_to_guarantee_repeat(k):
"""k খোপে নিশ্চিত একটা খোপে ≥2 পেতে কমপক্ষে কতটা = k + 1।"""
return k + 1
def min_items_for_count(k, m):
"""নিশ্চিত কোনো খোপে ≥ m পেতে কমপক্ষে কতটা = k(m−1) + 1।"""
return k * (m - 1) + 1
# --- brute force verifier ---
def must_have_repeat(n, k):
"""n জিনিস k খোপে রাখার *কোনো* উপায়ে কি জোড়া এড়ানো যায়?
এড়ানো গেলে False, না গেলে (সবসময় repeat) True। pigeonhole: n>k <=> True।"""
# প্রতিটা বণ্টন (প্রতি জিনিস কোন খোপে) ঘুরে দেখি কোনোটায় সব খোপে ≤1 কিনা
for assign in product(range(k), repeat=n):
counts = [0] * k
for box in assign:
counts[box] += 1
if max(counts) <= 1: # জোড়া এড়ানো গেল
return False
return True
def worst_case_picks_for_repeat(k):
"""simulate: adversary প্রতি খোপে 1টা ভরে (k টা), পরেরটায় repeat অনিবার্য।"""
return k + 1
# --- ছোট test গুলো (সব pass করা উচিত) ---
# ⌈n/k⌉ সঠিক কিনা
assert guaranteed_in_one_hole(10, 3) == 4
assert guaranteed_in_one_hole(10, 5) == 2
assert guaranteed_in_one_hole(7, 7) == 1
assert guaranteed_in_one_hole(13, 12) == 2 # 13 জন, 12 মাস
# "নিশ্চিত একটা জোড়া" = k + 1
assert min_items_to_guarantee_repeat(2) == 3 # 2 রঙ -> 3 মোজা
assert min_items_to_guarantee_repeat(12) == 13 # 12 মাস -> 13 জন
assert min_items_to_guarantee_repeat(7) == 8 # mod 7 -> 8 সংখ্যা
# "নিশ্চিত m টা" = k(m−1)+1
assert min_items_for_count(3, 4) == 10 # 3 খোপে নিশ্চিত 4 পেতে 10
assert min_items_for_count(2, 1) == 1
# pigeonhole মূল দাবি: n > k <=> repeat অনিবার্য (brute যাচাই, ছোট)
for k in range(1, 5):
for n in range(1, 8):
assert must_have_repeat(n, k) == (n > k)
# simulate-এর worst case == formula
for k in range(1, 8):
assert worst_case_picks_for_repeat(k) == min_items_to_guarantee_repeat(k)
print(guaranteed_in_one_hole(10, 3)) # 4
print(min_items_to_guarantee_repeat(12)) # 13
print(min_items_for_count(3, 4)) # 10
print("সব test pass!")
13. Line-by-line explanation¶
n জিনিস k খোপে সবচেয়ে সমানভাবে ভাগ করলেও সর্বোচ্চ খোপে ⌈n/k⌉ থাকবেই — মূল পরিমাণগত রূপ।
k খোপে প্রতিটায় 1টা রাখা গেলে k পর্যন্ত জোড়া এড়ানো যায়; (k+1)-তমটায় কোনো খোপে 2টা অনিবার্য।
প্রতি খোপে (m−1) পর্যন্ত রাখলে মোট k(m−1) — তাই এর চেয়ে 1 বেশি নিলে কোনো খোপে m অনিবার্য।
def must_have_repeat(n, k):
for assign in product(range(k), repeat=n):
... if max(counts) <= 1: return False
return True
verify-র brute — n জিনিস k খোপে রাখার সব উপায় ঘুরে দেখি কোনোটায় সব খোপে ≤1 (জোড়া এড়ানো) সম্ভব কিনা; না হলে repeat অনিবার্য। pigeonhole বলে এটা ঠিক n > k-তে True।
বাকি assert লাইনগুলো formula-কে brute যাচাই (n>k), worst-case simulate আর জানা case-এর সাথে মেলাচ্ছে। সব মিললে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম: guaranteed_in_one_hole(10, 3) = 4 (⌈10/3⌉)। দ্বিতীয়: min_items_to_guarantee_repeat(12) = 13 (জন্মমাস)। তৃতীয়: min_items_for_count(3, 4) = 10। আগের সব assert (formula বনাম brute n>k যাচাই, worst-case simulate) চুপচাপ pass করেছে। শেষে সব test pass!।
15. Time complexity¶
formula গুলো O(1) — সরাসরি গণিত (⌈n/k⌉, k+1, k(m−1)+1)। brute verifier must_have_repeat O(k^n · n) — সব বণ্টন ঘোরে, শুধু ছোট n-এ যাচাইয়ের জন্য। মূল principle-এর প্রয়োগ সবসময় O(1)।
16. Space complexity¶
formula O(1)। brute verifier O(k) — খোপের count রাখতে (একটা বণ্টন একবারে)।
17. Common mistakes¶
- খোপ ভুল গোনা — "খোপ কী?" ভুল বুঝলে পুরো যুক্তি ভুল; mod-remainder, রঙ, range-bucket — খোপ ঠিক চিহ্নিত করো।
- গড় (average) ভেবে ফেলা — pigeonhole অস্তিত্ব বলে (কোনো খোপে ≥⌈n/k⌉), গড় না; "কোন খোপ" তাও বলে না।
- n = k-এও গ্যারান্টি ভাবা — মিল নিশ্চিত হতে
n > kলাগে; ঠিক সমান হলে প্রতিটা আলাদা খোপে সম্ভব। - ⌈⌉ (ceiling) না নিয়ে floor নেওয়া — কোনো খোপে অন্তত কতটা = উপরে গোল;
n//k(floor) ভুল উত্তর দেয়। - "নিশ্চিত m টা" formula ভুল —
k(m−1)+1,kmনয়; প্রতি খোপে (m−1) পর্যন্ত এড়ানো যায়।
18. Harder problems that inherit this idea¶
- Classic — Erdős–Szekeres — যেকোনো (n²+1)-দৈর্ঘ্যের sequence-এ (n+1)-দৈর্ঘ্যের monotone subsequence আছে; pigeonhole-এর সুন্দর প্রয়োগ।
- 052 — Birthday Paradox Style (এই repo) — pigeonhole-এর সম্ভাবনা-রূপ ("নিশ্চিত" থেকে "সম্ভাব্য collision")।
- CP existence problems — "প্রমাণ করো এমন দুটো ... আছে যাদের যোগফল/পার্থক্য ... দিয়ে ভাগ যায়" — প্রায়ই mod-খোপে pigeonhole।
19. Pattern learned¶
Pigeonhole principle (existence via more items than holes) — n > k হলে কোনো খোপে ≥2; সাধারণভাবে কোনো খোপে ≥⌈n/k⌉; "নিশ্চিত একটা মিল" = k+1, "নিশ্চিত m টা" = k(m−1)+1। মূল signal: "নিশ্চিত / অবশ্যই / সবচেয়ে কম কয়টা হলে গ্যারান্টি" দেখলেই — খোপ কী, পায়রা কী?
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "pigeonhole: জিনিস > খোপ হলে কোথাও ভিড় অনিবার্য (≥⌈n/k⌉); নিশ্চিত জোড়া = k+1। 'নিশ্চিত/অবশ্যই' দেখলেই 'খোপ কী?' জিজ্ঞেস করো — এটা অস্তিত্বের গ্যারান্টি, গড় নয়।"
পরের ধাপ → 052 — Birthday Paradox Style Problems (একই খোপ-চিন্তার সম্ভাবনা-রূপ — collision কত তাড়াতাড়ি)।
ফিরে দেখা: concept ঝালাই → ../concept-notes.md · এই level-এর map → ../README.md · template → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।