Principiul lui Dirichlet / Principiul cutiei

Principiul lui Dirichlet / Principiul cutiei

Post by Admin » 25 Jan 2013, 02:50     Share on Facebook   Facebook  

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ă.

Produse evoMAG.ro
User avatar
Admin
Site Admin
 
Posts: 1322
Joined: 22 Jan 2012, 15:23
Location: România

Re: Principiul lui Dirichlet / Principiul cutiei

Post by Admin » 03 Feb 2013, 00:04     Share on Facebook   Facebook  

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: 1322
Joined: 22 Jan 2012, 15:23
Location: România

Re: Principiul lui Dirichlet / Principiul cutiei

Post by Admin » 03 Feb 2013, 00:19     Share on Facebook   Facebook  

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: 1322
Joined: 22 Jan 2012, 15:23
Location: România


Return to Cls. 10

Who is online

Users browsing this forum: No registered users and 0 guests

cron