📜 Pigeonhole Principle (Дирихлеов Принцип)

## 💡 Дефиниција **Основна форма:** Ако $n+1$ гулаби треба да влезат во $n$ гнезда, тогаш барем во едно гнездо мора да има **најмалку 2 гулаба**. **Генерализирана форма:** Ако $kn+1$ објекти се распоредат во $n$ кутии, барем една кутија содржи $k+1$ објекти. --- ## 🧠 Интуиција Ова е принцип на "неизбежност" или "пренатрупаност". Замислете дека имате 3 пара чорапи (вкупно 6), а имате само 2 фиоки. Нема шанси да ги распоредите така што во секоја фиока да има само по 2 чорапи. Некаде мора да има повеќе. Тоа е најдобриот начин да се докаже дека нешто **постои**, без да мораме да го најдеме точно кој е. --- ## 📝 Доказ (Со контрадикција) Да претпоставиме спротивно: дека во секое од $n$-те гнезда има најмногу 1 гулаб. Тогаш, вкупниот број на гулаби би бил: $$\text{Вкупно} \le 1 + 1 + \dots + 1 = n$$ Но, ние имаме $n+1$ гулаби. Бидејќи $n+1 > n$, стигнавме до контрадикција. Значи, претпоставката е погрешна -> мора да има гнездо со повеќе од 1 гулаб. --- ## 🛠 Каде се користи? 1. **Геометрија:** "Во рамностран триаголник со страна 1 се фрлени 5 точки. Докажи дека две се на растојание помало од 0.5." (Тука гнездата се 4 мали триаголници). 2. **Теорија на броеви:** "Меѓу било кои $n+1$ броеви, постојат два чија разлика е делива со $n$." (Гнездата се остатоците при делење). 3. **Секојдневен живот:** "Во Скопје сигурно има двајца луѓе со ист број на влакна на главата." --- ## 🔗 Поврзани задачи - [Чорапи во фиока](../pre_olympiad/grade_6/logic/kengur_log_03.md)