Principiul lui Dirichlet

Principiul lui Dirichlet (sau al sertarelor) este o teoremă matematică ce afirmă că dacă există n obiecte dispuse în n-1 cutii, atunci există o cutie care conține cel puțin două obiecte. Chiar dacă principiul lui Dirichlet este binecunoscut, originile lui sunt obscure. Acest principiu este menționat de către Dirichlet într-o lucrare din 1879, dar există cu siguranță utilizări anterioare: de exemplu în opera lui Gauss Disquisitiones Arithmeticae (1801) și este foarte probabil ca el să fi fost folosit și mai înainte în literatură. Descrierea axiomatică a numerelor naturale de către Giuseppe Peano avea să intervină abia în 1889 și avea să fie apreciată de către Russel abia în 1919.

Demonstrație

Presupunem prin absurd că cineva a reușit să plaseze n obiecte în n-1 cutii în condițiile din enunț, fără însă ca vreuna din cutii să conțină mai mult de un singur obiect. Atunci în fiecare cutie găsim maximum un obiect. Vom avea așadar două tipuri de cutii :

  • cutii cu câte un obiect
  • cutii goale.

Nu se poate ca toate cutiile să fie goale, deoarece avem mai multe obiecte decât cutii. Atunci există o cutie care conține un obiect. Înlăturăm acea cutie și obiectul conținut în ea.

Rămâne o situație în care avem n-1 obiecte plasate în n-2 cutii.

După încă n-3 astfel de operații de înlăturare obținem o ultimă cutie, care conține două obiecte. Aceasta însă contravine presupunerii inițiale.

Astfel, presupunerea de mai sus este falsă, iar Principiul lui Dirichet este cu necesitate adevărat. Q.E.D.

Enunțuri echivalente

Forma funcțională

Dacă A și B sunt mulțimi cu |A| > |B|, atunci pentru fiecare funcție f:A-->B găsim un element b în B astfel încât |f-1(b)| > 1.

Forma partițională

Fie P o partiție a unei mulțimi A, astfel că P are mai puțin de |A| părți. Atunci una dintre părți conține mai mult decât un singur element al lui A.

Exemple

Exemplul 1

Există un număr de n perechi de pantofi de mărimi diferite, dar neordonați pe perechi. Care este numărul minim de pantofi care trebuie cercetați pentru a forma o pereche?

Răspunsul este evident: Utilizăm câte o cutie (inițial goală) pentru fiecare mărime. După așezarea în cutii a n+1 pantofi, o cutie va conține doi pantofi. Deci în mod sigur vom reuși ca al (n+1)-lea pantof să îl putem împerechea cu unul din cei n anterior selectați.

Exemplul 2

Se consideră vectorul v → = ( a 1 , a 2 , ⋯ , a n ) , {\displaystyle {\vec {v}}=(a_{1},a_{2},\cdots ,a_{n}),} cu coordonatele numere naturale. Se caută indicii i < j {\displaystyle i<j} cu proprietatea ca a i + ⋯ + a j {\displaystyle a_{i}+\cdots +a_{j}} să fie multiplu de n.

Vom nota pentru orice x ∈ N {\displaystyle x\in \mathbb {N} } prin x ^ {\displaystyle {\hat {x}}} clasa sa de echivalență modulo n.

Considerăm sumele s k = a 1 + ⋯ + a k {\displaystyle s_{k}=a_{1}+\cdots +a_{k}} pentru k = 1 , ⋯ , n . {\displaystyle k=1,\cdots ,n.} Fie s ^ k {\displaystyle {\hat {s}}_{k}} clasele de echivalență corespunzătoare.

Avem cazurile:

1) dacă există k cu s ^ + x = 0 ^ , {\displaystyle {\hat {s}}+x={\hat {0}},} atunci o soluție este ( i , j ) = ( 1 , k ) . {\displaystyle (i,j)=(1,k).}

2) în caz contrar, este clar că s ^ 1 , ⋯ , s ^ n ∈ . {\displaystyle {\hat {s}}_{1},\cdots ,{\hat {s}}_{n}\in .} Conform principiului lui Dirichlet, vor exista indicii k < 1 {\displaystyle k<1} cu s ^ k = s 1 . {\displaystyle {\hat {s}}_{k}=s_{1}.} Atunci o soluție este ( i , j ) = ( k + 1 , 1 ) . {\displaystyle (i,j)=(k+1,1).}

Vezi și

  • Teoria lui Ramsey
  • Combinatorică

Bibliografie

  • Ronald L. Graham, Martin Grötschel and László Lovász, Handbook of Combinatorics Arhivat în , la Wayback Machine. vol. 2, MIT Press, 1995