Principio do pombal

Pombas en buratos. Aquí hai n = 10 pombas en m = 9 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 n elementos se colocan en m recipientes, con n > m, 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 k e m, se n = km + 1 obxectos están distribuídos entre m conxuntos, o principio do pombal afirma que polo menos un dos conxuntos conterá polo menos k + 1 obxectos. Para n e m arbitrarios, isto xeneralízase a $k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil$, onde $\lfloor \cdot \rfloor$ e $\lceil \cdot \rceil$ 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 n 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 (n = 7 elementos), cunha limitación de só catro equipos (m = 4 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:

$$\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$$

Suma do subconxunto

Calquera subconxunto de tamaño seis do conxunto S = {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.

Forma forte

Sexan q₁, q₂, ..., q_n enteiros positivos. Se

$q_{1}+q_{2}+\cdots +q_{n}-n+1$

obxectos distribúense en n caixas, entón ou a primeira caixa contén polo menos q₁ obxectos, ou a segunda caixa contén polo menos q₂ obxectos,... , ou a n-ésima caixa contén polo menos q_n obxectos.

A forma simple obtense a partir desta tomando q₁ = q₂ = ...= q_n = 2 , o que dá n + 1 obxectos. Tomando q₁ = q₂ = ... = q_n = r, dá a versión máis cuantificada do principio, a saber:

Sexan n e r números enteiros positivos. Se n(r - 1) + 1 obxectos están distribuídos en n caixas, daquela polo menos unha das caixas contén r ou máis dos obxectos.

Xeneralización do principio do pombal

Unha xeneralización probabilística do principio do pombal afirma que se n pombas se colocan aleatoriamente en m buratos con probabilidade uniforme 1/m, daquela polo menos un burato albergará máis dunha pomba con probabilidade

$1-{\frac {m^{\underline {n}}}{m^{n}}},$

onde $m^{\underline {n}}$ é o factorial descendente m(m − 1)(m − 2)...(m − n + 1). Para n = 0 e para n = 1 (e m > 0), a probabilidade é cero; noutras palabras, se só hai unha pomba, non pode haber conflito. Para n > m (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 ( n ≤ m ), 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.

Véxase tamén

Bibliografía

• Brualdi, Richard A. (2010). Introductory Combinatorics (5th ed.). Pentice Hall. ISBN 978-0-13-602040-0. 
• Fletcher, Peter; Patty, C.Wayne (1987). Foundations of Higher Mathematics. PWS-Kent. ISBN 978-0-87150-164-6. 
• Grimaldi, Ralph P. (1994). Discrete and Combinatorial Mathematics: An Applied Introduction (3rd ed.). Addison-Wesley. ISBN 978-0-201-54983-6. 
• Herstein, I. N. (1964). Topics In Algebra. Waltham: Blaisdell Publishing Company. ISBN 978-1114541016. 

Outros artigos

• Axioma da escolla

Ligazóns externas

• "Dirichlet box principle". Encyclopedia of Mathematics. EMS Press. 2001 [1994]. 
• "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".