A mindennapjaink során számtalan alkalommal futunk bele olyan helyzetekbe, ahol véletlenszerűnek tűnő dolgok mögött mégis valamilyen szabályszerűség, logikai összefüggés lapul. Talán észre sem vesszük, de ezek a felismerések teszik lehetővé, hogy megértsünk bonyolult rendszereket, hatékonyabban tervezzünk, vagy egyszerűen csak megbirkózzunk a minket körülvevő információk áradatával. A matematika egyik leghasznosabb és legszebben egyszerű elve éppen ebben segít: megmutatja, hogyan találhatunk rendet a káoszban, hogyan érhetünk el biztos következtetéseket még akkor is, ha nem ismerünk minden részletet. Ez az elv a "skatulya-elv", amelynek ereje és eleganciája sokszor meglepő módon egyszerű példákban rejlik.
Gondoljunk csak bele, hányféleképpen szervezhetünk dolgokat, hogy bizonyos feltételek teljesüljenek. A skatulya-elv pontosan erre kínál egy általános keretet. Lényegében arról szól, hogy ha elegendő számú elemet (mondjuk, becenevet) el kell helyeznünk egy korlátozott számú kategóriába (mondjuk, iskolai osztály), akkor elkerülhetetlenül lesz olyan kategória, amelybe egynél több elem kerül. Ez a látszólag triviális megállapítás azonban mélyebb következményekkel bír, és számos tudományterületen, a számítástechnikától a kombinatorikán át egészen a mindennapi élet logikai fejtörőiig, alkalmazható. Több nézőpontból is megvizsgálhatjuk majd, hogy ez az egyszerű alapelv hogyan válik rendkívül hatékony eszközzé.
Ebben az írásban nem csupán elméleti síkon közelítjük meg a skatulya-elvét. Megismerkedünk a pontos definícióval, feltárjuk a mögötte rejlő logikát, és nem utolsósorban, számos gyakorlati példán keresztül tesszük szemléletessé az alkalmazását. Célunk, hogy ne csupán a képleteket mutassuk be, hanem azt is megértsük, hogyan gondolkodhatunk a skatulya-elv segítségével, hogyan alkalmazhatjuk ezt a szemléletmódot saját problémáink megoldására. Az olvasó tehát nem csak egy elméleti bevezetést kap, hanem olyan ismereteket, amelyekkel gazdagodva képes lesz felismerni és kihasználni az elv erejét a saját környezetében.
A skatulya-elv alapjai
A skatulya-elv, más néven Dirichlet-féle boxed elv, egy rendkívül egyszerű, mégis erőteljes matematikai tétel, amely a kombinatorika egyik alapvető eszköze. Lényege abban rejlik, hogy ha rendelkezünk egy bizonyos számú "tárgyal", és ezeket egy korlátozott számú "dobozba" kell elhelyeznünk, akkor garantáltan lesz olyan doboz, amelybe egynél több tárgy kerül, feltéve, hogy a tárgyak száma meghaladja a dobozok számát. Ez az intuíció által is könnyen megérthető gondolat teszi lehetővé, hogy bizonyos tulajdonságok meglétét igazoljuk anélkül, hogy magukat a konkrét elrendezéseket kellene megvizsgálnunk.
Formálisan megfogalmazva, ha $n$ darab elemet elhelyezünk $m$ darab dobozban, és $n > m$, akkor biztosan lesz legalább egy doboz, amelyben több mint egy elem található. A tétel nem állítja, hogy pontosan mennyi elem lesz egy-egy dobozban, csupán azt garantálja, hogy az eloszlás nem lehet egyenletes, azaz nem helyezhetünk el $n$ darab elemet $m$ dobozba úgy, hogy minden dobozban legfeljebb egy elem legyen, ha $n > m$.
Az elvnek létezik egy általánosított, vagy "erős" változata is. Ez kimondja, hogy ha $n$ darab elemet helyezünk el $m$ darab dobozban, akkor biztosan lesz legalább egy doboz, amelyben legalább $\lceil n/m \rceil$ elem található. Itt a $\lceil x \rceil$ jelölés a "mennyezeti" függvényt jelenti, ami $x$ legkisebb egész számot jelenti, amely nem kisebb, mint $x$. Ez az általánosított forma sokkal több információt hordoz magában, és lehetővé teszi bonyolultabb problémák megoldását is.
"Ahol van korlátozott számú hely, és több dolog, mint hely, ott garantáltan lesz zsúfoltság."
A skatulya-elv magyarázata példákkal
A skatulya-elv megértésének legegyszerűbb módja konkrét példákon keresztül történik. Ezek a példák gyakran hétköznapi helyzeteket modelleznek, ami segít az absztrakt fogalmak levetítésében.
Példa 1: Zoknik a fiókban
Tegyük fel, hogy van egy fiókunkban 10 piros és 10 kék zokni. Hány zoknit kell minimum kivennünk ahhoz, hogy biztosan legyen egy párunk (azaz két azonos színű zoknink)?
Ebben az esetben a "dobozaink" a színek (piros és kék), tehát $m=2$. A "tárgyaink" a kivett zoknik. Ha csak egy zoknit veszünk ki, lehet piros vagy kék. Ha kettőt veszünk ki, lehet két különböző színű (egy piros, egy kék). Viszont, ha a harmadik zoknit is kivesszük, az vagy piros lesz (és akkor már van egy piros párunk) vagy kék lesz (és akkor már van egy kék párunk). A skatulya-elv szerint, ha $n$ a kivett zoknik száma, és $m=2$ a színek száma, akkor ha $n=3$, akkor $n>m$, így biztosan lesz olyan szín, amiből legalább $\lceil 3/2 \rceil = \lceil 1.5 \rceil = 2$ zoknink van. Tehát 3 zoknit kell kivennünk.
Példa 2: Emberek születésnapja
Egy csoportban legalább hány embernek kell lennie ahhoz, hogy biztosan legyen két olyan ember, akinek ugyanazon a napon van a születésnapja? (Mellőzzük a szökőévet, azaz 365 nap van egy évben.)
Itt a "dobozaink" az év napjai, tehát $m=365$. A "tárgyaink" az emberek. Ha azt szeretnénk, hogy biztosan legyen két ember, akinek ugyanazon a napon van a születésnapja, akkor az emberi létszám ($n$) a dobozok számánál ($m$) eggyel többnek kell, hogy legyen. Tehát $n = m+1 = 365 + 1 = 366$. A skatulya-elv szerint, ha 366 ember van, akkor legalább egy napon (dobozban) legalább $\lceil 366/365 \rceil = \lceil 1.0027…\rceil = 2$ embernek (tárgynak) kell születnie.
Példa 3: Pontok elhelyezése egy négyzetben
Tegyük fel, hogy 5 pontot helyezünk el egy 2×2-es négyzet belsejében. Bizonyítsuk be, hogy lesz két olyan pont, amelyek távolsága nem haladja meg $\sqrt{2}$-et.
Ezt a problémát a skatulya-elv általánosított alakjával tudjuk megoldani. Osszuk fel a 2×2-es négyzetet négy egységnyi (1×1) kisebb négyzetre. Ezek lesznek a "dobozaink", tehát $m=4$. Összesen 5 pontot helyezünk el, ezek a "tárgyaink", tehát $n=5$. Mivel $n > m$, a skatulya-elv szerint legalább egy 1×1-es négyzetben legalább $\lceil 5/4 \rceil = 2$ pont lesz. Ha két pont egy 1×1-es négyzetben helyezkedik el, akkor a maximális távolság közöttük a négyzet átlója, ami $\sqrt{1^2 + 1^2} = \sqrt{2}$. Tehát lesz két olyan pont, amelyek távolsága $\sqrt{2}$ vagy annál kisebb.
A skatulya-elv különböző megfogalmazásai
Ahogy az imént láthattuk, a skatulya-elvnek létezik egy alapvető és egy általánosított formája. Ezek a megfogalmazások adják a tétel gerincét, de a lényeg nem változik: a korlátozott erőforrások (dobozok) és a túlzott mennyiségű elem (tárgyak) elkerülhetetlen következményeket generálnak.
- Alapvető skatulya-elv: Ha $n$ elemet helyezünk el $m$ dobozban, és $n > m$, akkor legalább egy dobozban kettő vagy több elem található. Ez a legegyszerűbb és leginkább intuitív megfogalmazás.
- Általánosított skatulya-elv: Ha $n$ elemet helyezünk el $m$ dobozban, akkor legalább egy dobozban legalább $\lceil n/m \rceil$ elem található. Ez a forma lehetővé teszi, hogy pontosabb becsléseket adjunk az elemek maximális számáról egy-egy dobozban.
A jelölések magyarázata:
- $n$: az elemek száma (tárgyak).
- $m$: a dobozok száma (kategóriák, helyek).
- $\lceil x \rceil$: a mennyezeti függvény, ami az $x$ legkisebb egész számot jelenti, amely nem kisebb, mint $x$. Például $\lceil 3.14 \rceil = 4$, $\lceil 5 \rceil = 5$.
Ezek a megfogalmazások alapvetőek a tétel megértéséhez és alkalmazásához. Az, hogy melyik megfogalmazást használjuk, attól függ, hogy milyen mértékű bizonyosságot vagy becslést szeretnénk elérni a problémánkban.
Skatulya-elv a gyakorlatban: alkalmazások és példák
A skatulya-elv nem csupán egy elméleti matematikai fogalom, hanem rendkívül hasznos eszköz számos területen. A mindennapi élettől kezdve egészen a fejlett tudományos kutatásokig, ahol csak véges számú erőforrást kell véges számú kategóriába sorolni, ott felbukkanhat a skatulya-elv ereje.
Számítástechnika és algoritmizálás
A számítástechnika egyik alapvető területe, ahol a skatulya-elv szerepet játszik, az algoritmusok elemzése, különösen az adatstruktúrák és a keresési algoritmusok vizsgálatakor.
Példa: Keresés egy rendezett listában
Tegyük fel, hogy van egy $N$ elemű, rendezett listánk, és egy adott elemet keresünk benne. Bináris kereséssel (felező keresés) maximum $\lceil \log_2 N \rceil$ lépésre van szükségünk ahhoz, hogy megtaláljuk az elemet, vagy megállapítsuk annak hiányát.
Itt a "dobozaink" a lista azon részei, amelyeket az algoritmus minden lépésben vizsgál. Minden lépésben a lista felére csökkentjük a keresési tartományt. Gondolhatjuk úgy is, hogy $N$ elem keresése során, ha a lista felére csökkentjük a keresési tartományt, akkor a lehetséges helyek száma exponenciálisan csökken. Ez végső soron egy logaritmikus viselkedéshez vezet, amely a skatulya-elv általánosított formájából is levezethető. Ha a $k$ lépés után fennmaradó lehetséges helyek száma 1, akkor $N$ elemet $k$ lépésben tudunk megkülönböztetni, ami $\log_2 N$ körüli értékhez vezet.
Bizonyítások és matematikai problémák
A skatulya-elv számos matematikai bizonyításban kap szerepet, ahol eleganciájával és erejével egyszerűsíti le a bonyolultnak tűnő problémákat.
Példa: Az irrationális számok létezése
Bizonyítsuk be, hogy léteznek irracionális számok. Ez a bizonyítás nem közvetlenül a skatulya-elvvel történik, de az elv inspirálhatja a gondolkodásmódot. Egy bonyolultabb bizonyításban, például arra, hogy nem minden racionális szám írható fel egy adott alakban, eljuthatunk ahhoz a ponthoz, hogy véges számú "engedélyezett" alak van, de végtelen sok szám, amit el kell helyeznünk. Ekkor a skatulya-elv azt garantálja, hogy lesz olyan szám, amely nem fér bele az engedélyezett alakok egyikébe sem.
Egy másik példa: Tegyünk fel, hogy $n$ különböző egész szám van. Ha ezeket elosztjuk $n$-1-gyel, akkor a maradékok $0, 1, 2, \dots, n-2$ lehetnek. Mivel $n$ darab számunk van, és $n-1$ lehetséges maradék, a skatulya-elv szerint lesz legalább két olyan szám, amelyeknek ugyanaz a maradékuk az $n-1$-gyel való osztáskor. Ez azt jelenti, hogy e két szám különbsége osztható lesz $n-1$-gyel.
Gráfelmélet
A gráfelméletben is találkozunk a skatulya-elvvel, ahol a csomópontok és élek tulajdonságait vizsgáljuk.
Példa: Kötelező csomópontok fokszáma
Egy nem üres gráfban, ahol minden csomópontnak van legalább egy szomszédja (azaz nem izolált csomópontok vannak), biztosan van legalább két olyan csomópont, amelyeknek azonos a fokszáma (azaz azonos számú szomszédjuk van).
A probléma megközelítése: Tegyük fel, hogy az $N$ csomópontból álló gráfban minden csomópont fokszáma különböző. A lehetséges fokszámok $0, 1, 2, \dots, N-1$. Azonban, ha létezik egy $N-1$ fokszámú csomópont (azaz minden más csomóponthoz kapcsolódik), akkor nem létezhet $0$ fokszámú csomópont (egyik sem izolált). Tehát a lehetséges fokszámok halmaza $1, 2, \dots, N-1$ (ha van $N-1$ fokszámú csomópont) vagy $0, 1, \dots, N-2$ (ha nincs $N-1$ fokszámú csomópont, mert pl. van egy $N-1$ fokszámú csomópont). Mindkét esetben legfeljebb $N-1$ különböző fokszám létezhet az $N$ csomópontra. A skatulya-elv szerint, ha $N$ csomópontunk van, és legfeljebb $N-1$ féle fokszám lehet, akkor lesz legalább két csomópont, amelynek azonos a fokszáma.
Játékelmélet
A játékelméletben a skatulya-elv segíthet a stratégiák elemzésében és olyan helyzetek megértésében, ahol a játékosok lépései korlátozottak.
Példa: Cédulák húzása
Tegyünk fel, hogy van 5 cédulánk, amelyekre az 1, 2, 3, 4, 5 számok vannak írva. Két játékos felváltva húz egy-egy cédulát. Az a játékos nyer, aki előbb gyűjt össze olyan számokat, amelyek összege 10. Hány cédulát kell egy játékosnak minimum húznia ahhoz, hogy biztosan nyerjen?
Ez a probléma egy kicsit trükkösebb, és itt is a skatulya-elv általánosított formája segíthet. A lehetséges nyerő kombinációk (összeg 10) a következők lehetnek: (1,2,3,4), (1,4,5), (2,3,5). Ezek a halmazok. Ha egy játékosnak 3 cédulája van, és ezek nem alkotnak nyerő kombinációt, akkor lehet, hogy nem nyert még. Azonban, ha 4 cédulája van, akkor a lehetséges 5 cédula közül 4 van nála. A 5 cédula "dobozként" képzelhető el. Ha már 4 cédulát húzott, akkor a megmaradt 1 cédula "kiegészítheti" a már meglévőket egy nyerő kombinációvá.
Egy másik megközelítés: a lehetséges nyerő összegek (nem a konkrét cédulák) képzelhetők el dobozként. Három lehetséges nyerő halmaz van. Ha egy játékosnak 4 cédulája van, akkor a 4 cédulából bármely 3 kiválasztása is lehet nyerő szubhalmaz. A skatulya-elv ebben az esetben arra enged következtetni, hogy ha elegendő számú cédulát húzunk, amelyek "kitöltenek" bizonyos mintázatokat, akkor elkerülhetetlenül elérjük a győzelmet. Pontosabban, ha 4 cédulánk van, akkor a következő esetek lehetségesek:
- A 4 cédula már eleve egy nyerő kombináció (pl. 1, 4, 5).
- A 4 cédulából 3 cédula alkot egy nyerő kombinációt, a 4. pedig kiegészíti azt. (pl. 1, 2, 3, 4 – itt 1,2,3 nem nyerő, de az összeg 10).
A lényeg az, hogy 4 cédulával már biztosan nem lehet elveszíteni a játékot.
Azonban, ha a kérdés az, hogy mennyi cédulát kell húzni biztosan a nyeréshez, akkor egy kicsit át kell gondolni. A nyerő kombinációk: (1,2,3,4), (1,4,5), (2,3,5). Ezek a lehetséges halmazok.
Ha a játékos 3 cédulát húz, lehetséges, hogy a (1,2,3) van nála, ami nem nyerő.
Ha a játékos 4 cédulát húz, a 5. cédula megmarad.
- Ha a játékos (1,2,3,4) van nála, nyert.
- Ha a játékos (1,2,3,5) van nála, nyert (2,3,5).
- Ha a játékos (1,2,4,5) van nála, nyert (1,4,5).
- Ha a játékos (1,3,4,5) van nála, nyert (1,4,5).
- Ha a játékos (2,3,4,5) van nála, nyert (2,3,5).
Tehát 4 cédulával már biztosan nyer a játékos. A skatulya-elv itt a lehetséges kimenetelek számának véges volta és a szükséges elemek száma között teremt kapcsolatot.
Mindennapi élet logikai feladványai
A skatulya-elv nagyon jól alkalmazható hétköznapi logikai fejtörők megoldására is, ahol gyakran csak kiszámoljuk a "legrosszabb esetet".
Példa: Kulcsok és zárak
Van 4 kulcsod és 4 zár. Tudod, hogy minden kulcs csak egyetlen zárat nyit. Hány próbálkozás szükséges maximum ahhoz, hogy minden kulcsot a hozzá tartozó zárhoz rendelj?
Ez is a "legrosszabb eset" gondolatmenetre épül. Az első kulccsal megpróbálkozol a zárakkal. A legrosszabb esetben az utolsó zárhoz fog stimmelni. Ez 3 próbálkozás. A második kulccsal megpróbálkozol a maradék 3 zárral. A legrosszabb esetben ez 2 próbálkozás. A harmadik kulccsal megpróbálkozol a maradék 2 zárral, ami 1 próbálkozás. A negyedik kulcs pedig már biztosan a megmaradt zárhoz fog tartozni. Tehát összesen $3+2+1 = 6$ próbálkozás.
Itt a "dobozok" a zárak (4), a "tárgyak" pedig a kulcsok. A skatulya-elv önmagában nem adja meg a 6-ot, de a gondolatmenet, hogy minden próbálkozásnál csökken a lehetőségek száma, arra utal, hogy véges számú lépésben megoldható a probléma. A kulcsok és zárak problémája inkább a permutációkhoz kapcsolódik, ahol minden elemhez egyedi pár hozzárendelés szükséges.
A skatulya-elv kiterjesztése és mélyebb megfogalmazásai
Ahogy a matematikai problémák bonyolultabbá válnak, úgy válik szükségessé a skatulya-elv finomabb árnyalatainak, mélyebb megfogalmazásainak alkalmazása is. Ezek a kiterjesztések lehetővé teszik, hogy még összetettebb jelenségeket is a skatulya-elv keretein belül vizsgáljunk.
Színes dobozok és elemek
Az elv egyik érdekes kiterjesztése, amikor nem csak az elemek és dobozok számát, hanem az elemek (vagy a dobozok) tulajdonságait, például a színeket is figyelembe vesszük.
Példa: Színkeverés
Tegyük fel, hogy van 5 piros és 5 kék golyónk. Ezeket 3 dobozba kell elhelyeznünk. Bizonyítsuk be, hogy lesz olyan doboz, amelyben legalább 2 piros vagy legalább 2 kék golyó van.
Itt a "dobozaink" a 3 doboz ($m=3$). Az "elemek" a 10 golyó. A skatulya-elv alapvető formája azt mondja, hogy lesz olyan doboz, amelyben legalább $\lceil 10/3 \rceil = 4$ golyó lesz. De ez nem mond semmit a színekről.
Azonban, ha azt vizsgáljuk, hogy hogyan oszthatjuk el a piros és kék golyókat úgy, hogy ne legyen olyan doboz, amelyben legalább 2 piros VAGY legalább 2 kék van. Ez azt jelenti, hogy minden dobozban legfeljebb 1 piros és legfeljebb 1 kék golyó lehet. Ez azt jelenti, hogy minden dobozban legfeljebb 2 golyó lehet. Mivel 3 dobozunk van, ez azt jelenti, hogy maximum $3 \times 2 = 6$ golyót tudnánk így elhelyezni. Nekünk azonban 10 golyónk van. Ebből következik, hogy elkerülhetetlenül lesz olyan doboz, amelyben több mint 2 golyó van, és mivel a maximum 1 piros és 1 kék lehetne, ez azt jelenti, hogy lesz olyan doboz, amelyben legalább 2 piros vagy legalább 2 kék golyó lesz.
Ramsey-elmélet és az "egyszínűség" keresése
A Ramsey-elmélet a skatulya-elv egyik mélyebb és bonyolultabb kiterjesztése. A Ramsey-elmélet alapvető tétele kimondja, hogy bármilyen kellően nagy struktúrában bizonyosan megtalálható egy rendezett alstruktúra. Konkrétabban, ha egy struktúrát (például egy gráfot) színezünk véges számú színnel, akkor egy bizonyos méretű rendezett alstruktúra biztosan előfordul egyszínűként.
Példa: Barátság és ellenségek
Ez a legismertebb Ramsey-féle probléma, amely egy 6 fős társaságban játszódik le. Bizonyítsuk be, hogy ebben a 6 fős társaságban biztosan van három ember, akik kölcsönösen barátok, vagy van három ember, akik kölcsönösen ellenségek.
Tekintsünk egy 6 csomópontból álló teljes gráfot, ahol minden csomópont egy embert képvisel. Két csomópont között az élek vagy pirosak (ha a két személy barát), vagy kékek (ha ellenségek). Ez a skatulya-elv és a Ramsey-elmélet egy klasszikus példája.
Vegyünk egy tetszőleges személyt, nevezzük őt "A"-nak. A-nak 5 kapcsolata van a társaság többi tagjával. A skatulya-elv szerint A-nak legalább $\lceil 5/2 \rceil = 3$ barátja vagy legalább 3 ellensége kell, hogy legyen.
Tegyük fel, hogy A-nak van 3 barátja: B, C, D. Vizsgáljuk meg most a B, C, D kapcsolatát.
- Ha B és C barátok, akkor A, B, C hármas barátok (A-val való barátságuk adott, B és C barátságát most vizsgáltuk).
- Ha B és C ellenségek, akkor pedig A, B, C hármasban van két ellenségünk (B és C), de A is ellenséges B-vel és C-vel. Ebben az esetben a barátságok/ellenségek közötti kapcsolatok már adva vannak.
Tehát a lényeg az, hogy a 6 ember között biztosan lesz 3 kölcsönösen barát vagy 3 kölcsönösen ellenség.
A Ramsey-elmélet konkrét tétele, az $R(s, t)$ jelölés, azt jelenti, hogy a legkisebb $N$ szám, amelyre teljesül, hogy bármely $N$ csomópontú, 2 színre (pl. pirosra és kékre) színezett teljes gráf tartalmaz egy egyszínű (mind piros, mind kék) $K_s$ (teljes $s$ csomópontú gráfot) részgráfot. A fenti példában $R(3, 3) = 6$.
"Ahol elrendezünk dolgokat, ott valamilyen formát, bizonyos szabályszerűséget mindig találhatunk."
Véletlen minták és eloszlások
A skatulya-elv segítségével következtethetünk véletlen minták létezésére is, különösen olyan esetekben, ahol a véletlenszerűség mögött valamilyen mélyebb matematikai struktúra húzódik meg.
Példa: Döntő többség
Egy szavazáson 100 ember vesz részt. A szavazásban csak az "igen" és "nem" válaszok lehetségesek. Bizonyítsuk be, hogy biztosan van legalább 51 olyan ember, aki ugyanazt a választ adta.
Ebben az esetben a "dobozaink" a válaszlehetőségek (igen és nem), tehát $m=2$. Az "elemek" a 100 szavazó, tehát $n=100$. Az általánosított skatulya-elv szerint legalább egy válaszlehetőségre legalább $\lceil 100/2 \rceil = \lceil 50 \rceil = 50$ szavazat fog érkezni. Azonban, ha pontosan 50-50 lenne, akkor nem lenne "döntő többség". Ezért kell egy kicsit módosítani a gondolatmenetet.
Ha 100 szavazó van 2 opcióra, és feltételezzük, hogy nincs döntő többség, akkor mindkét opcióra legfeljebb 50 szavazat érkezhet. Ez azt jelenti, hogy az összes szavazat száma legfeljebb $50+50=100$ lehet. Ez nem zárja ki, hogy 50-50 legyen.
Azonban, ha azt akarjuk, hogy biztosan legyen legalább 51, akkor a legrosszabb esetben mindkét opcióra 50 szavazat érkezik. De mi van, ha az egyik opcióra pontosan 50, a másikra pedig 50 szavazat érkezett? Ez nem biztosítja a 51-et.
A skatulya-elv alkalmazása itt a következőképpen működik: a "dobozaink" az "igen" és a "nem" szavazatok. Ha $n$ szavazat van, és $m=2$ doboz, akkor az általánosított skatulya-elv szerint legalább egy dobozban $\lceil n/m \rceil$ szavazat lesz. Ha $n=100$, akkor $\lceil 100/2 \rceil = 50$. Ez azt jelenti, hogy legalább 50 szavazat lesz az egyik opcióra. Ahhoz, hogy biztosan 51 legyen, egy plusz szavazatra van szükségünk.
Ha 51 ember szavaz "igen"-re, akkor a maradék 49 szavaz "nem"-re. Ez rendben van.
Ha 50 ember szavaz "igen"-re, és 50 ember szavaz "nem"-re, akkor sincs döntő többség.
Azonban, ha $n=101$ szavazó lenne, akkor $\lceil 101/2 \rceil = 51$ lenne.
A kérdésben 100 szavazó van. Ha feltételezzük, hogy nincs 51 azonos válasz, akkor mindkét válaszra legfeljebb 50 szavazat érkezhet. Ez pedig $50+50=100$ szavazatot jelent. Tehát elképzelhető az 50-50 megoszlás. A feladat megfogalmazása itt kulcsfontosságú. Ha "legalább 51" a cél, akkor 100 szavazó esetén nem garantálható. Ha viszont a kérdés az, hogy "biztosan van olyan válasz, amire legalább annyian szavaztak, mint a másikra, plusz egy", akkor igen.
A klasszikus megfogalmazás szerint 100 szavazó esetén a legrosszabb esetben 50-50 arány lehetséges. Ahhoz, hogy biztosan legyen 51, $101$ szavazatra lenne szükség.
"A számok törvényszerűségei gyakran meglepő logikai következtetésekhez vezetnek, amelyek a valóságban is megjelennek."
Táblázatok a skatulya-elv szemléltetésére
Az alábbi táblázatok segítenek vizuálisan megjeleníteni a skatulya-elv működését különböző forgatókönyvekben.
Táblázat 1: Az alapvető skatulya-elv működése
Ez a táblázat az alapvető skatulya-elv ($n > m \implies$ legalább egy dobozban $\ge 2$ elem) szemléltetésére szolgál.
| Dobozok száma ($m$) | Elemek száma ($n$) | Feltétel $n > m$? | Következtetés: Legalább egy dobozban $\ge 2$ elem? | Példa |
|---|---|---|---|---|
| 3 | 4 | Igen | Igen | 4 vendég 3 szobában. |
| 5 | 7 | Igen | Igen | 7 labda 5 zsákban. |
| 10 | 10 | Nem | Nem feltétlenül (lehet 1 minden dobozban) | 10 elem 10 dobozban. |
| 2 | 1 | Nem | Nem | 1 alma 2 kosárban. |
Megjegyzés: A táblázat azt mutatja, hogy a skatulya-elv csak akkor garantálja a több elemet tartalmazó dobozt, ha az elemek száma meghaladja a dobozok számát.
Táblázat 2: Az általánosított skatulya-elv működése
Ez a táblázat az általánosított skatulya-elv ($n$ elem, $m$ doboz $\implies$ legalább egy dobozban $\ge \lceil n/m \rceil$ elem) szemléltetésére szolgál.
| Dobozok száma ($m$) | Elemek száma ($n$) | $\lceil n/m \rceil$ becslés | Következtetés: Legalább egy dobozban $\ge \lceil n/m \rceil$ elem? | Példa (a becslést konkrét példával szemléltetve) |
|---|---|---|---|---|
| 3 | 10 | $\lceil 10/3 \rceil = 4$ | Igen, legalább egy dobozban 4 elem lesz. | 10 golyó 3 dobozban. |
| 5 | 17 | $\lceil 17/5 \rceil = 4$ | Igen, legalább egy dobozban 4 elem lesz. | 17 pont 5 területen. |
| 2 | 5 | $\lceil 5/2 \rceil = 3$ | Igen, legalább egy dobozban 3 elem lesz. | 5 zokni 2 színnel (piros, kék). |
| 4 | 16 | $\lceil 16/4 \rceil = 4$ | Igen, legalább egy dobozban 4 elem lesz. | 16 diák 4 csapatban. |
Megjegyzés: Az általánosított skatulya-elv pontosabb becslést ad, mint az alapvető forma, és sokkal szélesebb körben alkalmazható bonyolultabb problémák elemzésére.
Gyakran ismételt kérdések a skatulya-elv kapcsán
H6: Mi a skatulya-elv legegyszerűbb megfogalmazása?
A legegyszerűbb megfogalmazás szerint, ha több dolgot próbálunk elhelyezni kevesebb dobozba, akkor legalább egy dobozba kettőnél több dolog fog kerülni. Pontosabban, ha $n$ dolgot helyezünk el $m$ dobozban, és $n > m$, akkor lesz legalább egy doboz, amelyben kettő vagy több dolog található.
H6: Miért fontos a skatulya-elv a matematika más területein?
A skatulya-elv alapvető fontosságú, mert megmutatja, hogyan lehet bizonyos tulajdonságok létezését igazolni anélkül, hogy a konkrét eseteket fel kellene sorolnunk. Ez teszi lehetővé hatékony bizonyítások felépítését a kombinatorikában, gráfelméletben, számítástechnikában és sok más területen.
H6: Milyen különbség van az alapvető és az általánosított skatulya-elv között?
Az alapvető skatulya-elv csak azt garantálja, hogy ha $n > m$, akkor lesz olyan doboz, amiben legalább két elem van. Az általánosított forma ennél pontosabb: azt állítja, hogy legalább egy dobozban legalább $\lceil n/m \rceil$ elem lesz. Ez utóbbi sokkal több információt hordoz és szélesebb körben alkalmazható.
H6: Miben különbözik a skatulya-elv a "pigeonhole principle" angol kifejezéstől?
A "skatulya-elv" és az "angol kifejezés", a "pigeonhole principle", ugyanazt a matematikai tételt jelöli. A skatulya-elv a magyar elnevezés, a "pigeonhole principle" pedig az angol. A lényegük és a matematikai tartalmuk azonos. A "galambdúc elv" is egy gyakran használt szinonima.
H6: Milyen hétköznapi példák illusztrálják a skatulya-elvét?
Számos hétköznapi példa létezik:
- Ha 3 vendég érkezik 2 szobába, akkor az egyik szobában legalább 2 vendég lesz.
- Egy rendezvényen, ahol több mint 366 ember van, legalább két embernek azonos a születésnapja (szökőévet figyelmen kívül hagyva).
- Egy fiókban, ahol 5 piros és 5 kék zokni van, legalább 3 zoknit kell kivennünk ahhoz, hogy biztosan legyen egy párunk.
H6: Alkalmazható-e a skatulya-elv a véletlen jelenségek vizsgálatára?
Igen, a skatulya-elv segíthet a véletlen jelenségek mögött rejlő bizonyos törvényszerűségek felismerésében, különösen akkor, ha a véletlen mintázatokat diszkrét kategóriákba sorolhatjuk. Például, bizonyos szerencsejátékok vagy szavazások elemzésekor.
