„Anglono“ žodynas:
pigeonhole
1 uoksas/urvas uoloje, kuriame karvelis suka lizdą
2 dėžutė (prie sienos); (rašomojo stalo) skyrelis (dokumentams, korespondencijai)
3 (klasifikavimo) skyrelis
***
1 (iš)dėlioti (popierius) į stalčiukus/dėžutes
3 klasifikuoti, skirstyti;
***
Pigeonhole principle (Wikipedija)
A probabilistic generalization of the pigeonhole principle states that if n pigeons are randomly put into m pigeonholes with uniform probability 1/m, then at least one pigeonhole will hold more than one pigeon with probability
P(A)= 1 – (m(m − 1)(m − 2)…(m − n + 1))/m^n.
For n = 0 and for n = 1 (and m > 0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For n > m (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of pigeonholes (n ≤ m), due to the random nature of the assignment of pigeons to pigeonholes there is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. If the number of holes stays fixed, there is always a greater probability of a pair when you add more pigeons. This problem is treated at much greater length at birthday paradox.
*
A further probabilistic generalisation is that when a real-valued random variable X has a finite mean E(X), then the probability is nonzero that X is greater than or equal to E(X), and similarly the probability is nonzero that X is less than or equal to E(X). To see that this implies the standard pigeonhole principle, take any fixed arrangement of n pigeons into m holes and let X be the number of pigeons in a hole chosen uniformly at random. The mean of X is n/m, so if there are more pigeons than holes the mean is greater than one. Therefore, X is sometimes at least 2.
***
Kaip gaunama formulė?
Pastebėkime, kad sąlygoje yra frazė „bent vienas [narvelis, urvelis, stalčiukas…]“, todėl pritaikome priešingo įvykio tikimybės skaičiavimo formulę:
P(A) = 1 – P(neA).
„neA“ šiuo atveju yra įvykis, kad kiekvienas balandis patenka į tuščią narvelį. Kiekvienas iš m balandžių gali skristi į bet kurį iš n narvelių – taip gauname vardiklio formulę. Pirmasis balandis gali pasirinkti vieną iš m narvelių, antrasis – vieną iš (m-1) likusių tuščių narvelių ir t.t. – taip gauname skaitiklio formulę.
***
Labai tinka egzaminui, tiesa?
P.S. Rašoma ir Pigeon Hole…
Atsakymai
Justas, 2010-10-21 23:32:14
Vis dėl to nusprendžiau atsiversti šį puslapį ir paskaityti apie PIGEONGOLE ne dėl to, kad Jūs kaip sakėte “galiu paklausti apie tai prieš egzaminą”, bet dėl smalsumo. Kas čia tokio svarbaus ir įdomaus, kad tai būtų klausiama. Nejaugi tai reiškia, kad pradėjau domėtis?
Burgis, 2010-10-22 14:36:54
Justui: jei pradėjote domėtis, tai reiškia, kad pradėjote domėtis. Bet jei rašote tik tam, kad paklaustumėte, ar pradėjote domėtis, tai reiškia, kad nepradėjote domėtis…
studentė, 2010-10-23 10:34:58
aš ne iš smalsumo vėl sugrįžau prie pigeonhole principo, sakau vėl nes jau domėjausi šiuo principu, o gal tik Jūsų dėstytojau įtakota peržvelgiau akimis nieko neįsidėdama į galvą, tačiau dabar kai jau nebelieka kitos išeities tik studijuoti pačiai ir Me jau nebetoli pagaliau susidomėjau ir netgi supratau:)
Ačiū Jums
Ramunas, 2011-09-14 22:18:31
Gerb. B. Burgi, Kaip manote kurioje loterijoje didesne tikimybe laimeti? Teleloto ar Vikingu LOTO? Ir gal galite parasyti kokios tikimybes laimeti butent didyji priza?
Burgis, 2011-09-15 09:41:47
Ramūnui: aš nesidomiu loterijomis, bet su studentais galiu išspręsti tą uždavinį, jei kas nors tiksliai suformuluos sąlygą.