A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. 1. feladat. Legyen és legyenek olyan nemnegatív valós számok, amelyek összege legfeljebb . Bizonyítandó, hogy létezik olyan egész szám és léteznek olyan egészek, amelyekre teljesül, hogy
I. megoldás. Osszuk az sorozatot blokkokra: a nulladik blokk álljon -ből, az első legyen , a másodikhoz tartozzon . Általában az -dik blokk az elemtől tartalmazza a sorozat elemeit az elemmel bezárólag. (Ha , akkor a blokk értelemszerűen csak -ig tartalmazza a sorozat elemeit.) Tegyük fel, hogy blokkból áll az sorozat, vagyis az utolsó blokk a -adik. Legyen -ra az -edik blokk legkisebb eleme, és legyen . A blokkok és az -k megválasztása miatt , ezért | | ahol az utolsó egyenlőtlenség definíciójából és abból következik, hogy az -edik blokk éppen db elemet tartalmaz. Azt kaptuk tehát, hogy az szorzat legfeljebb -szerese az -edik blokkban álló elemek összegének, tehát e szorzatok összege is legfeljebb -szerese az első blokk összegének: | |
Több versenyző is próbálkozott a feladatban szereplő összeg lehetséges értékeinek átlagolásával. Ha ugyanis ez az átlag kisebb lenne -nél, az garantálná, hogy létezik a feltételt teljesítő sorozat. Másképpen fogalmazva: állítsuk elő az sorozatot véletlenszerűen úgy, hogy az indexek mindegyikét (egymástól függetlenül) valószínűséggel választjuk ki (a -t és az -et mindenképpen ki kell választanunk), és vizsgáljuk meg az így előállított véletlen összeg várható értékét. Ha a várható érték -nél kisebb, akkor ez biztosítja, hogy az állítás igaz. Ez az ötlet ‐ ebben a formában ‐ nem vezethet eredményre, mert várható értéke tetszőlegesen nagy lehet. Az egyes indexek kiválasztási valószínűségének szerencsésebb megválasztásával azonban a feladat megoldható.
II. megoldás. Készítsük el az sorozatot véletlenszerűen úgy, hogy az indexet tetszőleges esetén valószínűséggel választjuk ki, és legyen az egyes indexek kiválasztása egymástól független. A valószínűségeket a következőképpen válasszuk meg: | | Megjegyezzük, hogy az és az indexeket biztosan ki kell választanunk, ennek megfelelően . Vizsgáljuk meg, hogy valamely esetén az kifejezés milyen valószínűséggel szerepel az (1) bal oldalán álló összeg tagjai között. Ennek szükséges és elégséges feltétele, hogy az és indexeket kiválasszuk, a közbülső indexek közül viszont egyet sem. Az tag előfordulásának valószínűsége tehát | | a teljes összeg várható értéke pedig
Ha , akkor
Ha pedig , akkor
Ezeket a becsléseket beírva (2)-be,
és | |
Mivel a várható érték a lehetséges összegeknek a ‐ valószínűségük szerint ‐ súlyozott átlaga, a lehetséges összegek között biztosan létezik -nél kisebb.
2. feladat. és teniszeznek. Az a játékos győz, aki elsőként nyer meg legalább négy labdamenetet úgy, hogy ellenfelénél legalább kettővel több labdamenetet nyert. Tudjuk, hogy az játékos minden labdamenetet, a korábbiaktól függetlenül, valószínűséggel nyer meg. Bizonyítsuk be, hogy az játékos győzelmének valószínűsége legfeljebb .
I. megoldás. Legyen mindazon játékok halmaza, amelyekben az játékos nyer, míg a halmaz tartalmazza a által megnyert játékokat. Az és halmazok között kölcsönösen egyértelmű megfeleltetést hozunk létre, ha egy által megnyert játéknak az a játék lesz a párja, amiben minden labdamenetet épp a másik játékos nyer meg, mint ahogyan az -ben történt. Azt mutatjuk meg, hogy tetszőleges játék esetén Ha ezt megtesszük, akkor
azaz bebizonyítottuk a feladat állítását. Ha a G játékban A l-szer és B k-szor nyert labdamenetet, akkor abból, hogy a B játékos q=1-p valószínűséggel nyer meg egy labdamenetet kapjuk, hogy P(G)=pl⋅qk, illetve P(G')=pk⋅ql, továbbá a játék definíciója miatt m:=l-k≥2. Azt kell tehát igazolni, hogy pl⋅qk≤2p2(pl⋅qk+pk⋅ql), ami azzal ekvivalens, hogy pm≤2p2(pm+qm). Világos, hogy (p-q)2≥0, ahonnan 2p2+2q2≥p2+2pq+q2=(p+q)2=1 adódik. Innen | pm≤(2p2+2q2)pm=2p2pm+2q2pm≤2p2pm+2qmp2=2p2(pm+qm), | ahol az utóbbi egyenlőtlenség m≥2 és q≥p miatt igaz. Nekünk pedig éppen ezt kellett bizonyítanunk. □
Megjegyzés. Könnyen látható, hogy ha p≤12, akkor 2p2≤p, és csakis akkor van egyenlőség, ha p=12 vagy p=0. Az A játékosnak tehát rosszabb az esélye a győzelemre, mint egyetlen labdamenet megnyerésére. Az I. megoldásban található párbaállítási ötlet egyedül Paulin Roland dolgozatában fordult elő. A feladatot szintén megoldó további versenyzők mindegyike az ilyen feladatokra szokványosabb számolásos megoldással ért célt. Az alábbiakban erre mutatunk egy példát.
II. megoldás. Vegyük észre, hogy ha hat labdamenet után még nincs győztes, akkor mindkét játékos éppen három labdamenetet nyert. Világos, hogy annak a valószínűsége, hogy az A játékos k egymás utáni játszmából l-t nyer meg (kl)plqk-l, ahol q:=1-p a B játékos esélye egy labdamenet megnyerésére. Figyeljük meg, hogy ha a játék legfeljebb öt labdamenet után véget ér, akkor a végeredmény akkor sem változik meg, ha a játékosok végigjátsszák az első hat labdamenetet, hisz a vesztes még ekkor is csak legfeljebb két labdamenetet nyerhet. Az A játékos győzelmének valószínűsége tehát | P(A nyer)=p6+6p5q+15p4q2+20p3q3r, | ahol az első tag a 6:0-ás, a második az 5:1-es, a harmadik a 4:2-es győzelem valószínűsége, r pedig annak a valószínűsége, hogy 3:3-as állás után az A játékos győz. A 3:3-as állásnál vagy valamelyik játékos megnyeri a soron következő két labdamenetet és győz, vagy mindkét játékos egy-egy labdamenetet nyer, aminek a valószínűsége 2pq. Az így kialakult helyzetben azonban mindkét játékos győzelmi esélye azonos a 3:3-as helyzetbeli esélyével. Tehát r=p2+2pqr (hiszen A p2 eséllyel nyeri meg a soron következő két labdamenetet), azaz r=p21-2pq. Azt kaptuk tehát, hogy | P(A nyer)=p6+6p5q+15p4q2+20p3q3p21-2pq. | Nyilván pq=p(1-p)=14-(p-12)2≤14, ahonnan 11-2pq≤2 adódik. Ezt felhasználva
P(A nyer)≤p6+64p4+1516p2+4064p2=p2(p4+32p2+2516)==p2((p2+34)2+1)≤p2((14+34)2+1)=2p2.
Egyenlőség pedig (p≥0 miatt) pontosan akkor áll, ha p2=0 vagy ha p2=14, azaz, ha p=0 vagy p=12. □
3. feladat. 2×1-es dominókból tornyot építünk a következő módon. Először elrendezünk 55 dominót úgy, hogy egy 10×11-es téglalapot fedjenek le; ez lesz a torony első szintje. Erre azután további, 55 dominót tartalmazó szinteket építünk, ügyelve arra, hogy minden egyes szint pontosan illeszkedjék az előzőre. Az így kapott építményt akkor nevezzük stabilnak, ha a 10×11-es téglalap minden rácsponttól különböző, belső pontja felett van dominónak belső pontja. Hány szintből áll a legalacsonyabb stabil torony?
Megoldás. Nevezzük a torony által lefedett téglalap 10 hosszú oldalát vízszintesnek, a 11 hosszút pedig függőlegesnek. A toronynak a feladatban leírt tulajdonsága azt jelenti, hogy az említett 10×11 méretű téglalapot (1×1)-es mezőkre osztva bármely két, élben szomszédos mezőhöz van a toronyban olyan dominó, amelyik pontosan e két mező felett található. A függőleges élek mentén szomszédos mezőpárokat nevezzük vízszintes pároknak ‐ 99 ilyen pár van ‐ a vízszintes élek mentén szomszédosakat pedig függőleges pároknak ‐ ezekből 100 darab van. Először igazoljuk, hogy létezik 5-szintes stabil torony. Világos, hogy két szint elegendő arra, hogy mind a 100 függőleges mezőpárt fedje dominó. A 99 vízszintes párnak a feladatban előírt ,,lefedéséhez'' három újabb szintet használunk fel. A téglalap vízszintes oldala páros, így kiparkettázható olyan dominókkal, amelyek kizárólag vízszintes párokat fednek le. Legyen ez a harmadik szint. Hagyjuk el a téglalap jobb és bal szélső oszlopát, valamint a legfelső sorát! A kapott 8×10-es tábla kiparkettázható csupa vízszintes dominóval. Ez a parkettázás kiterjeszthető az elhagyott szélső mezőkre is, legyen ez a negyedik szint. Mostanra a legfelső sor négy ,,belső'' párját kivéve minden vízszintes párról gondoskodtunk. Egy ötödik szinten ezek is lefedhetők, például az előzőhöz hasonló konstrukcióval, ha most a két szélső oszlopon kívül a legalsó sort hagyjuk el.
Állítjuk, hogy ha egy torony legfeljebb 4-szintes, akkor nem stabil. Ebből következik, hogy a legalacsonyabb stabil torony éppen 5-szintes. Indirekt módon bizonyítunk. Először is jegyezzük meg, hogy ha egy ilyen torony stabil, akkor legalább 4 szintje van. Valóban: a 10×11-es téglalap minden egyes, nem a szélen fekvő mezejének 4 szomszédja van, és az ezekhez tartozó dominók más-más szinten helyezkednek el. Ha tehát két szomszédos mező valamelyike nem szélső, akkor pontosan egy dominó fedi e két mezőt. Ha egy m mezőnek 3 élszomszédja van (azaz m a téglalap szélén van, de nem sarokmező), akkor van egy olyan m' élszomszédja, hogy m és m' felett pontosan két dominó van a toronyban, ráadásul, az előbb elmondottak szerint m' szintén szélső mező. Az m mező további 2 élszomszédját pedig egy-egy m-et is fedő dominó fedi. Minthogy tetszőleges élszomszédos mezők között van olyan, amelynek 3 vagy 4 élszomszédja van, a fentiek szerint nincs olyan szomszédos mezőpár, amelyet a toronynak három dominója is fed. Vizsgáljuk most már azokat a mezőpárokat, amelyeket a toronynak pontosan két dominója fed le! A fentiek szerint ezek a párok diszjunktak, a tábla szélén helyezkedhetnek el, továbbá az egyes sarokmezők mindkét szomszédjukkal ilyen kétszeresen fedett párt alkotnak. A bal alsó sarokmezőben végződő oszlop 11 mezején végighaladva azt találjuk, hogy vagy az oszlopban van olyan mező, amely nem szerepel kétszeresen fedett párban (ez lehetetlen), vagy az oszlop másik végében lévő sarokmező nincs duplán fedve az oszlopszomszédjával, amit szintén kizártunk. Ezzel a bizonyítást befejeztük, négyszintes stabil torony valóban nem létezik. □ |