Құтылар саны заттардан кем болса, кемінде бір құтыда екі зат болады

Кіріспе

Егер заттарды сақтауға арналған қораптардан заттар көп болса, онда кем дегенде бір қорапта екі немесе одан да көп зат болуы керек. Математикада, көгершін ұясы принципі бойынша, егер n зат m контейнерге салынатын болса, және n > m болса, онда кем дегенде бір контейнерде бір заттан артық болады. Мысалы, үш қолғаптың (олардың ешқайсысы оң және сол екі қолға да кигізілмейтін) кем дегенде екеуі оң қолға арналған немесе кем дегенде екеуі сол қолға арналған болуы керек, себебі үш нысан бар, бірақ оларды орналастыруға екі категория ғана бар. Бұл көзғалысқа түсінікті болатын тұжырым, санау аргументінің бір түрі, күтпеген нәтижелерді көрсету үшін қолданылуы мүмкін. Мысалы, Лондон халқының саны адам басындағы шаштың максималды санынан бір бірлік артық болса, онда принцип бойынша Лондонда шаштарының саны бірдей екі адам болуы керек. Бұл принцип 1624 жылы Жан Леурхонның кітабында айтылғанмен, көбінесе Дирихле қорап принципі немесе Дирихле сөре принципі деп аталады, өйткені 1834 жылы Питер Густав Лежун Дирихле осы принципті Schubfachprinzip ("қорап принципі" немесе "сөре принципі") деген атпен қарастырған. Принциптің бірнеше жалпылама түрлері бар және оны әртүрлі жолдармен тұжырымдауға болады. Квантитативті нұсқада: k және m табиғи сандары үшін, егер 1=n = km + 1 нысан m жиынға бөлінсе, көгершін ұясы принципі бойынша, кем дегенде бір жиында кем дегенде k + 1 нысан болады. Кез келген n және m үшін бұл келесідей жалпыланады: , мұндағы және сәйкесінше төмендеу және жоғарылау функцияларын білдіреді. Принциптің ең қарапайым қолданылуы – шекті жиындарға (мысалы, көгершін мен қораптар) болса да, ол бір-бірге сәйкес келмейтін шексіз жиындарға да қолданылады. Мұны істеу үшін көгершін ұясы принципінің формалды тұжырымы қажет: "кодоменасы доменасынан кіші инъективті функция жоқ". Сигель леммасы сияқты жоғары деңгейдегі математикалық дәлелдемелер осы жалпы ұғымға негізделген.

If there are more items than boxes holding them, one box must contain at least two items

In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. For example, of three gloves (none of which is ambidextrous/reversible), at least two must be right handed or at least two must be left handed, because there are three objects but only two categories of handedness to put them into. This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, given that the population of London is more than one unit greater than the maximum number of hairs that can be on a human's head, the principle requires that there must be at least two people in London who have the same number of hairs on their heads. Although the pigeonhole principle appears as early as 1624 in a book attributed to Jean Leurechon, it is commonly called Dirichlet's box principle or Dirichlet's drawer principle after an 1834 treatment of the principle by Peter Gustav Lejeune Dirichlet under the name Schubfachprinzip ("drawer principle" or "shelf principle"). The principle has several generalizations and can be stated in various ways. In a more quantified version: for natural numbers k and m, if 1=n = km + 1 objects are distributed among m sets, the pigeonhole principle asserts that at least one of the sets will contain at least k + 1 objects. For arbitrary n and m, this generalizes to , where and denote the floor and ceiling functions, respectively. Though the principle's most straightforward application is to finite sets (such as pigeons and boxes), it is also used with infinite sets that cannot be put into one to one correspondence. To do so requires the formal statement of the pigeonhole principle: "there does not exist an injective function whose codomain is smaller than its domain". Advanced mathematical proofs like Siegel's lemma build upon this more general concept.

Этимология

Дирихле өзінің еңбектерін француз және неміс тілдерінде жариялаған. Бұл терминдердің бастапқы мағынасы ағылшын тіліндегі «дәстүрлі жәшікке» (drawer) сәйкес келеді, яғни оны қамтитын шкафтан ішке-сыртқа жылға салатын ашық үстіңгі бөлігі бар қорап. (Дирихле шүмектерді жәшіктерге тарату туралы жазған.) Бұл терминдер көгершіндерге арналған құрылымдарға метафоралық түрде байланысты, үстелдегі, шкафтағы немесе қабырғадағы хаттар мен қағаздарды сақтауға арналған кішкентай ашық кеңістік ретінде өзгеріске ұшырады. Көбінесе жәшіктері бар жиһаздар көптеген санаттар бойынша нәрселерді сақтау немесе сұрыптау үшін қолданылады (мысалы, поштадағы хаттар немесе қонақүй бөлмелерінің кілттері), сондықтан «жәшік» аудармасы Дирихленің бастапқы «дәстүрлі жәшігінің» жақсырақ түсінігі болуы мүмкін. Жиһаздың ерекшеліктеріне қатысты «жәшік» терминінің түсінігі, әсіресе ағылшын тілін ана тілі ретінде емес, ғылыми әлемде лингва франка ретінде қолданатындар арасында, көгершіндер мен ойықтарды сөзбе-сөз бейнелейтін түсіндіруге қарай жоғалып барады. «Жәшік» сөзін «көгершін үйі» (dovecote) деп түсіндіру (бұл қате емес) соңғы кезде неміс тіліндегі «жәшік қағидасының» («pigeonhole principle») «Taubenschlagprinzip» деген кері аудармасына енді. «Schubfachprinzip» (неміс тілінде) және «Principe des tiroirs» (француз тілінде) бастапқы терминдерінен басқа, араб («مبدأ برج الحمام»), болгар («принцип на чекмеджетата»), қытай («抽屉原理»), даниялық («Skuffeprincippet»), голланд («ladenprincipe»), венгр («skatulyaelv»), итальян («principio dei cassetti»), жапон («引き出し論法»), парсы («اصل لانه کبوتری»), поляк («zasada szufladkowa»), португал («Princípio das Gavetas»), швед («Lådprincipen»), түрік («çekmece ilkesi»), вьетнам («nguyên lý hộp») тілдерінде де қолданылуда.

Шұлық теру

Мысалы, бір шулақ қорабында қара және көк шұлықтардың қоспасы бар делік, олардың әрқайсысын қандай да бір аяққа киюге болады. Сіз шулақ қорабынан бірнеше шұлықтарды қарамай-ақ тартып шығарасыз. Бір түсті жұпқа қол жеткізуге кепілдік беру үшін қанша шұлық тарту қажет? Көгершін бөлмесінің принципі бойынша (әр түс үшін бір бөлме пайдаланып), жауап үш (дана). Сіздің үш шұлығыңыз бір түсті болуы мүмкін, немесе бір түсті екі, ал екінші түсті біреуі болуы мүмкін.

Қол сілтеу

Егер n адам бір-бірімен қол алыса алатын болса (n > 1 болса), көгершін ойығы принципі әрқашан бірдей санда адаммен қол алысатын екі адам болатынын көрсетеді. Бұл принципті қолдануда, адамға тағайындалған "ұя" – сол адамның қол алысқан адамдар саны. Әрбір адам 0-ден n-1 дейінгі сандардағы адамдармен қол алыса алады, сондықтан n мүмкін ұя бар. Екінші жағынан, "0" ұясы, "n-1" ұясы немесе екеуі де бос болуы керек, себебі n > 1 болған жағдайда, бір адамның барлығымен қол алысуы және бір адамның ешкіммен қол алыспауы мүмкін емес. Бұл n адамды ең көп дегенде n-1 бос емес ұяға орналастыруға мүмкіндік береді, демек принцип қолданылады. Бұл қол алысу мысалы, бірден көп түйіні бар кез келген графта, бірдей дәрежеге ие кемінде екі түйін болатынына тең. Бұны әрбір адамды түйінмен және әр қабырғаны қол алысумен байланыстыру арқылы көруге болады.

Шашты санау

Бір адам Лондонда екі адамның басындағы шаштардың саны бірдей болуы керек екенін мысалы арқылы көрсетуге болады. Әдеттегі адам басында шаштарының орташа саны шамамен 150 000 болғандықтан, ешкімнің басында 1 000 000-нан астам шаш болмайды деп есептеу орынды (жоғарғы шек ретінде). Лондонда 1 000 000-нан астам адам бар (n 1 миллионнан астам). Әрбір шаш санына «көгершін тесігін» тағайындап, адамдарды басындағы шаштардың санына сәйкес «көгершін тесіктеріне» орналастырсақ, 1 000 001-ші адамды тағайындағанда кемінде екі адам бір «көгершін тесігіне» түседі (олардың басындағы шаштардың саны бірдей болғандықтан; немесе, n > m). Егер Лондонда 9,002 миллион адам болса, онда кем дегенде он лондондықтың шаштарының саны бірдей болады, себебі 1 миллион «көгершін тесігінің» әрқайсысында тоғыз лондондық болса, бұл тек 9 миллион адамды құрайды. Орташа жағдайда (l=m = 150 000), ең аз қайталану шектеуімен, әрбір «көгершін тесігіне» ең көп дегенде бір адам тағайындалады және 150 001-ші адам басқа біреумен бірдей «көгершін тесігіне» түседі. Бұл шектеу болмаған жағдайда бос «көгершін тесіктері» болуы мүмкін, өйткені «түйісу» 150 001-ші адамнан бұрын болады. Принцип тек түйісудің бар екенін дәлелдейді; ол түйісулердің саны туралы ештеңе айтпайды (бұл ықтималдық таралуының саласына жатады). Осы принциптің ағылшын тіліндегі сатиралық сілтемесі Афиналық қоғамның тарихында, Афиналық оракулға қосымша: Ескі афиналық меркурийлердегі қалған сұрақтар мен жауаптардың жинағы (Эндрю Белл үшін басылған, Лондон, 1710) кітабында кездеседі. Әлемде шаштарының саны бірдей екі адам бар ма деген сұрақ 1704 жылға дейін «Афиналық Меркурий» журналында көтерілген. Көгершін тесігі принципіне алғашқы жазбаша сілтеме француз иезуиті Жан Леурхонның 1622 жылғы Selectæ Propositiones еңбегіндегі қысқа сөйлемде кездеседі: толық принцип екі жылдан кейін, қосымша мысалдармен бірге, Леурхонға жатқызылатын басқа бір кітапта жазылған, бірақ оның шәкірттерінің бірі болуы мүмкін.

One can demonstrate there must be at least two people in London with the same number of hairs on their heads as follows. Since a typical human head has an average of around 150,000 hairs, it is reasonable to assume (as an upper bound) that no one has more than 1,000,000 hairs on their head holes). There are more than 1,000,000 people in London (n is bigger than 1 million items). Assigning a pigeonhole to each number of hairs on a person's head, and assigning people to pigeonholes according to the number of hairs on their heads, there must be at least two people assigned to the same pigeonhole by the 1,000,001st assignment (because they have the same number of hairs on their heads; or, n > m). Assuming London has 9.002 million people, it follows that at least ten Londoners have the same number of hairs, as having nine Londoners in each of the 1 million pigeonholes accounts for only 9 million people. For the average case (1=m = 150,000) with the constraint: fewest overlaps, there will be at most one person assigned to every pigeonhole and the 150,001st person assigned to the same pigeonhole as someone else. In the absence of this constraint, there may be empty pigeonholes because the "collision" happens before the 150,001st person. The principle just proves the existence of an overlap; it says nothing about the number of overlaps (which falls under the subject of probability distribution). There is a passing, satirical, allusion in English to this version of the principle in A History of the Athenian Society, prefixed to A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries (printed for Andrew Bell, London, 1710). It seems that the question whether there were any two persons in the World that have an equal number of hairs on their head? had been raised in The Athenian Mercury before 1704. Perhaps the first written reference to the pigeonhole principle appears in a short sentence from the French Jesuit Jean Leurechon's 1622 work Selectæ Propositiones: The full principle was spelled out two years later, with additional examples, in another book that has often been attributed to Leurechon, but might be by one of his students.

Баламалы пішіндер

Төменде "қоқыс ойығы" қағидасының басқа формулировкалары келтірілген. Егер n нысан m орынға таратылса және n > m болса, онда кем дегенде бір орын екі немесе одан көп нысанды қабылдайды. (4-тараудың жалпылауы) Егер S және T жиындар болса, және S жиынының кардиналдығы T жиынының кардиналдығынан кем болса, онда S-тен T-ге сюръективті функция жоқ.

Қатты түрі

Q1, q2, ..., qn оң бүтін сандар болсын. Егер нысандар n қорапқа бөлінсе, онда бірінші қорапта кем дегенде q1 нысан, немесе екінші қорапта кем дегенде q2 нысан, немесе n-ші қорапта кем дегенде qn нысан болады. Бұл қағидаттың қарапайым түрі 1=q1 = q2 = ... = qn = 2 деп алғанда алынады, бұл n + 1 нысанды береді. 1=q1 = q2 = ... = qn = r деп алғанда қағидаттың сандық нұсқасы пайда болады, атап айтқанда:

n және r оң бүтін сандар болсын. Егер n(r – 1) + 1 нысан n қорапқа бөлінсе, онда кем дегенде бір қорапта r немесе одан көп нысан болады. Бұны сондай-ақ, егер k дискретті нысан n контейнерге бөлінсе, онда кем дегенде бір контейнерде ⌈k/n⌉ нысан болады, мұнда ⌈x⌉ – төбе функциясы, x-тен үлкен немесе оған тең ең кіші бүтін санды білдіреді. Сол сияқты, кем дегенде бір контейнерде ⌊k/n⌋ нысаннан артық болмайды, мұнда ⌊x⌋ – еден функциясы, x-тен кіші немесе оған тең ең үлкен бүтін санды білдіреді.

Шексіз жиынтықтар

Клубшаңдық принципін шексіз жиындарға кардиналдық сандар арқылы тұжырымдау арқылы кеңейтуге болады: егер A жиынының кардиналдығы B жиынының кардиналдығынан артық болса, онда A-дан B-ға инъекциялық функция болмайды. Дегенмен, бұл тұжырым таутологиялық, себебі A жиынының кардиналдығы B жиынының кардиналдығынан артық деген сөздің мағынасы – A-дан B-ға инъективті функцияның жоқтығын білдіреді. Алайда, шекті жиынға кем дегенде бір элемент қосу кардиналдықтың өсуіне жеткілікті. Шекті жиындар үшін клубшаңдық принципін тұжырымдаудың тағы бір тәсілі – шекті жиындардың Дедекиндтік шектілігіне ұқсас: A және B – шекті жиындар болсын. Егер A-дан B-ға инъективті емес сюръекция болса, онда A-дан B-ға ешқандай сюръекция инъективті бола алмайды. Шындығында, A-дан B-ға дейінгі кез келген функция инъективті емес. Бұл шексіз жиындарға қатысты емес: мысалы, 1 мен 2-ні 1-ге, 3 және 4-ті 2-ге, 5 және 6-ны 3-қа және т.б. сәйкестендіретін натурал сандардағы функцияны қарастырайық. Шексіз жиындар үшін де ұқсас принцип бар: егер санаусыз көп көгершіндер санаулы көп ұяларға тығылса, онда кем дегенде бір ұяда санаусыз көп көгершіндер болады. Алайда, бұл принцип шекті жиындар үшін клубшаңдық принципінің жалпыламасы емес: ол шекті жиындар үшін жалған болуы мүмкін. Техникалық тұрғыдан алғанда, егер A және B – шекті жиындар болса және A-дан B-ға кез келген сюръективті функция инъективті болмаса, онда B жиынында b элементі бар, сонда b-ның кері бейнесі мен A жиыны арасында биекция бар. Бұл мүлдем басқа тұжырым және үлкен шекті кардиналдықтар үшін абсурдті.

Кванттық механика

Якир Ахаронов және басқалар кванттық механиканың көгершін тесігі принципін бұзу мүмкіндігін көрсетті және кванттық механикада көгершін тесігі принципін тексеру үшін интерферометриялық эксперименттер ұсынды. Кейінгі зерттеулер бұл қорытындыға күмән келтірді. 2015 жылғы қаңтарда arXiv препринтінде Бирмингем университетінің зерттеушілері Алястер Рей мен Тед Форган интерферометр арқылы әртүрлі энергиядағы электрондардың қозғалысын стандартты көгершін тесігі принципін қолдана отырып, теориялық толқындық функция арқылы талдады. Егер электрондардың өзара әрекеттесу күші болмаса, олардың әрқайсысы бір ғана, толыққанды дөңгелек пішіндегі шыңды құрар еді. Жоғары өзара әрекеттесу күші болғанда, әрбір электрон төрт түрлі шыңды құрайды, детекторда барлығы 12 шың пайда болады; бұл шыңдар әрбір электронның болуы мүмкін төрт өзара әрекеттесу түрінен туындайды (жеке, тек бірінші басқа бөлшектің қатысуымен, тек екінші басқа бөлшектің қатысуымен немесе үшеуінің бірдей қатысуымен). Егер өзара әрекеттесу күші төмен болса, көптеген нақты эксперименттердегідей, нөлдік өзара әрекеттесу үлгісінен ауытқу, мысалы, осы үлгілерді байқауға қолданылатын детекторлар сияқты, қатты денелердегі атомдардың кристалдық тор аралықтарынан әлдеқайда кіші болып, байқалмайтын болады. Бұл әлсіз, бірақ нөлдік емес өзара әрекеттесу күшін мүлдем өзара әрекеттесудің болмауынан ажыратуды өте қиын немесе мүмкін емес етеді, сондықтан үш электронның екі жолдан өтуіне қарамастан, өзара әрекеттеспегендігі туралы көрініс тудырады.