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