Pigeonhole principle: Difference between revisions
Jump to navigation
Jump to search
imported>Nick Johnson (Initial) |
imported>Nick Johnson m (fixed category) |
||
| Line 1: | Line 1: | ||
In [[discrete mathematics]], the '''Pigeonhole Principle''' states "if you have ten pigeons and only nine pigeonholes, then at least one of those pigeonholes is shared by more than one pigeon." More formally, for any group of N items which must be assigned to M categories, if N > M, then at least one category must contain more than one item. The pigeonhole priciple does not state any more. it does not state how excess items are distributed, or even that all categories are filled. | In [[discrete mathematics]], the '''Pigeonhole Principle''' states "if you have ten pigeons and only nine pigeonholes, then at least one of those pigeonholes is shared by more than one pigeon." More formally, for any group of N items which must be assigned to M categories, if N > M, then at least one category must contain more than one item. The pigeonhole priciple does not state any more. it does not state how excess items are distributed, or even that all categories are filled. | ||
[[Category:CZ_Live]] [[Category:Mathematics | [[Category:CZ_Live]] [[Category:Mathematics Workgroup]] | ||
Revision as of 14:34, 21 February 2007
In discrete mathematics, the Pigeonhole Principle states "if you have ten pigeons and only nine pigeonholes, then at least one of those pigeonholes is shared by more than one pigeon." More formally, for any group of N items which must be assigned to M categories, if N > M, then at least one category must contain more than one item. The pigeonhole priciple does not state any more. it does not state how excess items are distributed, or even that all categories are filled.