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. A tavaly szeptemberi számban kitűzött P. 306. probléma a következőképpen szólt: ,,Artúr király testőrei lovagi tornát vívtak. A torna végén kiderült, hogy a király bármely testőrhöz tud találni egy -ediket, aki mindegyiküket legyőzte. Bizonyítsuk be, hogy legalább résztvevő volt.'' A feladatra 5 tanuló küldött helyes megoldást: Erdélyi Tamás, Ligeti Rudolf, Lipusz Csaba, Nagy Gábor és Varga Lívia. Erdélyi Tamás dolgozatának végén megjegyzi: ,,Érdekes kérdés, hogy egy főből álló társaságra megadható-e olyan konstrukció, amelyre a feladat feltételei teljesülnek.'' Ennek az írásnak az a célja, hogy erről a kérdéskörről mindazt elmondja, amit ma a matematikusok tudnak. Kezdjük egy definícióval. Jelölje azt a legkisebb, -nél nagyobb egész számot, amelyre igaz a következő állítás. Ha a királynak pontosan testőre van, akkor a lovagi tornának lehetséges olyan végeredménye, hogy bármely testőrhöz található olyan -edik, aki mind az -et legyőzte. Könnyen belátható, hogy , az F. 2159. feladat megoldása (megjelent a Kömal 58. kötet, 1. szám 9. oldalán) szerint , továbbá a P. 306. probléma azt állítja, hogy . Elsőként Erdős Pál bizonyította, hogy 1965-ben azután két ausztráliai matematikus, E. és G. Szekeres megmutatták, hogy a valamivel erősebb egyenlőtlenség is igaz. Elsőként (2)-t bizonyítjuk, ebből (1) első egyenlőtlensége már következik. Ehhez egy újabb definícióra van szükségünk. Jelöljük -mel azt a legkisebb, -nél nagyobb egész számot, amelyre igaz a következő állítás. Ha Artúr királynak pontosan testőre van, akkor a lovagi tornának lehetséges olyan kimenetele, hogy bármely testőrt legalább másik testőr legyőzött. Világos, hogy . Legyen és tegyük fel, hogy a testőr közötti lovagi torna végeredménye megfelel a fenti feltételnek. Nem lehetséges, hogy minden testőr több mint testőrtől kapjon ki, mert ekkor a vereségek száma több volna, mint , noha összesen legfeljebb mérkőzés volt. Legyen tehát olyan testőr, aki legfeljebb alkalommal kapott ki. Ha most , akkor a feltétel szerint -t legalább testőr győzte le, azaz , ahonnan Ha , akkor állítjuk, hogy az -t legyőző testőrök száma legalább , azaz Ehhez elegendő megmutatnunk, hogy az -t legyőző testőrök teljesítik a definíciójában szereplő állítást.
1. ábra
Először is legalább testőr győzte le -t. Ugyanis ha csak a , , , testőrök nyertek volna ellen, akkor az , , , testőröket tetszőlegesen kiegészítve testőrré, volna olyan , aki mindnyájukat legyőzte, azaz legyőzte -t is és legyőzte , , , -t is (1. ábra). Ez a nem egyezhet meg egyik -vel sem; és legyőzte -t, ami ellentmond annak, hogy -t csak , , , győzte le. Másodszor azt kell ellenőriznünk, hogy ha a , , , testőrök mind legyőzték -t, akkor van testőr a legyőzők között, akik , , mindegyikét legyőzték. Ám ezt éppen az a feltételünk biztosítja, ami szerint az , , , , (összesen fő) testőrhöz található olyan testőr, akik ezt az -et legyőzték. Ezek persze legyőzték -t, és legyőzték , , -et is. A (3) és (4) egyenlőtlenségek alapján teljes indukcióval bizonyítjuk, hogy -re az állítás (3)-mal ekvivalens. Ha és (5)-öt már -re tudjuk, akkor (4) szerint | | amivel a teljes indukciós bizonyításunk készen van.
2. ábra Az (5) egyenlőtlenségben -et téve megkapjuk (1) első egyenlőtlenségét. Ahhoz, hogy (2)-t megkapjuk, még a következőket kell észrevennünk. Ha bármely testőrhöz van olyan -edik, aki mind az -et legyőzte, akkor bármely testőrt legalább győzött le. Tegyük fel ugyanis, hogy az , , , testőröket csak a , , , testőrök győzték le. A feltétel szerint létezik olyan testőr, aki a , , , mindegyikét legyőzte. Ez nem lehet azonos semelyik -vel sem, hiszen -t mindegyik legyőzte. Kell lenni olyan testőrnek is, aki az , , , , és testőröket legyőzte (2. ábra). nem lehet azonos egyetlen -vel sem, mivel legyőzte -t, viszont mindegyik kikapott -től. Másreszt -nek meg kell egyeznie valamelyik -vel, hiszen , , , mindegyikét csak a , , testőrök győzték le. Ellentmondásra jutottunk, ami állításunkat igazolja. Hasonlóan juthatunk ellentmondásra abból a feltevésből, hogy az -ket -nél kevesebb testőr győzte le. Így tehát , ahogyan az (2)-ben szerepel. Ahhoz, hogy az egyenlőtlenséget igazoljuk, semmi mást nem kell tennünk, mint a testőr közötti küzdelem eredményét úgy megválasztanunk, hogy bármely testőrt valaki legyőzzön. Sőt ezeket nem kell konkrétan megadnunk, elegendő bizonyítani, hogy a küzdelem eredménye megválasztható úgy, hogy bármely testőrt valaki legyőzzön. A helyzet hasonló ahhoz, amikor azt akarjuk bizonyítani, hogy az , , sorozat első 1001 tagja között van kettő olyan, melyek ugyanarra a számjegyre végződnek. Itt is elegendő megkeresnünk ezt a kettőt, de ehelyett igazolhatjuk azt is, hogy ilyen pár mindig kiválasztható anélkül, hogy tudnánk, mik is lesznek a párnak az elemei. Esetünkben ez a következőképpen fog történni. Megbecsüljük annak a valószínűségét, hogy a lovagi torna végeredménye ,,jó'' lesz. Ha ez a valószínűség pozitív, akkor készen vagyunk, a lehetetlen esemény valószínűsége ugyanis . Tegyük fel tehát, hogy annak valószínűsége, hogy az -edik testőr legyőzi a -ediket, -től és -től függetlenül . Tegyük fel továbbá, hogy a küzdelmek kimenetele egymástól független. Legyen annak a valószínűsége, hogy tetszőleges testőrhöz található olyan -edik, aki mind az -et legyőzte. Ha most a küzdelmek minden lehetséges kimenetele mellett található testőr, akiket senki sem győzött le, akkor a fenti esemény a lehetetlen esemény, és így . Így tehát megmutatjuk, hogy vagy ami ugyanaz, hogy , akkor a testőrök közötti küzdelmek eredménye megválasztható úgy, hogy bármely testőrhöz lehessen találni olyan -ediket, aki mindegyiküket legyőzte. Legyenek , , , tetszőleges testőrök. Annak valószínűsége, hogy az testőr mindegyik -t legyőzi, , hiszen mindet valószínűséggel győzi le, és a küzdelmek eredménye egymástól független. Így annak valószínűsége, hogy nem győzi le mindet, , és így annak valószínűsége, hogy a , , , -től különböző testőr egyike sem győzi le , , , mindegyikét, hiszen ezek még mindig független események. Így akárhogyan választunk ki testőrt, annak a valószínűsége, hogy senki sem győzi le mind az -et. A testőr közül testőrt-féleképpen választhatunk ki. Így annak a valószínűsége, hogy van olyan -es, akit senki sem győz le, legfeljebb , azaz Itt már nem feltétlenül áll fenn egyenlőség, ugyanis az összegzett események már nem zárják ki egymást. Mivel az egyenlőtlenség igazolásához elegendő megmutatni, hogy ha . Mindkét oldalból -edik gyököt vonva és értékét behelyettesítve, a bizonyítandó egyenlőtlenség | | (6) | Ennek igazolásához szükségünk lesz a következő két egyenlőtlenségre: | | (7) | Az Az első az ismert egyenlőtlenség reciproka, a másodikat -ra vonatkozó teljes indukcióval könnyen igazolhatjuk. (7) első egyenlőtlenségét -re alkalmazva | | (7) második egyenlőtlensége szerint. Ezzel (6)-t és ezzel (1) második egyenlőtlenségét is igazoltuk. Az függvény értékét tehát két korlát közé sikerült szorítanunk. Az alábbi táblázatban -ra tüntettük fel a korlátok, illetve értékét. Az, hogy , triviális, az egyenlőséget az F. 2159. feladat megoldásában bizonyítottuk. pontos értékét E. és G. Szekeres számították ki.
Megadták 19 testőr közötti 171 küzdelem végeredményét úgy, hogy bármely három testőrhöz legyen egy negyedik, aki mindhármukat legyőzte: az i-edik testőr pontosan akkor győzze le a j-ediket, ha az i+19-j kifejezés 19-cel osztva az 1, 4, 5, 6, 7, 9, 11, 16 vagy 17 maradékot adja. Az olvasóra bízzuk annak ellenőrzését, hogy ez valóban jó. Az n=4 értéktől fölfelé f(n) értéke nem ismeretes, sőt még azt sem tudjuk, hogy az f(n)n⋅2n sorozat korlátos-e. Megjegyezzük, hogy a konstrukcióból f(4)-re adódó legjobb felső korlát 311 (a legkisebb olyan k, amelyre (k4)q<1 fennáll), ennél jobb felső korlátot nem ismerünk. Sőt, bár tudjuk, hogy 311 testőr közötti küzdelmek eredményét meg lehet választani úgy, hogy bármely négy testőrt valaki legyőzzön, eddig még senki nem adott meg ilyet. Még annak eldöntése is, hogy f(4) egyenlő-e 47-tel, szinte reménytelennek látszik. A 47 testőr közötti 1081 mérkőzésnek 21081≈10300 különböző végeredménye lehet, és ha mindről átlag 0,1 másodperc alatt el tudjuk dönteni, hogy jó-e vagy sem (ami egyenként (474)=178365 vizsgálatot jelent), akkor az utolsó esetre is több mint 10290 év múlva kerülne sor. Csak győzzük kivárni!
|