„Skatulyaelv” változatai közötti eltérés

A Wikipédiából, a szabad enciklopédiából
[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
élesítés
→‎Példa: softball, zoknik
5. sor: 5. sor:
A skatulyaelv indirekt módon bizonyítható: ha az elv nem igaz, akkor minden skatulyába legfeljebb egy elem kerül. Ekkor legfeljebb annyi elem van, ahány skatulya. Ellentmondás.
A skatulyaelv indirekt módon bizonyítható: ha az elv nem igaz, akkor minden skatulyába legfeljebb egy elem kerül. Ekkor legfeljebb annyi elem van, ahány skatulya. Ellentmondás.
==Példa==
==Példa==
===Hajszálszám===
Egyszerűsége ellenére a skatulyaelvvel érdekes következtetésekre lehet jutni, például, hogy van legalább két [[budapest]]i lakos, akiknek pontosan ugyanannyi szál haja van.
Egyszerűsége ellenére a skatulyaelvvel érdekes következtetésekre lehet jutni, például, hogy van legalább két [[budapest]]i lakos, akiknek pontosan ugyanannyi szál haja van.


A bizonyításhoz mindenkihez hozzárendeljük a hajszálaik pontos számát. Egy ember hajszálainak száma általában 100 000 és 200 000 közötti. Feltehetjük, hogy senkinek sincs egy milliónál több hajszála. márpedig Budapesten több, mint egy millióan laknak.
A bizonyításhoz mindenkihez hozzárendeljük a hajszálaik pontos számát. Egy ember hajszálainak száma általában 100 000 és 200 000 közötti. Feltehetjük, hogy senkinek sincs egy milliónál több hajszála. márpedig Budapesten több, mint egy millióan laknak.
===Softball===
Öt lány [[softball]]t akar játszani, de nem akarnak ugyanabba a csapatba kerülni, és csak négy csapatba jelentkezhetnek. Mivel lehetetlen az öt lányt úgy elosztani a négy csapat között, hogy mindegyikbe legfeljebb egy jusson, így a skatulyaelv szerint lesz, aki hoppon marad.
===Zoknik===
Legyen egy dobozban 10 fekete, és 12 fehér zokni. Sorra vesszük ki a zoknikat úgy, hogy nem nézünk a dobozba. Legfeljebb hány zoknit kell kivenni, hogy legyen köztük egy pár?

A skatulyaelv szerint, mivel két szín van, ezért a harmadik zokni színe meg fog egyezni egy korábban kihúzott zokniéval. Ha tehát az első két zokni különböző színű, akkor a következő zokni már párt alkot valamelyikkel.

==Élesítés==
==Élesítés==
A skatulyaelv így élesíthető:
A skatulyaelv így élesíthető:

A lap 2010. június 22., 13:56-kori változata

A skatulyaelv az a Dirichlet által megfogalmazott matematikai elv, mely szerint ha n és m pozitív egészek és n>m, akkor n elemet m skatulyába helyezve kell lennie olyan skatulyának, amelyben 1-nél több elem van.

Másképpen megfogalmazva: nem létezik olyan véges halmazokon értelmezett injektív függvény, amelynek az értékkészlete kisebb, mint az értelmezési tartománya.

Bizonyítás

A skatulyaelv indirekt módon bizonyítható: ha az elv nem igaz, akkor minden skatulyába legfeljebb egy elem kerül. Ekkor legfeljebb annyi elem van, ahány skatulya. Ellentmondás.

Példa

Hajszálszám

Egyszerűsége ellenére a skatulyaelvvel érdekes következtetésekre lehet jutni, például, hogy van legalább két budapesti lakos, akiknek pontosan ugyanannyi szál haja van.

A bizonyításhoz mindenkihez hozzárendeljük a hajszálaik pontos számát. Egy ember hajszálainak száma általában 100 000 és 200 000 közötti. Feltehetjük, hogy senkinek sincs egy milliónál több hajszála. márpedig Budapesten több, mint egy millióan laknak.

Softball

Öt lány softballt akar játszani, de nem akarnak ugyanabba a csapatba kerülni, és csak négy csapatba jelentkezhetnek. Mivel lehetetlen az öt lányt úgy elosztani a négy csapat között, hogy mindegyikbe legfeljebb egy jusson, így a skatulyaelv szerint lesz, aki hoppon marad.

Zoknik

Legyen egy dobozban 10 fekete, és 12 fehér zokni. Sorra vesszük ki a zoknikat úgy, hogy nem nézünk a dobozba. Legfeljebb hány zoknit kell kivenni, hogy legyen köztük egy pár?

A skatulyaelv szerint, mivel két szín van, ezért a harmadik zokni színe meg fog egyezni egy korábban kihúzott zokniéval. Ha tehát az első két zokni különböző színű, akkor a következő zokni már párt alkot valamelyikkel.

Élesítés

A skatulyaelv így élesíthető:

Ha n elemet k halmazba osztunk, és n > k, akkor van legalább egy halmaz, ami legalább (n-1)/k elemet tartalmaz.

Az elv kombinatorikus általánosításaival a Ramsay-elmélet foglalkozik.