Principio do pombal

De testwiki
Saltar á navegación Saltar á procura
Pombas en buratos. Aquí hai Modelo:Math pombas en Modelo:Math 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 Modelo:Mvar elementos se colocan en Modelo:Mvar recipientes, con Modelo:Math, polo menos un recipiente debe conter máis dun elemento.[1] 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 Modelo:Mvar e Modelo:Mvar, se Modelo:Math obxectos están distribuídos entre Modelo:Mvar conxuntos, o principio do pombal afirma que polo menos un dos conxuntos conterá polo menos Modelo:Math obxectos.[2] Para Modelo:Mvar e Modelo:Mvar arbitrarios, isto xeneralízase a k+1=⌊(n−1)/m⌋+1=⌈n/m⌉, 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 Modelo:Math 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 Modelo:Math elementos), cunha limitación de só catro equipos Modelo:Math 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:

⌊n−1m⌋+1=⌊7−14⌋+1=⌊64⌋+1=1+1=2

Suma do subconxunto

Calquera subconxunto de tamaño seis do conxunto Modelo:Math = {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. [3]

Teorema de Svéd-Vázsonyi

Modelo:Ap Dada unha secuencia de Modelo:Mvar 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 Modelo:Mvar 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 Modelo:Mvar.

Forma forte

Sexan Modelo:Math enteiros positivos. Se

q1+q2+⋯+qn−n+1

obxectos distribúense en Modelo:Math caixas, entón ou a primeira caixa contén polo menos Modelo:Math obxectos, ou a segunda caixa contén polo menos Modelo:Math obxectos,... , ou a Modelo:Math-ésima caixa contén polo menos Modelo:Math obxectos.[4]

A forma simple obtense a partir desta tomando Modelo:Math , o que dá Modelo:Math obxectos. Tomando Modelo:Math, dá a versión máis cuantificada do principio, a saber:

Sexan Modelo:Math e Modelo:Math números enteiros positivos. Se Modelo:Math obxectos están distribuídos en Modelo:Math caixas, daquela polo menos unha das caixas contén Modelo:Math ou máis dos obxectos.

Xeneralización do principio do pombal

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

1−mn_mn,

onde mn_ é o factorial descendente Modelo:Math. Para Modelo:Math e para Modelo:Math (e Modelo:Math), a probabilidade é cero; noutras palabras, se só hai unha pomba, non pode haber conflito. Para Modelo:Math (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 ( Modelo:Math ), 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

Modelo:Reflist

Véxase tamén

Bibliografía

Outros artigos

Ligazóns externas

Modelo:Control de autoridades

  1. ↑ Modelo:Cita Harvard sen parénteses
  2. ↑ Modelo:Cita Harvard sen parénteses
  3. ↑ Modelo:Cita Harvard sen parénteses
  4. ↑ Modelo:Cita Harvard sen parénteses
Obtido de «https://gl.wiki.beta.math.wmflabs.org/w/index.php?title=Principio_do_pombal&oldid=1548»