Feladat: 1976. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Magyar Zoltán 
Füzet: 1977/február, 54 - 56. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Kombinatorikai leszámolási problémák, Kombinációk, Binomiális együtthatók, Skatulyaelv, Számsorok, Projektív geometria, Halmazok számossága, Logaritmusos függvények, Kombinatorikus geometria síkban, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1977/február: 1976. évi Kürschák matematikaverseny 2. feladata

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.

Megoldás. Feltesszük, hogy a különféle lottószelvények különféleképpen vannak kitöltve. Vegyünk egy tetszőleges L1 lottószelvényt. A többi 55-1 db lottószelvény mindegyike tartalmazza az L1-en levő 5 szám valamelyikét. Az L1-en levő 5 szám közül tehát legalább az egyiket a többi szelvények közül legalább 54 tartalmazza. Válasszunk ki egy ilyen számot, jelöljük ezt a-val. a-t tehát (L1-et is beleszámítva) több, mint 54 szelvény tartalmazza. Ha minden szelvény tartalmazza a-t, akkor az állítás helyes. Ha nem, legyen L2 egy olyan szelvény, amely nem tartalmazza a-t. Az a-t tartalmazó, több mint 54 szelvény mindegyike tartalmaz legalább egy L2-n levő számot. Tehát az L2-n levő 5 szám közül legalább az egyiket (mondjuk b-t) az a-t tartalmazó szelvények közül több, mint 53 kell, hogy tartalmazza. Ha minden szelvény tartalmazza a és b közül legalább az egyiket, készen vagyunk. Ha nem, legyen L3 egy sem a-t, sem b-t nem tartalmazó szelvény. A fenti gondolatmenetet megismételve találunk L3-on egy olyan c számot, hogy több mint 52 szelvény van, amelyik a, b, c mindegyikét tartalmazza. Ismét készen vagyunk, vagy van olyan L4 szelvény, ami a, b, c egyikét sem tartalmazza, és ekkor ezen találunk olyan d számot, hogy több, mint 5 szelvény tartalmazza a, b, c, d mindegyikét. Ha lenne olyan L5 szelvény, amelyik a, b, c, d egyikét sem tartalmazná, akkor az L5-ön levő öt szám egyike, mondjuk e, olyan lenne, hogy több, mint 1 szelvény lenne, amelyik a, b, c, d, e mindegyikét tartalmazná. Mivel ez feltevésünk szerint lehetetlen, bebizonyítottuk, hogy az a, b, c, d számnégyes rendelkezik a kívánt tulajdonsággal.
Megjegyzések. 1. Arra a feltevésre, hogy különböző szelvények különbözőképpen vannak kitöltve, valóban szükség van. Könnyen konstruálhatunk olyan példát, ami ezt mutatja. Válasszunk ki pl. az első 9 természetes szám közül minden lehetséges módon 5-öt. Ez (95)=126-féleképpen lehetséges.Ezután az 55 szelvény mindegyikén ezen ötösök valamelyikét jelöljük ki, mégpedig a 126 db ötös mindegyike legalább egy szelvényen legyen kijelölve. Könnyen látható, hogy ekkor bármely két szelvény tartalmaz közös számot, mégsem találhatunk a mondott tulajdonsággal rendelkező számnégyest.
2. Ha veszünk 55 db különbözőképpen kitöltött lottószelvényt, úgy hogy bármely kettőnek van közös eleme, akkor világos, hogy van 5 olyan szám, hogy minden lottószelvény tartalmazza ezen 5 szám közül legalább az egyiket. Pl. akármelyik lottószelvényen megjelölt 5 szám megfelel. Nehezebb (és éppen ez volt a feladat állítása), azt bizonyítani, hogy már 4 szám is található a kívánt módon.
Nem javítható-e a 4 tovább 3-ra, azaz nem igaz-e, hogy mindig van 3 olyan szám, hogy mindegyik lottószelvény tartalmazza e 3 szám valamelyikét? Megmutatjuk, hogy nem.
Rendezzük el az 1-től 10-ig terjedő számokat az alábbi séma szerint:

 
12345678910

 
Válasszuk ki ezek után az összes olyan számnégyest, amit úgy kapunk hogy valamelyik szintről az összes számot vesszük, minden alatta levő szintről 1‐1 számot veszünk, a fölötte levő szintekről pedig nem veszünk számokat.
Ilyen négyesek pl.:
  1258  1267  23410  4568  78910

Összesen
4!1!+4!2!+4!3!+4!4!=4⋅3⋅2+4⋅3+4+1=41
ilyen számnégyes van. Könnyen látszik, hogy bármely kettőnek van közös eleme, és nem található 3 olyan szám, hogy mind a 41 számnégyes tartalmazná ezen 3 szám valamelyikét.
Vegyük ezután hozzá mindegyik négyeshez a 11-től 90-ig terjedő számok mindegyikét. Így
41⋅80=3280
számötöst kapunk úgy, hogy bármely kettőnek van közös eleme és nincs 3 olyan szám, hogy mindegyik számötös tartalmazná e 3 szám valamelyikét. E számötösök száma még több is, mint a kívánt 3125=55. Ha azt akarjuk, hogy számuk pontosan 3125 legyen, hagyjunk el 155 db-ot közülük, csak arra vigyázva, hogy az elhagyás után is még mind a 41 számnégyest legalább egy megmaradt számötös tartalmazza. Nem nehéz belátni, hogy ez a konstrukció rendelkezik a kívánt tulajdonsággal.
3. Mint látható, a feladat bizonyításában nem használtuk ki, hogy éppen 90 szám közül választhatók az ötösök. Valójában azt bizonyítottuk, hogy akárhogy választunk (bármely elemekből képzett) 55 db 5-elemű halmazt úgy, hogy bármely két halmaznak van közös eleme, akkor mindig található 4 olyan elem, hogy mind az 55 db halmaz mindegyike tartalmazza e 4 elem közül legalább az egyiket.
Általánosabban a következő igaz: ha van nn db n elemű halmaz (n≥2) úgy, hogy bármely kettőnek van közös eleme, akkor található (n-1) db elem úgy, hogy bármely halmaz tartalmazza ezen (n-1) elem közül legalább az egyiket. Ennek bizonyítása teljesen megegyezik a fent közölt bizonyítással, csak éppen az ott szereplő gondolatmenetet nem 5, hanem n lépésen keresztül kell megismételni.
4. Az eddig tárgyalt problémakör matematikai tartalma még általánosabban a következő: Ha vannak n elemű halmazok úgy, hogy bármely kettőnek van közös eleme, továbbá tudjuk, hogy nem található n-nél kevesebb elem úgy, hogy mindegyik halmaz tartalmazza ezen elemek valamelyikét, akkor ezek az n elemű halmazok nem lehetnek sem túl sokan, sem túl kevesen.
Mennyi itt a ,,túl sok''? A 3. megjegyzésben láttuk, hogy nn-t már biztosan nem érheti el a számuk. Másrészt a 2. megjegyzésben leírt konstrukciót n szintből álló számháromszögre általánosítva látjuk, hogy
n!1!+n!2!+...+n!n!=[(e-1)⋅n!]
n elemű halmaz még található a fent leírt módon.
(Itt e=2,71828... és [x] jelöli a legnagyobb olyan egész számot, amelyik nem nagyobb x-nél.)
Nagy n-re [(e-1)⋅n!] sokkal kisebb, mint nn. Hogy [(e-1)⋅n!] és nn között hol kezdődik a ,,túl sok'', nem tudjuk.
Mennyi a ,,túl kevés''? Nem nehéz belátni, hogy 2(n-1) már túl kevés. Ha ugyanis legfeljebb ennyi halmazunk van, akkor kettenként választhatunk hozzájuk egy-egy elemet, ami annak a kettőnek mindegyikében benne van, (hiszen bármely két halmaznak van közös eleme) és így legfeljebb (n-1) elemre lesz szükségünk.
Véges projektív síkok* segítségével tudunk olyan halmazszámot is megadni, amennyi már nem ,,túl kevés''. Vegyünk egy olyan véges projektív síkot, amelyen minden egyenesnek n pontja van. Ilyen mindig található, ha n-1 prímhatvány. Az egyenesek lesznek a szóban forgó n-elemű halmazok, számuk n2-n+1. Bármely kettő metszi egymást, és nem nehéz belátni, hogy nem adható meg úgy (n-1) pont, hogy minden egyenes tartalmazza legalább az egyiket közülük. Finomabb módszerek alkalmazásával Erdős Pál és Lovász László kimutatta, hogy a ,,túl kevés'' valahol 83n-3 és c⋅n3/2⋅logn között ér véget, ahol c alkalmas konstans. Hogy pontosabban hol van ez a határ, az ez idő szerint szintén nem ismeretes.
*A véges projektív sík definíciója és elemi tulajdonságai megtalálhatók pl. a K.M.L. 51/2 (1975. október) számában az 53. oldalon kezdődő cikkben, vagy az alábbi szakköri füzetben:
Lovász‐Pelikán‐Vesztergombi: Kombinatorika. 2. kiadás (Tankönyvkiadó, Budapest, 1972. 128. old.)