Principiul cutiei: probleme și pragul minim

Principiul cutiei spune că, dacă așezi mai multe obiecte decât cutii, cel puțin o cutie conține minimum două obiecte. Ca să îl folosești într-o problemă, trebuie să precizezi ce reprezintă obiectele, ce reprezintă cutiile și de ce fiecare obiect intră într-una dintre ele. Principiul demonstrează că o situație este inevitabilă; nu îți spune întotdeauna unde apare.

De exemplu, dacă pui 9 creioane în 8 pahare, nu poți păstra cel mult un creion în fiecare pahar. Chiar dacă șapte pahare rămân goale, concluzia rămâne adevărată: un pahar are cel puțin două creioane. Nu trebuie ca distribuirea să fie uniformă sau aleatoare.

De ce funcționează principiul cutiei?

Presupune că fiecare dintre cele 8 pahare ar conține cel mult un creion. Atunci ai avea cel mult 8 creioane în total. Dar enunțul spune că ai 9. Contradicția arată că presupunerea este imposibilă.

Această demonstrație îți oferă și o metodă de lucru: calculezi câte obiecte încap dacă situația cerută nu apare, apoi adaugi unul. Pentru a garanta două obiecte într-o cutie, ai nevoie de un obiect mai mult decât numărul cutiilor.

Atenție la cuvinte: „cel puțin două” permite și trei, patru sau nouă. Concluzia „exact două” ar fi falsă pentru distribuirea în care toate cele 9 creioane ajung în același pahar.

Exemplul 1: aceeași lună de naștere

La un atelier participă 25 de elevi. Arată că minimum trei dintre ei sunt născuți în aceeași lună, fără să cunoști datele lor de naștere.

Obiectele sunt cei 25 de elevi. Cutiile sunt cele 12 luni ale anului. Fiecare elev intră în cutia lunii în care s-a născut. Dacă în fiecare lună ar fi cel mult doi elevi, totalul ar fi cel mult $12\cdot2=24$. Al douăzeci și cincilea elev obligă una dintre luni să conțină minimum trei persoane.

Nu afirmăm că acei elevi sunt născuți în aceeași zi sau în același an. Am grupat doar după lună. Nici nu trebuie să presupunem că lunile de naștere sunt la fel de frecvente: demonstrația acoperă orice distribuire.

Este suficient un grup de 24? Nu pentru o garanție: pot exista exact doi elevi născuți în fiecare lună. Am construit astfel un caz în care concluzia nu apare. Împreună, demonstrația pentru 25 și contraexemplul pentru 24 dovedesc că pragul minim este 25.

Exemplul 2: extragi șosete fără să vezi culoarea

Într-un sertar sunt 6 șosete albastre, 6 gri și 6 verzi. Câte șosete trebuie să scoți fără să te uiți, ca să fii sigur că ai două de aceeași culoare? În acest exercițiu, o pereche înseamnă numai două șosete de aceeași culoare; nu discutăm mărimi sau modele diferite.

Există trei categorii. În cel mai nefavorabil început, primele trei șosete au culori diferite. A patra are obligatoriu una dintre acele culori, deci formează o pereche. Răspunsul este 4.

Dacă vrei să fii sigur că ai trei șosete de aceeași culoare, poți scoate două din fiecare culoare fără să obții încă trei identice. Asta înseamnă 6 șosete. A șaptea garantează rezultatul. Stocul de 6 din fiecare culoare permite distribuirea nefavorabilă folosită în demonstrație.

Dacă ai cere însă două șosete albastre, răspunsul s-ar schimba. Ai putea scoate întâi toate cele 12 șosete gri și verzi, apoi două albastre: ai nevoie de 14 extrageri pentru garanție. „Aceeași culoare” și „o culoare precizată” sunt cerințe diferite.

Care este formula generală?

Dacă ai $m$ cutii și vrei să garantezi că una conține cel puțin $k$ obiecte, sunt suficiente:

$$m(k-1)+1$$

obiecte. Numerele $m$ și $k$ sunt întregi pozitive. Explicația: fără $k$ obiecte într-o cutie, fiecare cutie ar avea maximum $k-1$, deci totalul ar fi cel mult $m(k-1)$.

Formula dă pragul minim când distribuirea cu exact $k-1$ obiecte în fiecare cutie este posibilă. Dacă problema impune stocuri sau alte restricții, poți avea un prag mai mic. De aceea, verifici condițiile înainte să prezinți un număr ca fiind minim.

O altă formulare spune că, din $n$ obiecte distribuite în $m$ cutii, o cutie conține cel puțin $\lceil n/m\rceil$ obiecte. Simbolul înseamnă rotunjire în sus la primul întreg. Pentru 31 de obiecte și 7 cutii, obții minimum 5 într-o cutie: patru în fiecare ar acoperi doar 28.

Exemplul 3: resturi la împărțirea cu 5

Alegi șase numere întregi distincte. Arată că există două a căror diferență este divizibilă cu 5.

Cutiile sunt resturile posibile la împărțirea cu 5: 0, 1, 2, 3 și 4. Ai șase numere și cinci cutii, deci două numere au același rest. Dacă ele se scriu $5a+r$ și $5b+r$, diferența este $5(a-b)$, un multiplu de 5.

Pentru o verificare concretă, alege 2, 8, 14, 20, 26 și 32. Resturile sunt 2, 3, 4, 0, 1 și 2. Numerele 2 și 32 au diferența 30. Lista verifică un exemplu; demonstrația cu resturi explică de ce funcționează orice alegere admisă.

Cinci numere nu garantează rezultatul: 0, 1, 2, 3 și 4 au resturi diferite, iar nicio diferență dintre două numere distincte nu este multiplu de 5. Acesta este din nou controlul pragului minim.

Argumentul resturilor funcționează și când împărțitorul nu este prim: pentru împărțirea cu șase ai șase clase de resturi. Dacă vrei să lămurești această deosebire, consultă cum recunoști numerele prime. Nu confunda proprietatea împărțitorului cu numărul resturilor posibile.

Exemplul 4: perechi cu sumă fixă

Din numerele naturale de la 1 la 20 alegi 11 numere distincte. Arată că două dintre cele alese au suma 21.

Construiești zece cutii, fiecare fiind o pereche: {1, 20}, {2, 19}, {3, 18}, până la {10, 11}. Fiecare număr de la 1 la 20 apare exact o dată. Dacă ai selecta cel mult un număr din fiecare pereche, ai avea maximum zece numere.

Cum ai ales unsprezece, una dintre perechi este selectată complet. Cele două elemente ale ei au suma 21. Cutiile nu sunt obiecte fizice: le-ai construit după proprietatea pe care vrei să o obții.

Cu zece numere concluzia nu este obligatorie. Poți alege 1, 2, până la 10; suma a două numere distincte din această listă nu depășește 19. Ai arătat atât garanția pentru 11, cât și insuficiența lui 10.

Pentru antrenament, acoperă demonstrația și reconstruiește singur categoriile, apoi verifică pragul cu un contraexemplu. Poți integra această încercare în metoda de lucru la matematică; obiectivul este să poți justifica alegerea cutiilor, nu doar să reciți formula.

Trei exerciții scurte, cu justificare

1. În 6 rafturi așezi 43 de caiete. Ce număr poți garanta pe un raft? Cel puțin 8: șapte pe fiecare ar însemna doar 42. Nu poți garanta 9, fiindcă distribuirea 8, 7, 7, 7, 7, 7 respectă totalul.

2. Câți elevi garantează că patru au aceeași lună de naștere? Răspunsul este 37, deoarece $12\cdot3+1=37$. Cu 36 pot fi exact trei în fiecare lună.

3. Alegi 9 numere întregi. Garantezi două cu diferența divizibilă cu 8? Da: există opt resturi și nouă numere. Nu ai nevoie să calculezi toate cele 36 de diferențe dintre perechi.

Cum recunoști singur cutiile?

Scrie proprietatea comună pe care o cauți: aceeași culoare, același rest, aceeași lună sau apartenența la aceeași pereche. Transform-o într-o clasificare completă. Verifică apoi că fiecare obiect intră într-o singură categorie și că ai numărat toate categoriile.

Dacă vrei să discuți o demonstrație, caută în anunțurile de matematică profesori care menționează probleme de logică sau pregătire pentru concursuri. Adu și contraexemplul pentru pragul imediat mai mic: el arată ce parte a argumentului ai înțeles. Exemplele de aici nu reprezintă o listă de cerințe oficiale pentru un examen.