Principio do pombal

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