dereita|miniatura| Pombas en buratos. Aquí hai pombas en buratos. Dado que 10 é maior que 9, o principio do pombal di que polo menos un burato ten máis dunha pomba. (O burato superior esquerdo ten 2 pombas).
En matemáticas, o principio do pombal estabelece que se elementos se colocan en recipientes, con , polo menos un recipiente debe conter máis dun elemento. Por exemplo, de tres luvas, polo menos dúas deben ser dereitas ou polo menos dúas deben ser esquerdas, porque hai tres obxectos pero só dúas categorías de tipos de mans para colocalas. Esta afirmación aparentemente obvia, un tipo de argumento de contaxe, pódese usar para demostrar resultados posiblemente inesperados. Por exemplo, dado que a poboación da Galicia é máis dunha unidade maior que o número máximo de cabelos que pode haber na cabeza dun humano (que vén sendo uns 100.000), o principio esixe que haxa polo menos dúas persoas na Galiza que teñan o mesmo número de cabelos nas súas cabezas.
O principio ten varias xeneralizacións e pódese enunciar de varias maneiras. Nunha versión máis cuantificada: para os números naturais e , se obxectos están distribuídos entre conxuntos, o principio do pombal afirma que polo menos un dos conxuntos conterá polo menos obxectos. Para e arbitrarios, isto xeneralízase a , onde e indican as funcións chan e teito, respectivamente.
Malia a evidencia do principio, a complicación e utilidade do seu uso radica en enfocar e redefinir os problemas dun modo que este principio sexa aplicábel.
Exemplos
Conta de cabelos Visto na introdución.
O problema do aniversario O problema do aniversario pregunta, para un conxunto de persoas escollidas ao chou, cal é a probabilidade de que algún par delas teña o mesmo aniversario? O problema en si refírese principalmente ás probabilidades contraintuitivas, pero tamén se pode dicir polo principio do pombal que entre 367 persoas, hai polo menos un par de persoas que comparten o mesmo aniversario cun 100% de probabilidade, xa que só hai 366 posibles aniversarios para escoller.
Torneo por equipos Imaxínense sete persoas que queiran xogar nun torneo de equipos elementos), cunha limitación de só catro equipos buratos) para escoller. O principio do pombal di que non todos poden xogar en equipos diferentes; debe haber polo menos un equipo con polo menos dous dos sete xogadores:
Suma do subconxunto Calquera subconxunto de tamaño seis do conxunto = {1,2,3,...,9} debe conter dous elementos cuxa suma sexa 10. Os buratos serán etiquetados polos subconxuntos de dous elementos {1,9}, {2,8}, {3,7}, {4,6} e o conxunto unitario {5}, cinco buratos en total. Cando as seis "pombas" (elementos do subconxunto de tamaño seis) se colocan nestes buratos, cada pomba entrando no burato que o ten contido na súa etiqueta, resulta que polo menos un dos pombais etiquetados cun subconxunto de dous elementos terá dúas pombas nel.
Teorema de Svéd-Vázsonyi
Dada unha secuencia de números aleatorios existe unha subsecuencia consecutiva cuxa suma é divisíbel polo número de elementos da secuencia orixinal.
Se sumamos secuencialmente e dividimos por temos máis sumas parciais que residuos e polo tanto polo menos un residuo repítese, a suma entre os elementos co mesmo residuo é logo divisíbel por .
Forma forte Sexan enteiros positivos. Se
obxectos distribúense en caixas, entón ou a primeira caixa contén polo menos obxectos, ou a segunda caixa contén polo menos obxectos,... , ou a -ésima caixa contén polo menos obxectos.
A forma simple obtense a partir desta tomando , o que dá obxectos. Tomando , dá a versión máis cuantificada do principio, a saber:
Sexan e números enteiros positivos. Se obxectos están distribuídos en caixas, daquela polo menos unha das caixas contén ou máis dos obxectos.
Xeneralización do principio do pombal Unha xeneralización probabilística do principio do pombal afirma que se pombas se colocan aleatoriamente en buratos con probabilidade uniforme , daquela polo menos un burato albergará máis dunha pomba con probabilidade
onde é o factorial descendente . Para e para (e ), a probabilidade é cero; noutras palabras, se só hai unha pomba, non pode haber conflito. Para (máis pombais que buratos) é un, nese caso coincide co principio do pombal normal. Mais aínda que o número de pombas non supere o número de buratos ( ), debido á natureza aleatoria da asignación de pombas a buratos, moitas veces hai unha gran probabilidade de que se produzan agrupamentos no mesmo burato. Por exemplo, se 2 pombas son asignadas aleatoriamente a 4 buratos, hai un 25 % de posibilidades de que polo menos un burato contemple máis dunha pomba; para 5 pombas e 10 buratos, esa probabilidade é do 69,76 %; e para 10 pombas e 20 buratos é dun 93,45 %. Se o número de buratos permanece fixo, sempre hai unha maior probabilidade de parella cando se engaden máis pombas. Este problema trátase de forma ampliada no paradoxo do aniversario. Notas
Véxase tamén Bibliografía
Outros artigos Axioma da escolla Ligazóns externas
"The strange case of The Pigeon-hole Principle"; Edsger Dijkstra. "The Pigeon Hole Principle"; Exemplos elementais por Larry Cusick. "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; por Alexander Bogomolny. "16 fun applications of the pigeonhole principle".
Categoría:Combinatoria Categoría:Teoremas