# 051 — Pigeonhole Principle Problems

> এবার একটা principle যেটা শুনতে এত সহজ যে প্রথমে গুরুত্ব বুঝবে না, কিন্তু এ দিয়ে এমন সব জিনিস **প্রমাণ** করা যায় যা গোনা প্রায় অসম্ভব। মূল কথা: n+1 টা পায়রা n টা খোপে ঢুকলে, কোনো-না-কোনো খোপে অন্তত 2টা থাকবেই — উপায় নেই। এটা গোনার সূত্র নয়, **অস্তিত্বের গ্যারান্টি**: "এমন কিছু অবশ্যই আছে" বলে দেয়, কোনটা না জেনেও। এই যুক্তির খেলাটাই interview-তে চমক দেখায়।

<div class="problem-source" markdown="1">

<p class="source-label" id="source">Problem link ও উৎস</p>

- **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-এর সরাসরি সম্প্রসারণ নয়)

</div>

## প্রশ্ন ও উদাহরণ {#problem}

### সহজ করে প্রশ্ন {#1-problem-in-simple-words}

মূল principle (pigeonhole / কবুতর-খোপ):

> যদি `n` টা জিনিস (পায়রা) `k` টা খোপে রাখা হয় আর `n > k`, তাহলে অন্তত একটা খোপে **2টা বা তার বেশি** জিনিস থাকবেই।

আরও সাধারণ রূপ: `n` জিনিস `k` খোপে হলে, কোনো খোপে অন্তত **⌈n/k⌉** টা থাকবেই (ceiling = উপরে গোল)।

এটা গোনার সমস্যা নয় — **অস্তিত্ব প্রমাণের** হাতিয়ার। typical problem: "প্রমাণ করো অন্তত দুজনের ... এক হবেই", বা "সবচেয়ে কম কয়টা জিনিস নিলে নিশ্চিত একটা জোড়া/মিল পাব?"

### Input ও output {#6-example-input-and-output}

```text
প্রশ্ন -> উত্তর (যুক্তি)
----------------------
মিলে-যাওয়া জোড়া নিশ্চিত করতে কতটা তুলব (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` টা জিনিস।

### চেনা উদাহরণে বোঝা {#4-real-life-analogy}

ভাবো তোমার মোজার ড্রয়ারে শুধু **2 রঙের** মোজা মেশানো আছে — কালো আর সাদা (2টা "খোপ" = 2 রঙ)। অন্ধকারে রঙ না দেখে তুমি মোজা তুলছ। নিশ্চিতভাবে একটা **মিলে-যাওয়া জোড়া** পেতে সবচেয়ে কম কয়টা তুলতে হবে?

- 2টা তুললে? হতে পারে একটা কালো, একটা সাদা — জোড়া হলো না।
- **3টা** তুললে? 3টা মোজা, 2 রঙ — pigeonhole বলছে কোনো-না-কোনো রঙে অন্তত 2টা পড়বেই → নিশ্চিত একটা জোড়া!

তাই উত্তর 3। লক্ষ করো — pigeonhole বলে না কোন রঙের জোড়া পাবে, শুধু বলে **একটা জোড়া অবশ্যই আছে**। এই "নিশ্চয়তা, কিন্তু কোনটা তা নয়" — principle-টার আসল চরিত্র।

## ভিত্তির ধারণা {#idea}

### আগের কোন ধারণাটি লাগবে {#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 এর উপর দাঁড়ায়।

### ভেতরের অঙ্ক {#2-what-is-the-math-idea}

মূল idea — **খোপের চেয়ে জিনিস বেশি হলে কোথাও ভিড় হবেই।**

ধরো প্রতিটা খোপে বেশি-জোর 1টা করে রাখার চেষ্টা করি। তাহলে সর্বোচ্চ `k` টা জিনিস রাখা যায়। কিন্তু `n > k` মানে অন্তত একটা জিনিস "অতিরিক্ত" — তাকে কোনো-না-কোনো খোপে দ্বিতীয় হিসেবে ঢোকাতেই হবে।

পরিমাণগত রূপ (contrapositive): যদি **প্রতিটা** খোপে `< m` টা (মানে ≤ m−1) থাকত, মোট হতো `≤ k(m−1)`; তাই মোট `> k(m−1)` হলে কোনো খোপে `≥ m`। বিশেষভাবে কোনো খোপে অন্তত `⌈n/k⌉`।

## ধাপে ধাপে সমাধান {#walkthrough}

### প্রথম সরল উপায় {#7-brute-force-thinking}

pigeonhole মূলত প্রমাণের অস্ত্র, কিন্তু "নিশ্চিত করতে কতটা লাগবে" — এটা **সবচেয়ে খারাপ ক্ষেত্র (worst case) simulate** করে যাচাই করা যায়:

```python
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:

```text
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 দেখলেই গ্যারান্টি।** কাজটা প্রায়ই দুই ধাপ: (১) খোপ কী? (২) পায়রা কী? — ঠিক করলে উত্তর এক লাইনে।

```python
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-টার পুরো শক্তি।

### ছবিতে বোঝা {#5-visual-explanation}

প্রথমে দেখো মূল ছবি — n+1 পায়রা n খোপে:

```text
3 টা পায়রা, 2 টা খোপ:

খোপ A: [ 🕊 🕊 ]   <- এখানে 2টা পড়তেই হলো!
খোপ B: [ 🕊    ]

যতই চেষ্টা করো, 3টা পায়রাকে 2 খোপে রাখলে
একটা খোপে অন্তত 2টা -> এড়ানো অসম্ভব
```

এবার ceiling-রূপ (n জিনিস, k খোপ → কোনো খোপে ≥ ⌈n/k⌉):

```text
10 জিনিস, 3 খোপ -> ⌈10/3⌉ = 4

যতটা সমান ভাগের চেষ্টা: 4 + 3 + 3 = 10
                        ^
              কোনো একটা খোপে অন্তত 4 পড়বেই
(সব খোপে ≤3 হলে মোট ≤ 9 < 10 — অসম্ভব)
```

লক্ষ করো — সমান ভাগের সবচেয়ে ভালো চেষ্টা করেও সর্বোচ্চ খোপটা ⌈n/k⌉-এর নিচে নামানো যায় না।

### ছোট input-এ ধাপে ধাপে {#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।

## কোড ও ব্যাখ্যা {#code}

### Python {#12-python-solution}

```python
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}

```text
def guaranteed_in_one_hole(n, k):
    return math.ceil(n / k)
```

n জিনিস k খোপে সবচেয়ে সমানভাবে ভাগ করলেও সর্বোচ্চ খোপে `⌈n/k⌉` থাকবেই — মূল পরিমাণগত রূপ।

```text
def min_items_to_guarantee_repeat(k):
    return k + 1
```

k খোপে প্রতিটায় 1টা রাখা গেলে k পর্যন্ত জোড়া এড়ানো যায়; (k+1)-তমটায় কোনো খোপে 2টা অনিবার্য।

```text
def min_items_for_count(k, m):
    return k * (m - 1) + 1
```

প্রতি খোপে (m−1) পর্যন্ত রাখলে মোট k(m−1) — তাই এর চেয়ে 1 বেশি নিলে কোনো খোপে m অনিবার্য।

```text
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!`।

### Output মিলিয়ে দেখা {#14-output-walkthrough}

চালালে যা ছাপবে:

```text
4
13
10
সব test pass!
```

প্রথম: `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!`।

## খরচ ও সাধারণ ভুল {#cost}

### সময় {#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}

1. **খোপ ভুল গোনা** — "খোপ কী?" ভুল বুঝলে পুরো যুক্তি ভুল; mod-remainder, রঙ, range-bucket — খোপ ঠিক চিহ্নিত করো।
2. **গড় (average) ভেবে ফেলা** — pigeonhole **অস্তিত্ব** বলে (কোনো খোপে ≥⌈n/k⌉), গড় না; "কোন খোপ" তাও বলে না।
3. **n = k-এও গ্যারান্টি ভাবা** — মিল নিশ্চিত হতে `n > k` লাগে; ঠিক সমান হলে প্রতিটা আলাদা খোপে সম্ভব।
4. **⌈⌉ (ceiling) না নিয়ে floor নেওয়া** — কোনো খোপে অন্তত কতটা = **উপরে** গোল; `n//k` (floor) ভুল উত্তর দেয়।
5. **"নিশ্চিত m টা" formula ভুল** — `k(m−1)+1`, `km` নয়; প্রতি খোপে (m−1) পর্যন্ত এড়ানো যায়।

## শেখা ও পরের অনুশীলন {#practice}

### এই ধারণার পরের অনুশীলন {#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](052-birthday-paradox-style.md) (একই খোপ-চিন্তার সম্ভাবনা-রূপ — collision কত তাড়াতাড়ি)।

ফিরে দেখা: concept ঝালাই → [../concept-notes.md](../concept-notes.md) · এই level-এর map → [../README.md](../README.md) · template → [../../../templates/math-problem-note-template.md](../../../templates/math-problem-note-template.md)।

---

> **মনে রাখার নিয়ম (legal):** সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।