[10] Principiul lui Dirichlet / Principiul cutiei

Elemente de Matematică și Informatică. Teorie, Probleme. Discuții.
User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

[10] Principiul lui Dirichlet / Principiul cutiei

Postby Admin » 25 Jan 2013, 01:50

Image
Principiul lui Dirichlet (sau Principiul cutiei .. sau al sertarelor .. sau al porumbeilor - în engleză se mai numeşte Pigeonhole principle) este o teoremă matematică ce afirmă că dacă există n obiecte dispuse în n-1 cutii, atunci există cel puțin o cutie care conține cel puţin două obiecte.

Chiar dacă principiul lui Dirichlet este binecunoscut, originile lui sunt obscure.
Acest principiu a fost folosit de către Dirichlet într-o lucrare din 1879, dar a fost cu siguranță folosit anterior : Gauss a folosit acest principiu în "Disquisitiones Arithmeticae" (1801) și este foarte probabil ca el să fi fost folosit și mai înainte în Matematică.

Principiul lui Dirichlet - ro.wikipedia.org
Pigeonhole principle - en.wikipedia.org

PS.
Prin simplitatea lui acest principiu se poate explica şi la clasa a 5-a.
Am ales prezentarea lui într-un topic din "zona de teorie" pentru clasa a 10-a deoarece principiul are multe aplicaţii în Combinatorică. Dar în general aplicaţiile lui sunt în zone vaste din Matematică.



User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

[10] Principiul lui Dirichlet / Principiul cutiei

Postby Admin » 02 Feb 2013, 23:04

Principiul lui Dirichlet Extins - Extended Pigeonhole Principle

Dacă nk+1 obiecte sunt aşezate în n cutii, atunci cel puţin o cutie va conţine cel puţin k+1 obiecte.
If nk+1 objects are placed in n boxes, then (at least) one of the boxes must contain at least k+1 objects.

Remarcă
În formulările în limba engleză (dar şi în multe locuri în română) lipseşte cel mai adesea expresia "at least" ("cel puţin") atunci când se face "referire la cutii". Ori acesta e un element totuşi important. Sunt probleme care chiar se bazează mai mult pe numărul cutiilor care conţin cel puţin x obiecte ...

De exemplu, dacă avem 3001 obiecte de aşezat în 1000 de cutii atunci avem "măcar" o cutie cu "minim" 4 obiecte.
Să ne gândim că punem 1000 obiecte într-o cutie, 2001 în altă cutie .. iar restul cutiilor rămân goale.
Deci avem 2 cutii cu minim 4 obiecte.

User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

[10] Principiul lui Dirichlet / Principiul cutiei

Postby Admin » 02 Feb 2013, 23:19

Principiul lui Dirichlet Generalizat - Generalized Pigeonhole Principle

Presupunem că avem nk+s sau mai multe obiecte de aşezat în n cutii.
Atunci pentru fiecare m, care verifică 0 ≤ m ≤ n , există m cutii care au împreună cel puţin mk + min(s,m) obiecte.


Suppose nk+s or more objects are placed in n boxes.
Then for each 0 ≤ m ≤ n there exist m boxes with a total of at least mk + min(s,m) objects.

User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

[10] Principiul lui Dirichlet / Principiul cutiei

Postby Admin » 30 Jul 2022, 17:12

Image

User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

[10] Principiul lui Dirichlet / Principiul cutiei

Postby Admin » 01 Jan 2023, 18:39

Problemă. Se dă un pătrat cu latura de lungime $1$.
Să se arate că oricum am alege $5$ puncte interioare lui
există cel puțin $2$ astfel încât distanța dintre ele să fie mai mică decât $\dfrac{\sqrt{2}}{2}$.

Rezolvare - Principiul lui Dirichlet (principiul cutiei)

și împărțirea în $4$ pătrate identice, ca în imagine.

Image


Return to “Teorie și Probleme”

Who is online

Users browsing this forum: No registered users and 6 guests

mateinfo
UP
cron