3261:. If the electrons had no interaction strength at all, they would each produce a single, perfectly circular peak. At high interaction strength, each electron produces four distinct peaks, for a total of 12 peaks on the detector; these peaks are the result of the four possible interactions each electron could experience (alone, together with the first other particle only, together with the second other particle only, or all three together). If the interaction strength was fairly low, as would be the case in many real experiments, the deviation from a zero-interaction pattern would be nearly indiscernible, much smaller than the
2996:), 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 in the
1029:
329:
956:= {1,2,3,...,9} must contain two elements whose sum is 10. The pigeonholes will be labeled by the two element subsets {1,9}, {2,8}, {3,7}, {4,6} and the singleton {5}, five pigeonholes in all. When the six "pigeons" (elements of the size six subset) are placed into these pigeonholes, each pigeon going into the pigeonhole that has it contained in its label, at least one of the pigeonholes labeled with a two-element subset will have two pigeons in it.
729:) 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
3999:
20:
67:, 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
618:), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. In this application of the principle, the "hole" to which a person is assigned is the number of hands that person shakes. Since each person shakes hands with some number of people from 0 to
940:
708:
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
785:
randomly chosen people, what is the probability that some pair of them will have the same birthday? The problem itself is mainly concerned with counterintuitive probabilities, but we can also tell by the pigeonhole principle that among 367 people, there is at least one pair of people who share the
3265:
of atoms in solids, such as the detectors used for observing these patterns. This would make it very difficult or impossible to distinguish a weak-but-nonzero interaction strength from no interaction whatsoever, and thus give an illusion of three electrons that did not interact despite all three
570:
Suppose a drawer contains a mixture of black socks and blue socks, each of which can be worn on either foot. You pull a number of socks from the drawer without looking. What is the minimum number of pulled socks required to guarantee a pair of the same color? By the pigeonhole principle
1562:
816:
3989:
3611:"A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries. ... To which is Prefix'd the History of the Athenian Society, ... By a Member of the Athenian Society"
1696:
75:
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.
1399:
719:). 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.
3194:
There is a similar principle for infinite sets: If uncountably many pigeons are stuffed into countably many pigeonholes, there will exist at least one pigeonhole having uncountably many pigeons stuffed into it.
2182:
767:, or other things, as each other." 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.
1997:
2082:
227:
1925:
3987:
987:
whereby large data sets can be stored by a reference to their representative values (their "hash codes") in a "hash table" for fast recall. Typically, the number of unique objects in a data set
1314:
2521:
2986:(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 (
2911:
1863:
1754:
388:
in the scientific world—in favor of the more pictorial interpretation, literally involving pigeons and holes. The suggestive (though not misleading) interpretation of "pigeonhole" as "
3988:
1017:
algorithm, provided it makes some inputs smaller (as "compression" suggests), will also make some other inputs larger. Otherwise, the set of all input sequences up to a given length
810:
holes) to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be at least one team featuring at least two of the seven players:
253:
1119:
1236:
279:
376:
Because furniture with pigeonholes is commonly used for storing or sorting things into many categories (such as letters in a post office or room keys in a hotel), the translation
2787:
2191:, a version that mixes finite and infinite sets is used: If infinitely many objects are placed into finitely many boxes, then two objects share a box. In Fisk's solution to the
2813:
2717:
2743:
2232:
1369:
1181:
3198:
This principle is not a generalization of the pigeonhole principle for finite sets however: It is in general false for finite sets. In technical terms it says that if
3639:"The Athenian Oracle: Being an Entire Collection of All the Valuable Questions and Answers in the Old Athenian Mercuries. ... By a Member of the Athenian Society"
3191:
is injective. This is not true for infinite sets: Consider the function on the natural numbers that sends 1 and 2 to 1, 3 and 4 to 2, 5 and 6 to 3, and so on.
935:{\displaystyle \left\lfloor {\frac {n-1}{m}}\right\rfloor +1=\left\lfloor {\frac {7-1}{4}}\right\rfloor +1=\left\lfloor {\frac {6}{4}}\right\rfloor +1=1+1=2}
999:, and the pigeonhole principle holds in this case that hashing those objects is no guarantee of uniqueness, since if you hashed all objects in the data set
1589:
37:
holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon. (The top left hole has 2 pigeons.)
1557:{\displaystyle n_{1}a\in \left(p+{\frac {k}{M}},\ p+{\frac {k+1}{M}}\right),\quad n_{2}a\in \left(q+{\frac {k}{M}},\ q+{\frac {k+1}{M}}\right),}
3249:
experiments to test the pigeonhole principle in quantum mechanics. Later research has called this conclusion into question. In a
January 2015
2093:
1935:
2008:
4122:
148:
4004:
3305:
694:
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
4079:
3848:
1872:
3939:
3914:
3896:
742:
A Supplement to the
Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries
3300:
2188:
1243:
3957:
3682:(October 1976). "Combinatorial problems, some old, some new and all newly attacked by computer". Mathematical Games.
3567:
3515:
3488:
3461:
384:, referring to some furniture features, is fading—especially among those who do not speak English natively but as a
4127:
2455:
755:
Perhaps the first written reference to the pigeonhole principle appears in a short sentence from the French Jesuit
3257:
analysis, employing the standard pigeonhole principle, on the flight of electrons at various energies through an
2858:
3155:
Another way to phrase the pigeonhole principle for finite sets is similar to the principle that finite sets are
1025:
without collisions (because the compression is lossless), a possibility that the pigeonhole principle excludes.
3152:. However, adding at least one element to a finite set is sufficient to ensure that the cardinality increases.
1815:
1706:
104:
The principle has several generalizations and can be stated in various ways. In a more quantified version: for
92:
2285:
places in such a way that no place receives more than one object, then each place receives exactly one object.
4042:
4032:
646:) for some person to shake hands with everybody else while some person shakes hands with nobody. This leaves
232:
1075:
1203:
663:
258:
3253:
preprint, researchers
Alastair Rae and Ted Forgan at the University of Birmingham performed a theoretical
2976:), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For
4037:
2758:
4050:
2792:
2688:
1055:
lattice without any three being colinear – in this case, 16 pawns on a regular chessboard
4023:
3638:
3624:
2722:
2208:
1345:
301:
4061:
3285:
2372:
places in such a way that no place receives no object, then each place receives exactly one object.
1041:
730:
392:" has lately found its way back to a German back-translation of the "pigeonhole principle" as the "
3610:
1138:
4096:
3862:
Rae, Alastair; Forgan, Ted (2014-12-03). "On the implications of the
Quantum-Pigeonhole Effect".
3280:
746:
whether there were any two persons in the World that have an equal number of hairs on their head?
4132:
4117:
3562:. Translated by Holl, Winifred A. K. Paul, Trench, Trubner & Company, Limited. p. 72.
365:
304:. To do so requires the formal statement of the pigeonhole principle: "there does not exist an
72:
3582:
To avoid a slightly messier presentation, this example only refers to people who are not bald.
786:
same birthday with 100% probability, as there are only 366 possible birthdays to choose from.
3557:
3295:
1798:. This shows that 0 is a limit point of {}. One can then use this fact to prove the case for
1060:
671:
667:
3060:. To see that this implies the standard pigeonhole principle, take any fixed arrangement of
4019:
3802:
3397:
1014:
690:
with the same number of hairs on their heads as follows. Since a typical human head has an
380:
may be a better rendering of
Dirichlet's original "drawer". That understanding of the term
313:
130:
sets, the pigeonhole principle asserts that at least one of the sets will contain at least
3721:, Cambridge Tracts in Theoretical Computer Science, 2nd Edition, Joseph O'Rourke, page 9.
3625:"The Athenian Oracle being an entire collection of all the valuable questions and answers"
8:
4091:
4072:
3684:
3320:
3310:
3290:
2400:
2192:
548:
518:
333:
3806:
16:
If there are more items than boxes holding them, one box must contain at least two items
4068:
3928:
3863:
3825:
3790:
3689:
3592:
3401:
2317:
736:
There is a passing, satirical, allusion in
English to this version of the principle in
468:
428:
305:
3791:"Quantum violation of the pigeonhole principle and the nature of quantum correlations"
71:, can be used to demonstrate possibly unexpected results. For example, given that the
3953:
3935:
3910:
3892:
3830:
3563:
3511:
3484:
3457:
3315:
3242:
3230:. This is a quite different statement, and is absurd for large finite cardinalities.
3133:
2930:
1691:{\displaystyle (n_{2}-n_{1})a\in \left(q-p-{\frac {1}{M}},q-p+{\frac {1}{M}}\right).}
1064:
488:
317:
3405:
363:. (Dirichlet wrote about distributing pearls among drawers.) These terms morphed to
3820:
3810:
3383:
3375:
3094:, so if there are more pigeons than holes the mean is greater than one. Therefore,
2997:
2746:
968:
776:
538:
528:
498:
478:
438:
286:
79:
Although the pigeonhole principle appears as early as 1624 in a book attributed to
4054:
3505:
3478:
3451:
3393:
3275:
3262:
3156:
3113:
3004:
1128:
1124:
508:
448:
418:
414:
339:
Dirichlet published his works in both French and German, using either the German
3923:
3786:
3679:
3258:
3246:
3238:
2852:, then at least one pigeonhole will hold more than one pigeon with probability
2816:
1021:
could be mapped to the (much) smaller set of all sequences of length less than
756:
458:
282:
105:
80:
4086:
3379:
3363:
4111:
3254:
1377:
such subdivisions between consecutive integers). In particular, one can find
1028:
964:
385:
68:
3815:
3834:
3388:
3109:
3078:
be the number of pigeons in a hole chosen uniformly at random. The mean of
675:
361:
open-topped box that can be slid in and out of the cabinet that contains it
328:
297:
3424:
2833:
A probabilistic generalization of the pigeonhole principle states that if
371:
small open space in a desk, cabinet, or wall for keeping letters or papers
2301:
42:
4069:
Pigeonhole
Principle from Interactive Mathematics Miscellany and Puzzles
3693:
3532:
2244:
The following are alternative formulations of the pigeonhole principle.
355:
353:. The strict original meaning of these terms corresponds to the English
348:
4007:
was created from a revision of this article dated 5 June 2021
293:
674:. This can be seen by associating each person with a vertex and each
662:
This hand-shaking example is equivalent to the statement that in any
3418:
Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "
2177:{\displaystyle {\Bigl |}{\bigl }-p{\Bigr |}<{\frac {1}{M}}<e.}
744:(printed for Andrew Bell, London, 1710). It seems that the question
3849:"Quantum pigeonholes are not paradoxical after all, say physicists"
3419:
389:
309:
3868:
3003:
A further probabilistic generalization is that when a real-valued
1992:{\displaystyle p\in \left({\frac {j}{M}},{\frac {j+1}{M}}\right],}
4100:
4057:
investigates interpretations and reformulations of the principle.
3709:, Peter Linz, pp. 115–116, Jones and Bartlett Learning, 2006
3136:, since the meaning of the statement that the cardinality of set
2077:{\displaystyle k=\sup \left\{r\in N:r<{\frac {j}{M}}\right\},}
984:
691:
19:
4064:"; Elementary examples of the principle in use by Larry Cusick.
3930:
1131:
in . One finds that it is not easy to explicitly find integers
794:
Imagine seven people who want to play in a tournament of teams
763:: "It is necessary that two men have the same number of hairs,
687:
222:{\displaystyle k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil }
3784:
3754:
In the lead section this was presented with the substitutions
2828:
764:
292:
Though the principle's most straightforward application is to
3654:
3250:
670:, there is at least one pair of vertices that share the same
2755:. Similarly, at least one container must hold no more than
2632:
gives the more quantified version of the principle, namely:
631:
possible holes. On the other hand, either the "0" hole, the
3222:
such that there exists a bijection between the preimage of
3013:
2685:
containers, then at least one container must hold at least
971:
is the process of mapping an arbitrarily large set of data
3364:"The pigeonhole principle, two centuries before Dirichlet"
2187:
Variants occur in a number of proofs. In the proof of the
1005:, some objects must necessarily share the same hash code.
373:, metaphorically rooted in structures that house pigeons.
1920:{\displaystyle p\in {\bigl (}0,{\tfrac {1}{M}}{\bigr ]},}
993:
is larger than the number of available unique hash codes
686:
One can demonstrate there must be at least two people in
2819:, denoting the largest integer smaller than or equal to
2749:, denoting the smallest integer larger than or equal to
702:
holes). There are more than 1,000,000 people in London (
578:, using one pigeonhole per color), the answer is three (
4071:"; basic Pigeonhole Principle analysis and examples by
3425:
Earliest Known Uses of Some of the Words of
Mathematics
3206:
are finite sets such that any surjective function from
3593:"London's Population / Greater London Authority (GLA)"
3533:"D3 Graph Theory - Interactive Graph Theory Tutorials"
2213:
1896:
1835:
1726:
1350:
1208:
1194:
is some arbitrary irrational number. But if one takes
639:
hole, or both must be empty, for it is impossible (if
4087:"How Many Humans Have the Same Number of Body Hairs?"
2861:
2795:
2761:
2725:
2691:
2458:
2211:
2096:
2011:
1938:
1875:
1818:
1709:
1592:
1402:
1348:
1246:
1206:
1141:
1078:
819:
261:
235:
151:
3785:
Aharonov, Yakir; Colombo, Fabrizio; Popescu, Sandu;
3245:may violate the pigeonhole principle, and proposed
3183:is injective. In fact no function of any kind from
2532:boxes, then either the first box contains at least
3927:
3428:. Electronic document, retrieved November 11, 2006
2905:
2807:
2781:
2737:
2711:
2515:
2226:
2176:
2076:
1991:
1919:
1857:
1748:
1690:
1556:
1363:
1309:{\displaystyle n_{1},n_{2}\in \{1,2,\ldots ,M+1\}}
1308:
1230:
1175:
1113:
1045:for the number of points that can be placed on an
934:
709:have the same number of hairs on their heads; or,
296:(such as pigeons and boxes), it is also used with
273:
247:
221:
2147:
2099:
1032:The pigeonhole principle gives an upper bound of
417:, other literal translations are still in use in
4109:
3043:, and similarly the probability is nonzero that
2570:The simple form is obtained from this by taking
2270:, then some place receives at least two objects.
2018:
552:
522:
4080:16 fun applications of the pigeonhole principle
3855:
3795:Proceedings of the National Academy of Sciences
3789:; Struppa, Daniele C.; Tollaksen, Jeff (2016).
3688:. Vol. 235, no. 4. pp. 131–137.
3214:is not injective, then there exists an element
3175:that is not injective, then no surjection from
3144:is exactly that there is no injective map from
2664:boxes, then at least one of the boxes contains
611:people can shake hands with one another (where
472:
432:
4082:"; Interesting facts derived by the principle.
3361:
3167:be finite sets. If there is a surjection from
2203:boxes, then there is a box containing at most
492:
4051:The strange case of The Pigeon-hole Principle
3904:
3707:Introduction to Formal Languages and Automata
3437:
2541:objects, or the second box contains at least
2516:{\displaystyle q_{1}+q_{2}+\cdots +q_{n}-n+1}
2134:
2106:
1909:
1884:
802:items), with a limitation of only four teams
542:
532:
502:
482:
442:
4099:from the original on 2021-12-11 – via
3340:
3338:
3336:
3108:The pigeonhole principle can be extended to
2802:
2796:
2776:
2762:
2732:
2726:
2706:
2692:
1340:are in the same integer subdivision of size
1303:
1273:
1108:
1079:
1013:The principle can be used to prove that any
983:fixed-size values. This has applications in
512:
452:
422:
408:
402:
393:
346:
340:
268:
262:
242:
236:
216:
202:
190:
164:
96:
91:after an 1834 treatment of the principle by
3362:Rittaud, Benoît; Heeffer, Albrecht (2014).
3357:
3355:
3353:
2906:{\displaystyle 1-{\frac {(m)_{n}}{m^{n}}},}
2829:Generalizations of the pigeonhole principle
2239:
659:non-empty holes, so the principle applies.
462:
101:("drawer principle" or "shelf principle").
3449:
1240:by the pigeonhole principle there must be
3952:, Waltham: Blaisdell Publishing Company,
3867:
3861:
3824:
3814:
3651:
3476:
3387:
3333:
3132:. However, in this form the principle is
1858:{\displaystyle <{\tfrac {1}{M}}<e;}
1749:{\displaystyle <{\tfrac {1}{M}}<e,}
1104:
4015:, and does not reflect subsequent edits.
3998:
3947:
3922:
3905:Fletcher, Peter; Patty, C.Wayne (1987),
3666:
3350:
3344:
2679:discrete objects are to be allocated to
1027:
1008:
327:
18:
3886:
3742:
3730:
3678:
3555:
3140:is greater than the cardinality of set
3120:is greater than the cardinality of set
3026:, then the probability is nonzero that
770:
248:{\displaystyle \lfloor \cdots \rfloor }
4110:
1114:{\displaystyle \{:n\in \mathbb {Z} \}}
320:build upon this more general concept.
3503:
2845:pigeonholes with uniform probability
2357:, then some place receives no object.
1231:{\displaystyle {\tfrac {1}{M}}<e,}
316:". Advanced mathematical proofs like
274:{\displaystyle \lceil \cdots \rceil }
3477:Weintraub, Steven H. (17 May 2017).
3306:Hilbert's paradox of the Grand Hotel
3233:
1583:}. One can then easily verify that
950:Any subset of size six from the set
2782:{\displaystyle \lfloor k/n\rfloor }
2310:is greater than the cardinality of
2189:pumping lemma for regular languages
503:
423:
13:
3985:
3530:
3124:, then there is no injection from
2360:(equivalent formulation of 4) If
2273:(equivalent formulation of 1) If
1929:the proof is complete. Otherwise
789:
14:
4144:
3966:
3907:Foundations of Higher Mathematics
3301:Dirichlet's approximation theorem
2808:{\displaystyle \lfloor x\rfloor }
2712:{\displaystyle \lceil k/n\rceil }
2387:are sets, and the cardinality of
738:A History of the Athenian Society
652:people to be placed into at most
23:Pigeons in holes. Here there are
4123:Theorems in discrete mathematics
3997:
3934:(3rd ed.), Addison-Wesley,
3241:et al. presented arguments that
3103:
2393:is less than the cardinality of
681:
3841:
3778:
3748:
3736:
3724:
3712:
3700:
3672:
3660:
3656:, Gasparem Bernardum, p. 2
3645:
3631:
3617:
3603:
3585:
3576:
3450:Zimmermann, Karl-Heinz (2006).
2738:{\displaystyle \lceil x\rceil }
2673:This can also be stated as, if
2227:{\displaystyle {\tfrac {n}{k}}}
2195:a sort of converse is used: If
1478:
1364:{\displaystyle {\tfrac {1}{M}}}
1190:is a small positive number and
600:
565:
3891:(5th ed.), Pentice Hall,
3549:
3524:
3497:
3470:
3443:
3431:
3412:
3368:The Mathematical Intelligencer
2878:
2871:
2839:pigeons are randomly put into
2419:
2123:
2111:
2050:
2041:
1828:
1819:
1719:
1710:
1619:
1593:
1160:
1143:
1091:
1082:
179:
167:
126:objects are distributed among
93:Peter Gustav Lejeune Dirichlet
1:
3880:
3504:James, R. C. (31 July 1992).
2658:objects are distributed into
2526:objects are distributed into
2366:objects are distributed over
2341:objects are distributed over
2279:objects are distributed over
2254:objects are distributed over
945:
3887:Brualdi, Richard A. (2010),
3116:: if the cardinality of set
3032:is greater than or equal to
1176:{\displaystyle |na-m|<e,}
401:Besides the original terms "
332:Pigeon-hole messageboxes at
323:
89:Dirichlet's drawer principle
7:
4038:Encyclopedia of Mathematics
3719:Computational Geometry in C
3559:The Psychology of Reasoning
3269:
3266:passing through two paths.
3112:by phrasing it in terms of
560:
10:
4149:
3889:Introductory Combinatorics
3745:, p. 74 Theorem 3.2.1
959:
589:of one color, or you have
4062:The Pigeon Hole Principle
4033:"Dirichlet box principle"
3556:Rignano, Eugenio (1923).
3438:Fletcher & Patty 1987
3380:10.1007/s00283-013-9389-1
3100:is sometimes at least 2.
3049:is less than or equal to
2647:be positive integers. If
2556:th box contains at least
2449:be positive integers. If
2375:(generalization of 4) If
2288:(generalization of 1) If
493:
443:
433:
302:one-to-one correspondence
85:Dirichlet's box principle
3948:Herstein, I. N. (1964),
3652:Leurechon, Jean (1622),
3422:". In Jeff Miller (ed.)
3326:
3286:Combinatorial principles
2670:or more of the objects.
2240:Alternative formulations
2199:objects are placed into
1042:no-three-in-line problem
731:probability distribution
585:items). Either you have
300:that cannot be put into
83:, it is commonly called
4128:Mathematical principles
3816:10.1073/pnas.1522411112
1070:, to show that the set
434:принцип на чекмеджетата
137:objects. For arbitrary
3993:
3973:Listen to this article
3507:Mathematics Dictionary
2907:
2809:
2783:
2739:
2713:
2517:
2228:
2178:
2078:
1993:
1921:
1859:
1750:
1692:
1558:
1365:
1310:
1232:
1177:
1115:
1056:
936:
722:For the average case (
553:
543:
533:
523:
513:
484:principio dei cassetti
483:
473:
463:
453:
409:
403:
394:
347:
341:
336:
275:
249:
223:
145:, this generalizes to
97:
38:
3992:
3296:Dedekind-infinite set
2908:
2810:
2784:
2740:
2714:
2550:objects, ..., or the
2518:
2229:
2179:
2079:
1994:
1922:
1860:
1751:
1693:
1559:
1366:
1311:
1233:
1178:
1116:
1061:mathematical analysis
1059:A notable problem in
1031:
1009:Uses and applications
937:
761:Selectæ Propositiones
524:Princípio das Gavetas
331:
276:
250:
224:
22:
4095:. December 1, 2016.
4024:More spoken articles
3420:Pigeonhole principle
3281:Blichfeldt's theorem
2859:
2793:
2759:
2723:
2689:
2456:
2209:
2094:
2009:
1936:
1873:
1816:
1707:
1590:
1400:
1346:
1244:
1204:
1139:
1076:
1015:lossless compression
817:
771:The birthday problem
750:The Athenian Mercury
410:Principe des tiroirs
312:is smaller than its
259:
233:
149:
73:population of London
47:pigeonhole principle
4092:PBS Infinite Series
4073:Alexander Bogomolny
3807:2016PNAS..113..532A
3685:Scientific American
3453:Diskrete Mathematik
3311:Multinomial theorem
3291:Combinatorial proof
2401:surjective function
2399:, then there is no
2316:, then there is no
2193:Art gallery problem
779:asks, for a set of
748:had been raised in
666:with more than one
395:Taubenschlagprinzip
334:Stanford University
53:items are put into
3994:
3924:Grimaldi, Ralph P.
3597:data.london.gov.uk
3480:The Induction Book
2903:
2805:
2779:
2735:
2709:
2513:
2318:injective function
2300:are sets, and the
2224:
2222:
2174:
2074:
1989:
1917:
1905:
1855:
1844:
1746:
1735:
1701:This implies that
1688:
1554:
1361:
1359:
1306:
1228:
1217:
1173:
1111:
1057:
932:
678:with a handshake.
514:zasada szufladkowa
369:in the sense of a
337:
306:injective function
271:
245:
219:
39:
3990:
3950:Topics In Algebra
3941:978-0-201-54983-6
3916:978-0-87150-164-6
3898:978-0-13-602040-0
3851:. 8 January 2015.
3531:Pandey, Avinash.
3316:Pochhammer symbol
3243:quantum mechanics
3234:Quantum mechanics
2931:falling factorial
2898:
2221:
2163:
2064:
1979:
1958:
1904:
1843:
1734:
1678:
1653:
1544:
1521:
1514:
1468:
1445:
1438:
1358:
1216:
1065:irrational number
902:
875:
840:
593:of one color and
424:"مبدأ برج الحمام"
407:" in German and "
287:ceiling functions
69:counting argument
57:containers, with
4140:
4104:
4046:
4014:
4012:
4001:
4000:
3991:
3981:
3979:
3974:
3962:
3944:
3933:
3919:
3901:
3874:
3873:
3871:
3859:
3853:
3852:
3845:
3839:
3838:
3828:
3818:
3782:
3776:
3774:
3763:
3752:
3746:
3740:
3734:
3728:
3722:
3716:
3710:
3704:
3698:
3697:
3676:
3670:
3664:
3658:
3657:
3649:
3643:
3642:
3635:
3629:
3628:
3621:
3615:
3614:
3607:
3601:
3600:
3589:
3583:
3580:
3574:
3573:
3553:
3547:
3546:
3544:
3543:
3528:
3522:
3521:
3501:
3495:
3494:
3474:
3468:
3467:
3447:
3441:
3435:
3429:
3416:
3410:
3409:
3391:
3359:
3348:
3342:
3321:Ramsey's theorem
3229:
3225:
3221:
3217:
3213:
3209:
3205:
3201:
3190:
3186:
3182:
3178:
3174:
3170:
3166:
3162:
3151:
3147:
3143:
3139:
3131:
3127:
3123:
3119:
3114:cardinal numbers
3099:
3093:
3083:
3077:
3071:
3065:
3059:
3048:
3042:
3031:
3025:
3011:
2998:birthday paradox
2995:
2985:
2975:
2968:
2961:
2954:
2928:
2912:
2910:
2909:
2904:
2899:
2897:
2896:
2887:
2886:
2885:
2869:
2851:
2844:
2838:
2824:
2814:
2812:
2811:
2806:
2788:
2786:
2785:
2780:
2772:
2754:
2747:ceiling function
2744:
2742:
2741:
2736:
2718:
2716:
2715:
2710:
2702:
2684:
2678:
2669:
2663:
2657:
2646:
2640:
2631:
2603:objects. Taking
2602:
2595:
2566:
2555:
2549:
2540:
2531:
2522:
2520:
2519:
2514:
2500:
2499:
2481:
2480:
2468:
2467:
2448:
2414:
2408:
2398:
2392:
2386:
2380:
2371:
2365:
2356:
2346:
2340:
2331:
2325:
2315:
2309:
2299:
2293:
2284:
2278:
2269:
2259:
2253:
2235:
2233:
2231:
2230:
2225:
2223:
2214:
2202:
2198:
2183:
2181:
2180:
2175:
2164:
2156:
2151:
2150:
2138:
2137:
2110:
2109:
2103:
2102:
2083:
2081:
2080:
2075:
2070:
2066:
2065:
2057:
2002:and by setting
1998:
1996:
1995:
1990:
1985:
1981:
1980:
1975:
1964:
1959:
1951:
1928:
1926:
1924:
1923:
1918:
1913:
1912:
1906:
1897:
1888:
1887:
1866:
1864:
1862:
1861:
1856:
1845:
1836:
1809:
1805:
1801:
1797:
1777:
1757:
1755:
1753:
1752:
1747:
1736:
1727:
1697:
1695:
1694:
1689:
1684:
1680:
1679:
1671:
1654:
1646:
1618:
1617:
1605:
1604:
1582:
1574:
1570:
1563:
1561:
1560:
1555:
1550:
1546:
1545:
1540:
1529:
1519:
1515:
1507:
1488:
1487:
1474:
1470:
1469:
1464:
1453:
1443:
1439:
1431:
1412:
1411:
1392:
1376:
1373:(there are only
1372:
1370:
1368:
1367:
1362:
1360:
1351:
1339:
1327:
1315:
1313:
1312:
1307:
1269:
1268:
1256:
1255:
1239:
1237:
1235:
1234:
1229:
1218:
1209:
1197:
1193:
1189:
1182:
1180:
1179:
1174:
1163:
1146:
1134:
1125:fractional parts
1122:
1120:
1118:
1117:
1112:
1107:
1069:
1063:is, for a fixed
1054:
1038:
1024:
1020:
1004:
998:
992:
982:
976:
969:computer science
955:
941:
939:
938:
933:
907:
903:
895:
880:
876:
871:
860:
845:
841:
836:
825:
809:
801:
784:
777:birthday problem
728:
718:
707:
701:
658:
651:
645:
638:
630:
624:
617:
610:
584:
577:
556:
546:
536:
526:
516:
506:
505:
496:
495:
486:
476:
466:
456:
454:Skuffeprincippet
446:
445:
436:
435:
426:
425:
412:
406:
404:Schubfachprinzip
397:
352:
344:
289:, respectively.
280:
278:
277:
272:
254:
252:
251:
246:
228:
226:
225:
220:
212:
186:
144:
140:
136:
129:
125:
114:
110:
100:
98:Schubfachprinzip
66:
56:
52:
36:
29:
4148:
4147:
4143:
4142:
4141:
4139:
4138:
4137:
4108:
4107:
4085:
4055:Edsger Dijkstra
4031:
4028:
4027:
4016:
4010:
4008:
4005:This audio file
4002:
3995:
3986:
3983:
3977:
3976:
3972:
3969:
3960:
3942:
3917:
3899:
3883:
3878:
3877:
3860:
3856:
3847:
3846:
3842:
3787:Sabadini, Irene
3783:
3779:
3765:
3755:
3753:
3749:
3741:
3737:
3729:
3725:
3717:
3713:
3705:
3701:
3680:Gardner, Martin
3677:
3673:
3665:
3661:
3650:
3646:
3637:
3636:
3632:
3623:
3622:
3618:
3609:
3608:
3604:
3591:
3590:
3586:
3581:
3577:
3570:
3554:
3550:
3541:
3539:
3529:
3525:
3518:
3510:. p. 490.
3502:
3498:
3491:
3475:
3471:
3464:
3456:. p. 367.
3448:
3444:
3436:
3432:
3417:
3413:
3389:1854/LU-4115264
3360:
3351:
3343:
3334:
3329:
3276:Axiom of choice
3272:
3263:lattice spacing
3247:interferometric
3236:
3227:
3223:
3219:
3215:
3211:
3207:
3203:
3199:
3188:
3184:
3180:
3176:
3172:
3168:
3164:
3160:
3157:Dedekind finite
3149:
3145:
3141:
3137:
3129:
3125:
3121:
3117:
3106:
3095:
3085:
3079:
3073:
3067:
3061:
3050:
3044:
3033:
3027:
3016:
3007:
3005:random variable
2987:
2977:
2970:
2963:
2956:
2933:
2927:
2917:
2892:
2888:
2881:
2877:
2870:
2868:
2860:
2857:
2856:
2846:
2840:
2834:
2831:
2820:
2794:
2791:
2790:
2789:objects, where
2768:
2760:
2757:
2756:
2750:
2724:
2721:
2720:
2719:objects, where
2698:
2690:
2687:
2686:
2680:
2674:
2665:
2659:
2648:
2642:
2636:
2626:
2617:
2610:
2604:
2597:
2593:
2584:
2577:
2571:
2565:
2557:
2551:
2548:
2542:
2539:
2533:
2527:
2495:
2491:
2476:
2472:
2463:
2459:
2457:
2454:
2453:
2447:
2438:
2431:
2425:
2422:
2410:
2404:
2394:
2388:
2382:
2376:
2367:
2361:
2348:
2347:places, and if
2342:
2336:
2327:
2321:
2311:
2305:
2295:
2289:
2280:
2274:
2261:
2260:places, and if
2255:
2249:
2242:
2212:
2210:
2207:
2206:
2204:
2200:
2196:
2155:
2146:
2145:
2133:
2132:
2105:
2104:
2098:
2097:
2095:
2092:
2091:
2056:
2025:
2021:
2010:
2007:
2006:
1965:
1963:
1950:
1949:
1945:
1937:
1934:
1933:
1908:
1907:
1895:
1883:
1882:
1874:
1871:
1870:
1868:
1834:
1817:
1814:
1813:
1811:
1807:
1803:
1799:
1796:
1789:
1779:
1776:
1769:
1759:
1725:
1708:
1705:
1704:
1702:
1670:
1645:
1632:
1628:
1613:
1609:
1600:
1596:
1591:
1588:
1587:
1576:
1572:
1568:
1530:
1528:
1506:
1499:
1495:
1483:
1479:
1454:
1452:
1430:
1423:
1419:
1407:
1403:
1401:
1398:
1397:
1391:
1384:
1378:
1374:
1349:
1347:
1344:
1343:
1341:
1335:
1329:
1323:
1317:
1264:
1260:
1251:
1247:
1245:
1242:
1241:
1207:
1205:
1202:
1201:
1199:
1195:
1191:
1184:
1159:
1142:
1140:
1137:
1136:
1132:
1103:
1077:
1074:
1073:
1071:
1067:
1046:
1033:
1022:
1018:
1011:
1000:
994:
988:
978:
972:
962:
951:
948:
894:
890:
861:
859:
855:
826:
824:
820:
818:
815:
814:
803:
795:
792:
790:Team tournament
780:
773:
723:
710:
703:
695:
684:
653:
647:
640:
632:
626:
619:
612:
606:
603:
579:
572:
568:
563:
504:اصل لانه کبوتری
326:
260:
257:
256:
234:
231:
230:
208:
182:
150:
147:
146:
142:
138:
131:
127:
116:
112:
108:
106:natural numbers
95:under the name
58:
54:
50:
49:states that if
31:
24:
17:
12:
11:
5:
4146:
4136:
4135:
4130:
4125:
4120:
4106:
4105:
4083:
4076:
4065:
4058:
4047:
4017:
4003:
3996:
3984:
3971:
3970:
3968:
3967:External links
3965:
3964:
3963:
3959:978-1114541016
3958:
3945:
3940:
3920:
3915:
3902:
3897:
3882:
3879:
3876:
3875:
3854:
3840:
3801:(3): 532–535.
3777:
3747:
3735:
3723:
3711:
3699:
3671:
3659:
3644:
3630:
3616:
3602:
3584:
3575:
3568:
3548:
3523:
3516:
3496:
3489:
3483:. p. 13.
3469:
3462:
3442:
3430:
3411:
3349:
3331:
3330:
3328:
3325:
3324:
3323:
3318:
3313:
3308:
3303:
3298:
3293:
3288:
3283:
3278:
3271:
3268:
3259:interferometer
3239:Yakir Aharonov
3235:
3232:
3105:
3102:
3072:holes and let
2945:− 2)...(
2923:
2914:
2913:
2902:
2895:
2891:
2884:
2880:
2876:
2873:
2867:
2864:
2830:
2827:
2817:floor function
2804:
2801:
2798:
2778:
2775:
2771:
2767:
2764:
2734:
2731:
2728:
2708:
2705:
2701:
2697:
2694:
2622:
2615:
2608:
2596:, which gives
2589:
2582:
2575:
2561:
2546:
2537:
2524:
2523:
2512:
2509:
2506:
2503:
2498:
2494:
2490:
2487:
2484:
2479:
2475:
2471:
2466:
2462:
2443:
2436:
2429:
2421:
2418:
2417:
2416:
2373:
2358:
2333:
2286:
2271:
2241:
2238:
2220:
2217:
2185:
2184:
2173:
2170:
2167:
2162:
2159:
2154:
2149:
2144:
2141:
2136:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2108:
2101:
2085:
2084:
2073:
2069:
2063:
2060:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2034:
2031:
2028:
2024:
2020:
2017:
2014:
2000:
1999:
1988:
1984:
1978:
1974:
1971:
1968:
1962:
1957:
1954:
1948:
1944:
1941:
1916:
1911:
1903:
1900:
1894:
1891:
1886:
1881:
1878:
1854:
1851:
1848:
1842:
1839:
1833:
1830:
1827:
1824:
1821:
1794:
1787:
1774:
1767:
1745:
1742:
1739:
1733:
1730:
1724:
1721:
1718:
1715:
1712:
1699:
1698:
1687:
1683:
1677:
1674:
1669:
1666:
1663:
1660:
1657:
1652:
1649:
1644:
1641:
1638:
1635:
1631:
1627:
1624:
1621:
1616:
1612:
1608:
1603:
1599:
1595:
1565:
1564:
1553:
1549:
1543:
1539:
1536:
1533:
1527:
1524:
1518:
1513:
1510:
1505:
1502:
1498:
1494:
1491:
1486:
1482:
1477:
1473:
1467:
1463:
1460:
1457:
1451:
1448:
1442:
1437:
1434:
1429:
1426:
1422:
1418:
1415:
1410:
1406:
1389:
1382:
1357:
1354:
1333:
1321:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1267:
1263:
1259:
1254:
1250:
1227:
1224:
1221:
1215:
1212:
1172:
1169:
1166:
1162:
1158:
1155:
1152:
1149:
1145:
1110:
1106:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1010:
1007:
961:
958:
947:
944:
943:
942:
931:
928:
925:
922:
919:
916:
913:
910:
906:
901:
898:
893:
889:
886:
883:
879:
874:
870:
867:
864:
858:
854:
851:
848:
844:
839:
835:
832:
829:
823:
791:
788:
772:
769:
757:Jean Leurechon
740:, prefixed to
683:
680:
602:
599:
597:of the other.
567:
564:
562:
559:
544:çekmece ilkesi
359:, that is, an
345:or the French
325:
322:
318:Siegel's lemma
270:
267:
264:
244:
241:
238:
218:
215:
211:
207:
204:
201:
198:
195:
192:
189:
185:
181:
178:
175:
172:
169:
166:
163:
160:
157:
154:
81:Jean Leurechon
15:
9:
6:
4:
3:
2:
4145:
4134:
4133:Ramsey theory
4131:
4129:
4126:
4124:
4121:
4119:
4118:Combinatorics
4116:
4115:
4113:
4102:
4098:
4094:
4093:
4088:
4084:
4081:
4077:
4074:
4070:
4066:
4063:
4059:
4056:
4052:
4048:
4044:
4040:
4039:
4034:
4030:
4029:
4025:
4021:
4006:
3961:
3955:
3951:
3946:
3943:
3937:
3932:
3931:
3925:
3921:
3918:
3912:
3908:
3903:
3900:
3894:
3890:
3885:
3884:
3870:
3865:
3858:
3850:
3844:
3836:
3832:
3827:
3822:
3817:
3812:
3808:
3804:
3800:
3796:
3792:
3788:
3781:
3772:
3768:
3762:
3758:
3751:
3744:
3739:
3732:
3727:
3720:
3715:
3708:
3703:
3695:
3691:
3687:
3686:
3681:
3675:
3669:, p. 277
3668:
3667:Grimaldi 1994
3663:
3655:
3648:
3640:
3634:
3626:
3620:
3612:
3606:
3598:
3594:
3588:
3579:
3571:
3569:9780415191326
3565:
3561:
3560:
3552:
3538:
3534:
3527:
3519:
3517:9780412990410
3513:
3509:
3508:
3500:
3492:
3490:9780486811994
3486:
3482:
3481:
3473:
3465:
3463:9783833455292
3459:
3455:
3454:
3446:
3439:
3434:
3427:
3426:
3421:
3415:
3407:
3403:
3399:
3395:
3390:
3385:
3381:
3377:
3373:
3369:
3365:
3358:
3356:
3354:
3346:
3345:Herstein 1964
3341:
3339:
3337:
3332:
3322:
3319:
3317:
3314:
3312:
3309:
3307:
3304:
3302:
3299:
3297:
3294:
3292:
3289:
3287:
3284:
3282:
3279:
3277:
3274:
3273:
3267:
3264:
3260:
3256:
3255:wave function
3252:
3248:
3244:
3240:
3231:
3196:
3192:
3158:
3153:
3135:
3115:
3111:
3110:infinite sets
3104:Infinite sets
3101:
3098:
3092:
3088:
3082:
3076:
3070:
3066:pigeons into
3064:
3057:
3053:
3047:
3040:
3036:
3030:
3023:
3019:
3015:
3012:has a finite
3010:
3006:
3001:
2999:
2994:
2990:
2984:
2980:
2973:
2966:
2959:
2952:
2948:
2944:
2940:
2936:
2932:
2926:
2921:
2900:
2893:
2889:
2882:
2874:
2865:
2862:
2855:
2854:
2853:
2850:
2843:
2837:
2826:
2823:
2818:
2799:
2773:
2769:
2765:
2753:
2748:
2729:
2703:
2699:
2695:
2683:
2677:
2671:
2668:
2662:
2655:
2651:
2645:
2639:
2633:
2630:
2625:
2621:
2614:
2607:
2600:
2592:
2588:
2581:
2574:
2568:
2564:
2560:
2554:
2545:
2536:
2530:
2510:
2507:
2504:
2501:
2496:
2492:
2488:
2485:
2482:
2477:
2473:
2469:
2464:
2460:
2452:
2451:
2450:
2446:
2442:
2435:
2428:
2413:
2407:
2402:
2397:
2391:
2385:
2379:
2374:
2370:
2364:
2359:
2355:
2351:
2345:
2339:
2334:
2330:
2324:
2319:
2314:
2308:
2303:
2298:
2292:
2287:
2283:
2277:
2272:
2268:
2264:
2258:
2252:
2247:
2246:
2245:
2237:
2218:
2215:
2194:
2190:
2171:
2168:
2165:
2160:
2157:
2152:
2142:
2139:
2129:
2126:
2120:
2117:
2114:
2090:
2089:
2088:
2087:one obtains
2071:
2067:
2061:
2058:
2053:
2047:
2044:
2038:
2035:
2032:
2029:
2026:
2022:
2015:
2012:
2005:
2004:
2003:
1986:
1982:
1976:
1972:
1969:
1966:
1960:
1955:
1952:
1946:
1942:
1939:
1932:
1931:
1930:
1914:
1901:
1898:
1892:
1889:
1879:
1876:
1852:
1849:
1846:
1840:
1837:
1831:
1825:
1822:
1793:
1786:
1782:
1773:
1766:
1762:
1743:
1740:
1737:
1731:
1728:
1722:
1716:
1713:
1685:
1681:
1675:
1672:
1667:
1664:
1661:
1658:
1655:
1650:
1647:
1642:
1639:
1636:
1633:
1629:
1625:
1622:
1614:
1610:
1606:
1601:
1597:
1586:
1585:
1584:
1580:
1571:integers and
1551:
1547:
1541:
1537:
1534:
1531:
1525:
1522:
1516:
1511:
1508:
1503:
1500:
1496:
1492:
1489:
1484:
1480:
1475:
1471:
1465:
1461:
1458:
1455:
1449:
1446:
1440:
1435:
1432:
1427:
1424:
1420:
1416:
1413:
1408:
1404:
1396:
1395:
1394:
1388:
1381:
1355:
1352:
1338:
1332:
1326:
1320:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1270:
1265:
1261:
1257:
1252:
1248:
1225:
1222:
1219:
1213:
1210:
1187:
1170:
1167:
1164:
1156:
1153:
1150:
1147:
1130:
1126:
1100:
1097:
1094:
1088:
1085:
1066:
1062:
1053:
1049:
1044:
1043:
1037:
1030:
1026:
1016:
1006:
1003:
997:
991:
986:
981:
975:
970:
966:
957:
954:
929:
926:
923:
920:
917:
914:
911:
908:
904:
899:
896:
891:
887:
884:
881:
877:
872:
868:
865:
862:
856:
852:
849:
846:
842:
837:
833:
830:
827:
821:
813:
812:
811:
807:
799:
787:
783:
778:
768:
766:
762:
759:'s 1622 work
758:
753:
752:before 1704.
751:
747:
743:
739:
734:
732:
726:
720:
717:
713:
706:
699:
693:
689:
682:Hair counting
679:
677:
673:
669:
665:
660:
656:
650:
643:
636:
629:
622:
615:
609:
598:
596:
592:
588:
582:
575:
558:
555:
554:nguyên lý hộp
550:
545:
540:
535:
530:
525:
520:
515:
510:
500:
490:
485:
480:
475:
470:
465:
464:ladenprincipe
460:
455:
450:
440:
430:
420:
416:
411:
405:
399:
396:
391:
387:
386:lingua franca
383:
379:
374:
372:
368:
367:
362:
358:
357:
351:
350:
343:
335:
330:
321:
319:
315:
311:
307:
303:
299:
298:infinite sets
295:
290:
288:
284:
265:
239:
213:
209:
205:
199:
196:
193:
187:
183:
176:
173:
170:
161:
158:
155:
152:
134:
123:
119:
107:
102:
99:
94:
90:
86:
82:
77:
74:
70:
65:
61:
48:
44:
34:
27:
21:
4090:
4036:
3949:
3929:
3909:, PWS-Kent,
3906:
3888:
3857:
3843:
3798:
3794:
3780:
3770:
3766:
3760:
3756:
3750:
3743:Brualdi 2010
3738:
3733:, p. 70
3731:Brualdi 2010
3726:
3718:
3714:
3706:
3702:
3683:
3674:
3662:
3653:
3647:
3633:
3619:
3605:
3596:
3587:
3578:
3558:
3551:
3540:. Retrieved
3536:
3526:
3506:
3499:
3479:
3472:
3452:
3445:
3433:
3423:
3414:
3374:(2): 27–29.
3371:
3367:
3347:, p. 90
3237:
3197:
3193:
3154:
3134:tautological
3107:
3096:
3090:
3086:
3080:
3074:
3068:
3062:
3055:
3051:
3045:
3038:
3034:
3028:
3021:
3017:
3008:
3002:
2992:
2988:
2982:
2978:
2971:
2964:
2957:
2950:
2946:
2942:
2938:
2934:
2924:
2919:
2915:
2848:
2841:
2835:
2832:
2821:
2751:
2681:
2675:
2672:
2666:
2660:
2653:
2649:
2643:
2637:
2634:
2628:
2623:
2619:
2612:
2605:
2598:
2590:
2586:
2579:
2572:
2569:
2562:
2558:
2552:
2543:
2534:
2528:
2525:
2444:
2440:
2433:
2426:
2423:
2411:
2405:
2395:
2389:
2383:
2377:
2368:
2362:
2353:
2349:
2343:
2337:
2328:
2322:
2312:
2306:
2296:
2290:
2281:
2275:
2266:
2262:
2256:
2250:
2243:
2186:
2086:
2001:
1791:
1784:
1780:
1771:
1764:
1760:
1700:
1578:
1577:{0, 1, ...,
1566:
1386:
1379:
1336:
1330:
1324:
1318:
1185:
1058:
1051:
1047:
1040:
1035:
1012:
1001:
995:
989:
979:
973:
963:
952:
949:
805:
797:
793:
781:
774:
760:
754:
749:
745:
741:
737:
735:
724:
721:
715:
711:
704:
697:
685:
661:
654:
648:
641:
634:
627:
625:, there are
620:
613:
607:
604:
601:Hand shaking
594:
590:
586:
580:
573:
569:
566:Sock picking
534:Lådprincipen
400:
381:
377:
375:
370:
364:
360:
354:
338:
291:
132:
121:
117:
103:
88:
84:
78:
63:
59:
46:
40:
32:
25:
2941:− 1)(
2420:Strong form
2302:cardinality
700:= 1 million
474:skatulyaelv
294:finite sets
281:denote the
43:mathematics
30:pigeons in
4112:Categories
4020:Audio help
4011:2021-06-05
3881:References
3542:2021-01-12
1810:such that
1393:such that
1316:such that
1198:such that
1135:such that
946:Subset sum
637:− 1"
549:Vietnamese
519:Portuguese
382:pigeonhole
378:pigeonhole
366:pigeonhole
4043:EMS Press
3869:1412.1333
2866:−
2803:⌋
2797:⌊
2777:⌋
2763:⌊
2733:⌉
2727:⌈
2707:⌉
2693:⌈
2567:objects.
2502:−
2486:⋯
2236:objects.
2140:−
2030:∈
1943:∈
1880:∈
1662:−
1643:−
1637:−
1626:∈
1607:−
1581:− 1
1567:for some
1493:∈
1417:∈
1289:…
1271:∈
1154:−
1101:∈
866:−
831:−
727:= 150,000
657:− 1
623:− 1
469:Hungarian
429:Bulgarian
342:Schubfach
324:Etymology
269:⌉
266:⋯
263:⌈
243:⌋
240:⋯
237:⌊
217:⌉
203:⌈
191:⌋
174:−
165:⌊
4097:Archived
4022: ·
3926:(1994),
3835:26729862
3694:24950467
3537:d3gt.com
3406:44193229
3270:See also
2962:and for
2949:−
2656:- 1) + 1
2618:= ... =
2585:= ... =
1867:then if
1790:−
1770:−
905:⌋
892:⌊
878:⌋
857:⌊
843:⌋
822:⌊
561:Examples
547:"), and
489:Japanese
390:dovecote
310:codomain
229:, where
4101:YouTube
4045:, 2001
4009: (
3980:minutes
3826:4725468
3803:Bibcode
3641:. 1704.
3627:. 1704.
3613:. 1710.
3440:, p. 27
3398:3207654
2929:is the
2815:is the
2745:is the
2439:, ...,
2234:
2205:
1927:
1869:
1865:
1812:
1806:: find
1756:
1703:
1371:
1342:
1238:
1200:
1121:
1072:
1050:×
1039:in the
985:caching
965:Hashing
960:Hashing
692:average
539:Turkish
529:Swedish
499:Persian
479:Italian
439:Chinese
3956:
3938:
3913:
3895:
3833:
3823:
3692:
3566:
3514:
3487:
3460:
3404:
3396:
3159:: Let
2974:> 0
2955:. For
2916:where
1804:(0, 1]
1758:where
1520:
1444:
1188:> 0
1183:where
688:London
672:degree
668:vertex
644:> 1
616:> 1
509:Polish
494:引き出し論法
449:Danish
419:Arabic
415:French
356:drawer
349:tiroir
314:domain
308:whose
45:, the
3864:arXiv
3690:JSTOR
3402:S2CID
3327:Notes
3251:arXiv
2981:>
2969:(and
2403:from
2352:<
2320:from
2265:>
1129:dense
714:>
664:graph
587:three
459:Dutch
413:" in
283:floor
115:, if
62:>
3954:ISBN
3936:ISBN
3911:ISBN
3893:ISBN
3831:PMID
3764:and
3564:ISBN
3512:ISBN
3485:ISBN
3458:ISBN
3226:and
3202:and
3163:and
3014:mean
2953:+ 1)
2641:and
2635:Let
2424:Let
2381:and
2294:and
2166:<
2153:<
2054:<
1847:<
1832:<
1738:<
1723:<
1569:p, q
1328:and
1220:<
1165:<
1133:n, m
775:The
765:écus
676:edge
557:").
537:"),
527:"),
517:"),
507:"),
497:"),
487:"),
477:"),
467:"),
457:"),
447:"),
444:抽屉原理
437:"),
285:and
255:and
141:and
111:and
28:= 10
4053:";
3821:PMC
3811:doi
3799:113
3773:− 1
3384:hdl
3376:doi
3218:of
3210:to
3187:to
3179:to
3171:to
3148:to
3128:to
3084:is
2967:= 1
2960:= 0
2601:+ 1
2594:= 2
2409:to
2335:If
2326:to
2304:of
2248:If
2019:sup
1802:in
1778:or
1575:in
1127:is
1123:of
977:to
967:in
808:= 4
800:= 7
733:).
605:If
595:one
591:two
583:= 3
576:= 2
427:),
398:".
135:+ 1
124:+ 1
87:or
41:In
35:= 9
4114::
4089:.
4041:,
4035:,
3978:24
3829:.
3819:.
3809:.
3797:.
3793:.
3769:=
3759:=
3595:.
3535:.
3400:.
3394:MR
3392:.
3382:.
3372:36
3370:.
3366:.
3352:^
3335:^
3000:.
2991:≤
2847:1/
2825:.
2627:=
2611:=
2578:=
2432:,
1783:=
1763:=
1385:,
551:("
541:("
531:("
521:("
511:("
501:("
491:("
481:("
471:("
461:("
451:("
441:("
431:("
122:km
120:=
4103:.
4078:"
4075:.
4067:"
4060:"
4049:"
4026:)
4018:(
4013:)
3982:)
3975:(
3872:.
3866::
3837:.
3813::
3805::
3775:.
3771:r
3767:k
3761:n
3757:m
3696:.
3599:.
3572:.
3545:.
3520:.
3493:.
3466:.
3408:.
3386::
3378::
3228:A
3224:b
3220:B
3216:b
3212:B
3208:A
3204:B
3200:A
3189:B
3185:A
3181:B
3177:A
3173:B
3169:A
3165:B
3161:A
3150:B
3146:A
3142:B
3138:A
3130:B
3126:A
3122:B
3118:A
3097:X
3091:m
3089:/
3087:n
3081:X
3075:X
3069:m
3063:n
3058:)
3056:X
3054:(
3052:E
3046:X
3041:)
3039:X
3037:(
3035:E
3029:X
3024:)
3022:X
3020:(
3018:E
3009:X
2993:m
2989:n
2983:m
2979:n
2972:m
2965:n
2958:n
2951:n
2947:m
2943:m
2939:m
2937:(
2935:m
2925:n
2922:)
2920:m
2918:(
2901:,
2894:n
2890:m
2883:n
2879:)
2875:m
2872:(
2863:1
2849:m
2842:m
2836:n
2822:x
2800:x
2774:n
2770:/
2766:k
2752:x
2730:x
2704:n
2700:/
2696:k
2682:n
2676:k
2667:r
2661:n
2654:r
2652:(
2650:n
2644:r
2638:n
2629:r
2624:n
2620:q
2616:2
2613:q
2609:1
2606:q
2599:n
2591:n
2587:q
2583:2
2580:q
2576:1
2573:q
2563:n
2559:q
2553:n
2547:2
2544:q
2538:1
2535:q
2529:n
2511:1
2508:+
2505:n
2497:n
2493:q
2489:+
2483:+
2478:2
2474:q
2470:+
2465:1
2461:q
2445:n
2441:q
2437:2
2434:q
2430:1
2427:q
2415:.
2412:T
2406:S
2396:T
2390:S
2384:T
2378:S
2369:n
2363:n
2354:m
2350:n
2344:m
2338:n
2332:.
2329:T
2323:S
2313:T
2307:S
2297:T
2291:S
2282:n
2276:n
2267:m
2263:n
2257:m
2251:n
2219:k
2216:n
2201:k
2197:n
2172:.
2169:e
2161:M
2158:1
2148:|
2143:p
2135:]
2130:a
2127:n
2124:)
2121:1
2118:+
2115:k
2112:(
2107:[
2100:|
2072:,
2068:}
2062:M
2059:j
2051:]
2048:a
2045:n
2042:[
2039:r
2036::
2033:N
2027:r
2023:{
2016:=
2013:k
1987:,
1983:]
1977:M
1973:1
1970:+
1967:j
1961:,
1956:M
1953:j
1947:(
1940:p
1915:,
1910:]
1902:M
1899:1
1893:,
1890:0
1885:(
1877:p
1853:;
1850:e
1841:M
1838:1
1829:]
1826:a
1823:n
1820:[
1808:n
1800:p
1795:2
1792:n
1788:1
1785:n
1781:n
1775:1
1772:n
1768:2
1765:n
1761:n
1744:,
1741:e
1732:M
1729:1
1720:]
1717:a
1714:n
1711:[
1686:.
1682:)
1676:M
1673:1
1668:+
1665:p
1659:q
1656:,
1651:M
1648:1
1640:p
1634:q
1630:(
1623:a
1620:)
1615:1
1611:n
1602:2
1598:n
1594:(
1579:M
1573:k
1552:,
1548:)
1542:M
1538:1
1535:+
1532:k
1526:+
1523:q
1517:,
1512:M
1509:k
1504:+
1501:q
1497:(
1490:a
1485:2
1481:n
1476:,
1472:)
1466:M
1462:1
1459:+
1456:k
1450:+
1447:p
1441:,
1436:M
1433:k
1428:+
1425:p
1421:(
1414:a
1409:1
1405:n
1390:2
1387:n
1383:1
1380:n
1375:M
1356:M
1353:1
1337:a
1334:2
1331:n
1325:a
1322:1
1319:n
1304:}
1301:1
1298:+
1295:M
1292:,
1286:,
1283:2
1280:,
1277:1
1274:{
1266:2
1262:n
1258:,
1253:1
1249:n
1226:,
1223:e
1214:M
1211:1
1196:M
1192:a
1186:e
1171:,
1168:e
1161:|
1157:m
1151:a
1148:n
1144:|
1109:}
1105:Z
1098:n
1095::
1092:]
1089:a
1086:n
1083:[
1080:{
1068:a
1052:n
1048:n
1036:n
1034:2
1023:L
1019:L
1002:n
996:m
990:n
980:m
974:n
953:S
930:2
927:=
924:1
921:+
918:1
915:=
912:1
909:+
900:4
897:6
888:=
885:1
882:+
873:4
869:1
863:7
853:=
850:1
847:+
838:m
834:1
828:n
806:m
804:(
798:n
796:(
782:n
725:m
716:m
712:n
705:n
698:m
696:(
655:n
649:n
642:n
635:n
633:"
628:n
621:n
614:n
608:n
581:n
574:m
571:(
421:(
214:m
210:/
206:n
200:=
197:1
194:+
188:m
184:/
180:)
177:1
171:n
168:(
162:=
159:1
156:+
153:k
143:m
139:n
133:k
128:m
118:n
113:m
109:k
64:m
60:n
55:m
51:n
33:m
26:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.