Principi de les caselles

De Viquipèdia
Dreceres ràpides: navegació, cerca
En aquest exemple hi ha n = 10 coloms i k = 9 forats, per tant, hi ha d'haver un forat amb més d'un colom.

El principi de les caselles, de Dirichlet o del colomar[1][2] diu que si repartim n objectes en k caselles, i n és més gran que k, aleshores, necessàriament alguna de les caselles ha de rebre més d'un objecte.[3] La idea en què es basa és molt senzilla: si s'han de col·locar tres coloms en dues gàbies, per força dos coloms han de compartir una mateixa gàbia.[2]

L'origen del principi, almenys en el camp de les matemàtiques, és atribuït al matemàtic Johann Peter Gustav Lejeune Dirichlet el 1834. Segons Peter Flor, a la dècada de 1950 els especialistes en teoria de nombres de les universitats de Viena i Hamburg ja parlaven del principi de les caselles, referint-lo de vegades a Dirichlet. La denominació original en alemany fa referència a calaixos, però la traducció anglesa, pigeonhole principle, ha fet que en els exemples sovint es parli de pigeons ('coloms') i holes ('forats'), i això duu a la pintoresca denominació de principi del colomar.[4][2]

Hi ha diverses versions més generals del principi que es poden enunciar de diferents maneres. Una versió diu que per k i m nombres naturals, si es distribueixen n = km + 1 objectes en k caselles, aleshores almenys una de les caselles tindrà com a mínim m + 1 objectes. Per a n i k arbitraris, això generalitza a que almenys una casella tindrà n/k + 1 objectes, si k no és divisor de n, o n/k objectes, si k és divisor de n, a on els símbols ⌊·⌋ denoten la part entera.[2]

Encara que pugui semblar trivial, el principi de les caselles és molt eficaç per a demostrar, en un conjunt amb condicions que afecten només el nombre d'elements, l'existència d'alguns elements que comparteixen les mateixes propietats.[2]

Exemples[modifica | modifica el codi]

Agafant mitjons[modifica | modifica el codi]

Suposant que tinc una barreja de mitjons negres i blaus, quin és el mínim nombre de mitjons que he d'agafar per a poder garantir que en tinc dos del mateix color?

Considerem dues «caselles», k = 2, una per cada color. Pel principi de les caselles, només cal que agafi tres mitjons, n = 3, i ja tindré un color amb almenys 2 mitjons.

Encaixades de mans[modifica | modifica el codi]

Si hi ha n persones que es poden donar la mà entre elles (amb n > 1), el principi de les caselles prova que sempre hi haurà un parell de persones que hauran donat la mà a la mateixa quantitat de persones.

El nombre de persones a les quals algú dóna la mà seran les nostres «caselles». Cada persona donarà a entre 0 i n − 1 altres persones, i això crea n caselles possibles. Ara bé, o bé la casella del '0' o bé la de 'n − 1' han de quedar buides (si una persona dóna la mà a totes les altres, no és possible tenir una altra persona que no hagi donat la mà a ningú, i viceversa), i per tant tindrem n − 1 caselles per omplir. I com que hem de col·locar n persones en un màxim de n − 1 caselles, tindrem alguna repetició.

Comptant cabells[modifica | modifica el codi]

Podem argumentar que hi ha d'haver almenys dues persones a Barcelona amb el mateix nombre de cabells. Com que les persones tenen de mitjana uns 150.000 cabells, no és descabellat assumir (com a fita superior) que ningú no té més d'1.000.000 de cabells (prendrem k = 1 milió de caselles). Hi ha més d'1.000.000 de persones a Barcelona (n és més gran que 1 milió). Si assignem les persones a les caselles segons el seu nombre de cabells, hi ha d'haver almenys dues persones assignades a la mateixa casella quan fem l'assignació 1.000.001 (perquè tenen la mateixa quantitat de cabells). El principi només demostra l'existència d'una superposició, no diu res de la quantitat de superposicions (que és un tema que correspon a la teoria de la probabilitat).

Treballs de grup[modifica | modifica el codi]

En una classe de n = 25 alumnes, s'ofereixen k = 11 treballs, i cada alumne n'ha d'escollir un. El principi de les caselles ens diu que hi haurà almenys un treball que serà fet per com a mínim 3 alumnes. Per deduir-ho, com que 11 no és divisor de 25, el que s'ha de calcular és:

 \left\lfloor \frac{n}{k} \right\rfloor + 1 = \left\lfloor \frac{25}{11} \right\rfloor + 1 = \left\lfloor 2,27... \right\rfloor + 1 = 2 + 1 = 3

Suma en subconjunts[modifica | modifica el codi]

Qualsevol suconjunt de 6 elements del conjunt C = {1,2,3,...,9} ha de contenir dos elements que sumen 10. Etiquetarem les caselles amb els parells {1,9}, {2,8}, {3,7}, {4,6} i l'element {5}, un total de cinc caselles. Quan els sis elements (els elements del subconjunt de mida 6) es col·loquen en aquestes 5 caselles, posant cada element a la casella en què està etiquetat, com a mínim una de les caselles etiquetades amb dos nombres contindrà els dos nombres, i aquests sumaran 10.[5]

Formulació forta[modifica | modifica el codi]

Siguin q1, q2, ..., qn enters positius. Si

q_1 + q_2 + \cdots + q_n - n + 1

objectes es distribueixen en n capses, llavors o bé la primera capsa conté almenys q1 objectes, o la segona capsa conté almenys q2 objectes, ..., o la capsa número n conté almenys qn objectes.[6]

Usos i aplicacions[modifica | modifica el codi]

El principi de les caselles sorgeix en la informàtica teòrica. Per exemple, les col·lisions són inevitables en una taula de hash perquè la quantitat de claus possibles és més gran que el nombre de posicions de la taula. Una funció resum, tant és com estigui feta, no pot evitar aquestes col·lisions.

El principi es fa servir per demostrar que qualsevol algorisme de compressió sense pèrdua, assumint que redueix la mida d'algunes entrades (com suggereix el nom), també farà que algunes altres entrades augmentin de mida. Altramnent, el conjunt de totes les seqüències d'entrada de longitud com a màxim L es podrien enviar al conjunt molt més petit de totes les seqüències de longitud menor que L, i això es faria sense col·lisions (perquè la compressió no té pèrdua), situació impossible segons el principi de les caselles.

Un problema destacat de l'anàlisi matemàtica és, fixat un nombre irracional a, provar que el conjunt de nombres donat per la part decimal dels múltiples enters de a (na on n és enter) és un subconjunt dens de l'interval [0, 1]. Hom es troba amb que no sembla fàcil trobar explícitament enters n i m tals que |nama| < e, on e > 0 és un nombre positiu arbitràriament petit i a és un nombre irracional. Però si es pren M tal que 1/M < e, pel principi de les caselles hi ha d'haver n1, n2 ∈ {1, 2, ..., M + 1} tals que n1a i n2a es trobin a la mateixa subdivisió de mida 1/M (només hi ha M trossos d'aquesta mida entre dos enters). En particular, es poden trobar n1n2 tals que n1a és a (p + k/M, p + (k + 1)/M), i n2a és a (q + k/M, q + (k + 1)/M), per a certs pq enters i k a {0, 1, ..., M − 1}. Llavors, es pot verificar que (n2n1)a és a (qp − 1/M, qp + 1/M). Això implica que la part decimal de na és més petita que 1/M que és més petit que e, on n = n2n1 o n = n1n2. Això demostra que 0 és un punt d'acumulació del conjunt. Ara es pot fer servir aquest resultat per demostrar el cas per a p a (0, 1]: amb aquesta n, si p ∈ (0, 1/M] ja hem acabat. Altrament p és a (j/M, (j + 1)/M] i, fent servir els símbols [·] per denotar la part decimal, si es pren k = sup{rN : r[na] < j/M}, s'obté |[(k + 1)na] − p| < 1/M < e.

Referències[modifica | modifica el codi]

  1. «UPCTERM». Servei de Llengües i Terminologia (UPC). [Consulta: 26 juny 2015].
  2. 2,0 2,1 2,2 2,3 2,4 Pla i Carrera, Josep. «El principi de les caselles». A: Sessions de preparació per a l'Olimpíada Matemàtica. Societat Catalana de Matemàtiques, 1999, p. 255–256. ISBN 82-7283-458-1. 
  3. Herstein, I. N.. Topics In Algebra (en anglès). Waltham: Blaisdell Publishing Company, 1964. ISBN 978-0-471-01090-6. 
  4. Miller, Jeff; et al. «Pigeonhole Principle» (en anglès). Earliest Known Uses of Some of the Words of Mathematics p. 90. [Consulta: 26 juny 2015].
  5. Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 3a ed. (en anglès), 1994, p. 277. ISBN 978-0-201-54983-6. 
  6. Brualdi, Richard A. Introductory Combinatorics (en anglès). Pentice Hall, 2010, p. 74. ISBN 978-0-13-602040-0.