Principiul cutiei (Principiul lui Dirichlet)

Principiul cutiei (Principiul lui Dirichlet)

Principiul cutiei: Dacă n+1n+1 obiecte sunt puse în nn cutii (n∈N∗n \in \N^*), atunci cel puțin o cutie conține mai mult de un obiect.

Principiul cutiei (varianta generalizată): Dacă n⋅k+1n\cdot k+1 obiecte sunt puse în nn cutii (n,k∈N∗n,k \in \N^*), atunci cel puțin o cutie conține mai mult de kk obiecte.

Principiul cutiei (varianta pentru o infinitate de elemente): Dacă o infinitate de elemente sunt împărțite într-un număr finit de părți (cutii), atunci cel puțin o parte va conține o infinitate de elemente.

Observație: În probleme vom stabili elementele care corespund cutiilor și elementele care corespund obiectelor.

Nivel introductiv

E.725. Arătați că din 88 persoane se pot alege două care să fie văzute în aceeași zi a săptămânii.

Mate2000 excelență, 1/37
Soluție
Soluție:

Considerăm:

  • 77 cutii, corespunzătoare celor 77 zile ale săptămânii;
  • 88 obiecte, corespunzătoare celor 88 persoane.

Conform principiului cutiei, cel puțin o cutie va conține două sau mai multe obiecte. Altfel spus, există cel puțin o zi a săptămânii în care pot fi văzute două sau mai multe persoane.

E.727. Arătați că:
a) din orice 1010 numere naturale nenule putem alege două care încep cu aceeași cifră;
b) din orice 1111 numere naturale putem alege două care se termină cu aceeași cifră.

Art, Matematică pentru excelență, 29/136
Soluție
Soluție:

a) Considerăm:

  • 99 cutii, corespunzătoare celor 99 cifre cu care poate începe un număr nenul;
  • 1010 obiecte, corespunzătoare celor 1010 numere nenule alese.

Conform principiului cutiei, cel puțin o cutie va conține mai mult de un obiect. Altfel spus, printre cele 1010 numere disponibile există cel puțin două numere care încep cu aceeași cifră.

b) Considerăm:

  • 1010 cutii, corespunzătoare celor 1010 cifre cu care se poate termina un număr natural;
  • 1111 obiecte, corespunzătoare celor 1111 numere alese.

Conform principiului cutiei, cel puțin o cutie va conține mai mult de un obiect. Altfel spus, printre cele 1111 numere disponibile există cel puțin două numere care se termină cu aceeași cifră.

E.728. În interiorul unui dreptunghi 6×4,6 \times 4, care este împărțit în pătrate 1×1,1 \times 1, se desenează 2525 de puncte, astfel încât niciunul dintre acestea să nu fie pe laturile pătratelor. Arătați că exista cel puțin un pătrat 1×11 \times 1 care conține două puncte distincte.

Art, Matematică pentru excelență, 1/139
Soluție
Soluție:

Considerăm:

  • 2424 cutii, corespunzătoare celor 2424 pătrate 1×11 \times 1;
  • 2525 obiecte, corespunzătoare celor 2525 puncte.

Conform principiului cutiei, cel puțin o cutie va conține mai mult de un obiect. Altfel spus, există cel puțin un pătrat 1×11 \times 1 care conține cel puțin două puncte distincte.

E.726. Într-o clasă sunt 2929 elevi. Arătați că dintre ei putem alege 55 elevi care s-au născut în aceeași zi din săptămână.

Mate 2000 excelență, 2/37
Soluție
Soluție:

Considerăm:

  • 77 cutii, corespunzătoare celor 77 zile ale săptămânii;
  • 7⋅4+17 \cdot 4 +1 obiecte, corespunzătoare celor 2929 elevi.

Conform principiului cutiei (varianta generalizată), cel puțin o cutie va conține mai mult de 44 obiecte. Altfel spus, există cel puțin o zi a săptămânii în care s-au născut 55 sau mai mulți elevi.

E.730. Într-o clasă sunt 3737 de elevi. Arătați că există o lună a anului în care cel puțin 44 elevi își sărbătoresc ziua de naștere.

Aritmetică pentru excelență, Artur Bălăucă, 1/101
Soluție
Soluție:

Considerăm:

  • 1212 cutii, corespunzătoare celor 1212 luni ale săptămânii;
  • 12⋅3+112 \cdot 3 +1 obiecte, corespunzătoare celor 3737 de elevi.

Conform principiului cutiei (varianta generalizată), cel puțin o cutie va conține mai mult de 33 obiecte. Altfel spus, există cel puțin o lună în care își sărbătoresc ziua 44 sau mai mulți elevi.

E.729. Cei 2828 de elevi ai clasei a 5-a D au ochii albaștri, verzi sau căprui. Arătați că printre aceștia există cel puțin 1010 elevi care au aceeași culoare a ochilor.

Art, Matematică pentru excelență, 3/139
Soluție
Soluție:

Considerăm:

  • 33 cutii, corespunzătoare celor 33 culori;
  • 3⋅9+13 \cdot 9 + 1 obiecte, corespunzătoare celor 2828 de elevi.

Conform principiului cutiei (forma generalizată), cel puțin o cutie va conține mai mult de 99 obiecte. Altfel spus, există cel puțin 1010 elevi care au aceeași culoare a ochilor.

E.731. Scriem la rând 20242024 de numere naturale nenule distincte, cu proprietatea că suma oricăror două numere vecine este un număr par.
a) Arătați că oricum am alege șapte numere dintre cele 20242024 de numere, există cel puțin două numere a căror diferență este divizibilă cu 12.12.
b) Demonstrați că cea mai mică sumă posibilă a celor 20242024 de numere este un număr pătrat perfect.

Olimpiadă, etapa locală, Ilfov, 2024
Soluție
Soluție:

a) Diferența a două numere este divizibilă cu 1212 dacă numerele dau același rest la împărțirea cu 12.12. Prin urmare, este suficient să arătăm că printre cele 77 numere există două care dau același rest la împărțirea cu 12.12.

Deoarece suma oricăror două numere alăturate este pară, toate numerele au aceeași paritate.

  • Dacă toate numerele sunt pare, ele dau rest par la împărțirea cu 1212 și pot fi de forma 12ki+r, r∈{0,2,4,6,8,10}.12k_i+r,~r \in \{0,2,4,6,8,10\}.
  • Dacă toate numerele sunt impare, ele dau rest impar la împărțirea cu 1212 și pot fi de forma 12ki+r, r∈{1,3,5,7,9,11}.12k_i+r,~r \in \{1,3,5,7,9,11\}.

În fiecare caz în parte sunt 66 resturi posibile. Așadar, alegem:

  • 6 cutii, corespunzătoare celor 66 forme posibile;
  • 7 obiecte, corespunzătoare celor 77 numere alese.

Conform principiului cutiei, există cel puțin două numere care dau același rest la împărțirea cu 12,12, deci diferența lor va fi divizibilă cu 12.12.

b) Pentru că numerele sunt nenule, cea mai mică sumă se obține pentru primele 20242024 de numere impare consecutive:
S=1+3+5+…+4047=20242.S=1+3+5+ \ldots + 4047 =2024^2.

E.724. Arătați că oricum am alege nouă numere naturale, găsim trei dintre ele astfel încât suma sau diferența oricăror două să dea un multiplu al lui 7.

Olimpiadă, etapa locală, Olt, 2018
GM 3/2017
Soluție
Soluție:

La împărțirea cu 77 putem obține resturile: 0,1,2,3,4,50, 1, 2, 3, 4, 5 sau 6.6. Să vedem întâi cum am putea grupa aceste numere pentru a obține triplete cu proprietatea din enunț:

  • {0,0,0}\{0,0,0\};
  • {1,1,1},{1,1,6},{1,6,1},{1,6,6},{6,1,1},{6,1,6},{6,6,1},{6,6,6}\{1,1,1\}, \{1,1,6\}, \{1,6,1\}, \{1,6,6\},\{6,1,1\}, \{6,1,6\},\{6,6,1\},\{6,6,6\} (toate combinațiile de 11 și 66);
  • {2,2,2},{2,2,5},…,{5,5,5}\{2,2,2\}, \{2,2,5\}, \ldots,\{5,5,5\};
  • {3,3,3},{3,3,4},…,{4,4,4}\{3,3,3\}, \{3,3,4\}, \ldots,\{4,4,4\}.

De aici ne vine ideea să folosim principiul cutiei, cu 44 cutii:

  • numere care dau restul 0;0;
  • numere care dau restul 11 sau 6;6;
  • numere care dau restul 22 sau 5;5;
  • numere care dau restul 33 sau 4.4.

Având 99 numere, există cel puțin o cutie cu 33 numere. Acestea sunt numerele căutate.
Justificare: Pentru oricare două dintre cele trei numere din aceeași cutie avem două posibilități:

  • cele două numere dau același rest și atunci diferența lor se divide cu 7;7;
  • cele două numere dau resturi diferite și atunci suma lor se divide cu 7.7.
Nume CreatLa (UTC)
Principiul cutiei (Principiul lui Dirichlet) 01-03-2025 06:14