Дирихлегийн зарчим

Дирихлегийн зарчим (Герман: Schubfachprinzip - хайрцагны зарчим, Англи: Pigeonhole principle - тагтааны үүрний зарчим) — комбинаторикт, хэрвээ n ширхэг зүйлийг (объектийг) m ширхэг хайрцганд хийхэд, n>m бол, дор хаяж нэг хайрцаг нэгээс их зүйлийг агуулна. Энэ нь гарцаагүй үнэн зарчим бөгөөд бодит амьдралд "гурван бээлийний аль нэг хоёр нь заавал баруун эсвэл зүүн гарынх байна", "арван тагтааг (n=10, объект) есөн үүрэнд (m=9, хайрцаг) багтаавал, дор хаяж нэг үүрэнд нэгээс илүү тагтаа байна" гэдгээр батлагдана. Маш энгийн юм шиг боловч Дирихлегийн зарчмаар боломжгүй мэт зүйлүүдийг тооцоолж болно. Жишээ нь, Улаанбаатарын иргэдийн хоёрынх нь үсний тоо ижил гэдгийг (доор үзэх). Математикийн чухал энэ зарчмыг 1834 онд германы математикч Дирихле тодорхойлсон.

9 үүр 10 тагтаа, Дирихлегийн зарчмын дагуу бол ядаж (дор хаяж) нэг үүр нэгээс илүү тагтааг агуулна.

Төгсгөлтэй олонлог (жишээ нь, тагтаа ба тагтааны үүр) энэ зарчмыг хэрэглэж болох хамгийн энгийн жишээ бөгөөд, түүнийг шууд тодорхойлох боломжгүй төгсгөлгүй олонлог дээр мөн ашигладаг.

Жишээ

Хөл бөмбөгийн багийн гишүүд

Хэрвээ 5 хүн (5-н объект, n=5) хөл бөмбөгийн 4 багаас (4-н хайрцаг, m=4) сонгон тоглохоор болжээ. Тэгвэл Дирихлегийн зарчмын дагуу тэдгээр 5 хүн бүгд өөр өөр багт орон тоглох боломжгүй юм. Тэдний дор хаяж 2 нь нэг багт орж тоглоно.

Ижил оймс

Танд хар ба хөх өнгөтэй оймс холилдсон байна гэж үзье. Тэгвэл хамгийн багадаа хэдэн оймс авахад тэр дотор нэг өнгийн хос оймс байх нь гарцаагүй вэ? Хэрвээ өнгийг хайрцаг (m=2) гэвэл, Дирихлегийн зарчмын дагуу таны авах оймсны тоо 3 (n=3) байна.

Гар барилт

Бусадтайгаа гар барих боломжтой n хүн байгаа гэвэл Дирихлегийн зарчмын дагуу эдгээр хүмүүсийн дотор ижил тооны хүнтэй гар барьсан хоёр хүн ямагт байх болно. Хайрцаг буюу m нь баригдсан гарын тоо ба хүн тус бүр бусдын гарыг 0-с n-1 удаа барих боломжтой тул, боломжит хайрцагны тоо n-1 юм. 0-с n-1 хүртэл n боломж байхад яагаад хайрцагны тоо n-1 гэж. Учир нь, 0 дугаар эсвэл n-1 дүгээр хайрцагны аль нэг заавал хоосон байна. Яагаад гэвэл, хэрэв хэн нэгэн бусад бүх хүнтэй гар барьсан бол, нэг ч хүнтэй гар бариагүй хүн байх боломжгүй. Иймд, n хүнийг m=n-1 хайрцаганд багтаавал аль нэг хайрцганд хоёр хүн орох нь гарцаагүй юм.

Үсний тоо

Улаанбаатарын иргэд дотор үсний тоо ижилтэй дор хаяж хоёр хүн байгаа гэдгийг бид харуулж болно. Ердийн хүний толгой ойролцоогоор 150,000 үстэй байдаг бол, 1 саяас илүү тооны үстэй хүн байхгүй гэж үзэхэд буруутах зүйл байхгүй болов уу. Тэгвэл, m=1 сая хайрцаг. Улаанбаатар 1 саяас илүү хүн амтай. Тэгвэл n > m = 1сая болно. Хүмүүсийг үснийх нь тоогоор хайрцаглавал Улаанбаатарын иргэний тоог 1,000,001 гэж үзэхэд л дор хаяж нэг хайрцаганд хоёр хүн орно. Толгой дахь үсний тоог дундаж үзүүлэлтээр нь m=150,000 гэж үзвэл, Дирихлегийн зарчмын дагуу 150,001 дэх хүнээс эхлээд үсний тооны давхцал үүсэж эхэлнэ. Гэтэл давхцал 150,001 дэх хүнд хүрэхээс өмнө үүсэж болно. Учир нь, зарим нэг хайрцаг хоосон байж болно (тийм тооны үстэй хүн байхгүй). Дирихлегийн зарчим нь давхцал байгаа гэдгийг баталдаг боловч, давхцалын тооны тухай юуг ч өгүүлдэггүй юм. Давхцал нь магадлалын тархалт сэдэвт хамаарна.

Төрсөн өдрийн бодлого

Санамсаргүйгээр сонгон авсан хүмүүсийн хоёрынх нь төрсөн өдөр ижил байна. Дирихлегийн зарчмын дагуу бол өрөөнд байгаа 367 (n) хүний дор хаяж хоёр нь нэг өдөр төрсөн байна. Учир нь жилд 366 хоног (хоёрдугаар сарын 29-г оруулбал) байдаг.

Хэрэглээ

Дирихлегийн зарчим нь компьютерийн шинжлэх ухаанд ажиглагддаг. Жишээ нь, хэш хүснэгтэд давхцал үүсэх нь тодорхой юм. Учир нь боломжит түлхүүрийн тоо нь дараалал дахь индексийн тооноос их. Хэш алгоритм нь хэдий ухаантай ч давхцалыг тойрч чадахгүй.

The principle can be used to prove that any lossless compression algorithm, provided it makes some inputs smaller (as the name compression suggests), will also make some other inputs larger. Otherwise, the set of all input sequences up to a given length L could be mapped to the (much) smaller set of all sequences of length less than L, and do so without collisions (because the compression is lossless), which possibility the pigeonhole principle excludes.

A notable problem in mathematical analysis is, for a fixed irrational number a, to show that the set {[na]: n is an integer} of fractional parts is dense in [0, 1]. One finds that it is not easy to explicitly find integers n, m such that |na − ma| < e, where e > 0 is a small positive number and a is some arbitrary irrational number. But if one takes M such that 1/M < e, by the pigeonhole principle there must be n₁, n₂ ∈ {1, 2, ..., M + 1} such that n₁a and n₂a are in the same integer subdivision of size 1/M (there are only M such subdivisions between consecutive integers). In particular, we can find n₁, n₂ such that n₁a is in (p + k/M, p + (k + 1)/M), and n₂a is in (q + k/M, q + (k + 1)/M), for some p, q integers and k in {0, 1, ..., M − 1}. We can then easily verify that (n₂ − n₁)a is in (q − p − 1/M, q − p + 1/M). This implies that [na] < 1/M < e, where n = n₂ − n₁ or n = n₁ − n₂. This shows that 0 is a limit point of {[na]}. We can then use this fact to prove the case for p in (0, 1]: find n such that [na] < 1/M < e; then if p ∈ (0, 1/M], we are done. Otherwise p in (j/M, (j + 1)/M], and by setting k = sup{r ∈ N : r[na] < j/M}, one obtains |[(k + 1)na] − p| < 1/M < e.

Тодорхойлолт

9 үүр 7 тагтаа, Дирихлегийн зарчмын дагуу бол ядаж (дор хаяж) нэг үүр 7/9-с ихгүй, ө.х. 0 тагтааг агуулна.

Зарчмын ерөнхий тодорхойлолт нь: m контейнеруудад тараан байрлуулсан n объектийн хувьд дор хаяж нэг контейнер, дор хаяж ${\displaystyle \lceil n/m\rceil }$ объектийг агуулна. Үүнд, ${\displaystyle \lceil x\rceil }$ нь дээвэр функц ба х-с их эсвэл тэнцүү хамгийн бага бүхэл тоо. Үүнтэй адилаар, дор хаяж нэг контейнер ${\displaystyle \lfloor n/m\rfloor }$-с ихгүй объектийг агуулна. Үүнд, ${\displaystyle \lfloor x\rfloor }$ нь шал функц ба х-с бага эсвэл тэнцүү хамгийн их бүхэл тоо. Дирихлегийн зарчмыг магадлалаар нь тодорхойлбол n тагтаа санамсаргүйгээр m үүрэнд ${\displaystyle 1/m}$ магадлалтайгаар орвол, дор хаяж нэг үүр нэгээс илүү тагтааг

${\displaystyle 1-{\frac {(m)_{n}}{m^{n}}},\!}$ магадлалтайгаар агуулна.

Үүнд: (m)_n нь буурах факториал m(m − 1)(m − 2)...(m − n + 1). n=0 ба n=1 (m>0) үед магадлал 0-тэй тэнцүү. Мэдээж хэрэг нэг тагтаанд асуудал гарахгүй. n>m үед Дирихлегийн ердийн зарчимд нийцнэ. n≤m үед ч давхцал (нэг үүрэнд нэгээс илүү тагтаа байх) үүсэх магадлалтай. Учир нь тагтаа санамсаргүйгээр үүрэнд орж байгаа. Жишээ нь, 2 тагтаа 4 үүрний хувьд дор хаяж нэг үүр, нэгээс илүү тагтаа агуулах магадлал нь 25%; 5 тагтаа 10 үүрний хувьд энэ магадлал нь 69,76%; 10 тагтаа 20 үүрний хувьд энэ нь 93,45% тус тус байна. Үүрний тоо тогтмол байхад тагтааны тоог ихэсгэх тусам нэг үүрэнд хоёр тагтаа байх магадлал ихэснэ. Төрсөн өдрийн парадоксд энэ асуудал дэлгэрэнгүй тайлбарлагдана.

Энэ математикийн тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.