Principi del colomer

Archiu:Pigeons-in-holes.jpg

L'inspiració per al nom del principi: aus en un colomer. Ací $n=7$ i $m=9$.

En Matemàtica, el principi del colomer, també cridat principi de caselles, principi de Dirichlet o principi de les caixes, establix que si $n$ colomes es distribuïxen en $m$ colomers, i si $n>m$, llavors a lo manco hi haurà un colomer en més d'una coloma. Una atra forma de dir-ho és que $m$ colomers poden albergar com a molt $m$ colomes si cada una de les colomes està en un colomer distint, aixina que el fet d'afegir una atra coloma força a tornar a utilisar algun dels colomers. Esta afirmació aparentment òbvia, un tipo d'argument combinatori, pot usar-se per a demostrar resultats possiblement inesperats.

A pesar de que el principi de caselles apareix en 1624 en un llibre atribuït a Jean Leurechon, és comunament cridat Principi de les caixes de Dirichlet o Principi de les caixons de Dirichlet per un tractat sobre el principi escrit en 1834 per Johann Peter Gustav Lejeune Dirichlet en el nom de Schubfachprinzip ("principi dels caixons").

Etimologia

Archiu:Pigeon-hole messagebox 3.jpg

Caselles de mensages en Universitat Stanford.

Dirichlet va publicar el seu treball en francés i alemà, usant el terme en alemà Schubfach o el terme en francés tiroir. El significat original d'eixos térmens correspon a l'espanyol caixó, això és, peça mòvil de diversos mobles, tancada pels seus costats i avall, oberta per dalt, usada per a guardar diversos elements ordenadamente. (Dirichlet va escriure sobre distribuir perles entre eixos caixons.) Eixos térmens es varen transformar en la paraula colomer en el sentit d'un espai chicotet en un escritori, gabinet, o paret per a guardar cartes o papers, metafòricament arraïlat en estructures que alberguen colomes.

La sugerent (encara que no enganyosa) interpretació de "caseller" com "colomer" ha trobat el seu camí de tornada a l'alemà per mig d'una retrotraducción del principi del colomer com "Taubenschlagprinzip".

Generalisació i demostració

Archiu:TooManyPigeons.jpg

Ací $n=10$ i $m=9$.

El principi té vàries generalisacions i pot ser enunciat de distintes maneres. En una versió més quantificada: per als número natural $k$ i $m$, si $n=km+1$ objectes són distribuïts en $m$ conjunts, llavors pel principi de caselles afirma que a lo manco un dels conjunts contindrà a lo manco $k+1$ objectes. Per a $n$ i $m$ arbitraris, açò es generalisa a $k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil$, a on $\lfloor \cdots \rfloor$ i $\lceil \cdots \rceil$ denoten les funcions sol i sostre, respectivament.

Encara que l'aplicació més directa és en conjunts finitos (com a colomes i caixes), també s'utilisa en conjunts infinits que no poden ser posats en una correspondència un a un. Per a açò és necessari la proposició formal del principi de caselles, com és "no existix una funció inyectiva que el seu codominio és més chicotet que el seu domini". Demostracions matemàtiques alvançades com el lema de Siegel es construïxen sobre este concepte més general.

Enunciem el principi de la següent manera: Sean $n$, $q$ i $r$ tres número natural (en $1\le r\le q$). Si es desigen colocar $nq+r$ objectes en $n$ caselles, alguna caixa deu contindre a lo manco $q+1$ objectes.

Demostració. Assumim per contradicció que cada casella conté com a molt $q$ objectes, el número total d'objectes que podem colocar és $nq<nq+1\le nq+r$. Per tant, en $q$ per caixa no és possible distribuir els $nq+r$ objectes. $◼$

Esta demostració nos servix per a provar de manera anàloga, el següent corolari: Si es desigen colocar $nq+r$ objectes en $n$ caselles, alguna caixa deu contindre al sum $q$ objectes.

Demostració per conjunts

Si $A$ i $B$ són conjunts finitos en $|A|$ > $|B|$ llavors no existix cap funció biyectiva de $A$ a $B$.

Demostració per inducció:

• Passe base: Supongam $|B|=0$, és dir, $B=\mathrm{\varnothing }$. Llavors no existix cap funció $f:A\to B$ , en particular no existix cap funció biyectiva.
• Hipòtesis inductiva: $f:A\to B$ no és biyectiva para tot conjunt finito $A$ i para tot conjunt finito $B$, que complixquen $|A|>|B|$, i $|B|\le n$, en $n\ge 0$.
• Tesis inductiva: Per a $|A|>|B|=n+1$, no existix una funció $f:A\to B$ biyectiva.
• Demostració del pas inductivo: Com $A$ no és buit, elegim un $a\in \text{A}$. Poden ocórrer dos coses. O be existix un atre element distint a $a$ en $A$, cridem-li $a^{\prime }$ que complixca $f(a)=f(a^{\prime })$. O be no existix tal element. Si el cas és que existix, la funció $f$ no és biyectiva i termina la demostració. Prengam el cas que no existix, llavors $f(a)$ té solament una preimagen que és $a$. Considerem la funció $g:A-\{a\}\to B-\{f(a)\}$ que coincidix en $f$ en tots els elements de $A-\{a\}$. Ara apliquem l'hipòtesis inductiva puix $B-\{f(a)\}$ té $n$ elements i $|A-\{a\}|=|A|-1>|B|-1=|B-\{f(a)\}|=n$, per lo tant $g$ no és biyectiva. Com $g$ no és biyectiva, $f$ no és biyectiva. $◼$

Vore també

• Combinatòria
• Principis combinatoris
• Teoria de Ramsey
• Lema de Siegel

Bibliografia

• Grimaldi, Ralph P. (1997), Matemàtiques Discretes i Combinatoria: Una introducció en aplicacions, 2dona ed., Mèxic, Addison Wesley Iberoamericana, S.A.
• Gómez Ortega, José A., Valdez Prim, Rogelio, Vázquez Padilla, Rita, (2011) Principi de les caselles, Mèxic, Universitat Nacional Autònoma de Mèxic.
• Guzmán, Miguel de (1986), Editorial Llabor S.A. Barcelona, Espanya. ¿títul?