Usategi printzipio

Matematikan, Usategi printzipioak $n>m$ izanik $n$ elementu $m$ kaxetan sartzen direnean kaxa batek gutxienez elementu bat baino gehiago izan behar duela ezartzen duen teorema edo printzipioa da. Teorema honen izena usategietan sarritan ikusten den kasuarengatik ezarrita dago. Askotan, $m$ habiko usategi batean, habi kopuru baino uso gehiago egoten dira. Ondorioz, habietako batean (edo batzuetan) uso bat baino gehiago ipini beharko dira. Horri, Usategiaren printzipioa deritzogu.

Usategi printzipioa: 9 txokotan 10 uso sartzen badira (m=9, n=10), ezinbestean izango da txoko bat 2 uso edo gehiagorekin.

Matematikoki ere azaldu dezakegu:

Izan bitez $n,m\in$ $\mathbb {N}$. Orduan, $n$ objektu $m$ multzotan banatzen baditugu eta

• $n>m$ bada, orduan gutxienez bi objektu multzo berean egon beharko dira (printzipio arrunta).
• existitzen bada $k\in \mathbb {N}$ zeinetarako $n>km$ den, orduan gutxienez $k+1$ objektu multzo berean egongo dira (printzipio orokortua).

Printzipioa maiz erabiltzen matematikako frogapenetan, batik bat konbinatorian, eta informatikan.

Lehenengo aldiz Dirichlet matematikariak 1834. urtean erabili zuela uste da, Schubfachprinzip edo kajoien printzipioa esapidea erabiliz.

Frogapena (Printzipio orokortua)

Frogapen honetarako printzipio orokortuari begiratuko diogu, arrunta orokortuaren kasu berezi bat denez ($k=1$ kasua), orokortua frogatzerakoan, arrunta ere frogatuko dugu. Erabiliko dugun metodoa Absurdura eramatearen metodoa erabiliko dugu ( kontraesana izenaz ere ezagutua).

Demagun, multzo (habi) guztietan $k$ objektu edo gutxiago daudela. Orduan, $m$ multzo dauzkagunez, gehienez $km$ objektu izan ditzakegu guztira. Baina, $n>km$ baldin bada ezinezkoa izango litzateke objektu guztiak $n$ multzoetan kokatzea. Kontraesan bat lortu dugu, beraz ondorioztatu dezakegu asumitu duguna gezurra dela, hau da; multzo guztietan $k$ objektu edo gutxiago egotea ezinezkoa da $n>km$ baldin bada. Orduan, $n>km$ denetarako, gutxienez $k+1$ objektu multzo berean egongo direla frogatu dugu (Usategiaren printzipio orokortua).

Printzipioa kardinalak erabiliz

Printzipio hau kardinalen bitartez adierazi dezakegu,

$Card(A)>Card(B)$ bada, hau da: A multzoko elementu kopurua B multzokoa baino handiagoa bada, $A$-tik $B$-rako funztio injektiboa ez da existitzen.

Enuntziatua

Dirichleten usategiaren printzipioa. Hartu edozein n,m,p zenbaki natural, np+m uso n kaxatan sartui nahi badituzu, kaxa batek behintzat p+1 uso eduki behar ditu.

Frogapena

Kaxa bakoitzak gehienez p objektu baditu, kokatu ditzakegun objektu kopuru totala np<np+1≤ np+m.

Bere bertsio sinplenean, n>m bada, m elementu eta n elementuen artean aplikazio injektiborik ez dela existitzen dio. Baliokidea da honako hau, m objektu n kaxetan kokatu nahi izanez gero, m>n bada, kaxa batean behintzat bi o objektu egon behar dira.

Aplikazioak

Usategiaren printzipioak behaketa tribialaren itxura duen arren, aurreikusi ezin diren emaitzak kalkulatzeko balio du.

Kanpo estekak

• Datuak: Q188276