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. I. megoldás. A halmaz elemei legyenek , a kiválasztott részhalmazok pedig . Ha valamelyik csak egyetlen -ben szerepel, akkor a feltételek szerint abban a részhalmazban az összes elemnek szerepelnie kell, további részhalmaz pedig nem lehet kiválasztva, vagyis ekkor . Tegyük fel tehát, hogy minden legalább két -ben szerepel.
1. ábra Minden elemhez rendeljünk hozzá egy tagú számsorozatot, amelynek -edik tagja 1, ha , egyébként pedig 0. Ha és két -tagú valós számsorozat, pedig tetszőleges valós szám, akkor legyen | | Ezek a műveletek a térbeli vektorok összeadásának, számmal való szorzásának és skaláris szorzatának természetes általánosításai. Könnyen meggondolható, hogy az összeadás kommutativitásán és asszociativitásán túl még a következő, a vektorműveleteknél megszokott azonosságok is érvényesek: | | Mivel a feladat feltétele szerint bármely két különböző elem pontosan egy kiválasztott részhalmazban szerepel együtt, azért esetén . Feltevésünk szerint pedig minden kiválasztott részhalmaz legalább két elemű, tehát minden -re a számok közt legalább kettő darab 1-es szerepel, azaz . Ezek alapján, ha olyan valós számok, melyekre , akkor
ami miatt csak úgy teljesülhet, ha . Az feltétel tagonként egy-egy lineáris egyenletet jelent az ismeretlenekre nézve: | | Ennek az darab egyenletből álló egyenletrendszernek tehát csak egyetlen megoldása van, mégpedig az . Megmutatjuk, hogy ez csak akkor lehetséges, ha . Valóban, ha lenne, vagyis az egyenletek száma kisebb lenne az ismeretlenek számánál, akkor az egyenletrendszernek végtelen sok megoldása lenne. Ekkor ugyanis így okoskodhatnánk: ha minden egyenletben 0 együtthatóval szerepel, akkor értékét tetszőlegesen megválaszthatjuk. Ha valamelyik egyenletben nem 0 az együtthatója, akkor abból az egyenletből kifejezhető a többi ismeretlen segítségével. Ezt a többi egyenletbe beírva kapunk egy egyenletből álló, ismeretlent tartalmazó lineáris egyenletrendszert, ahol az egyenlőségek jobb oldalán ismét csak 0-k állnak. Ezt ismételgetve végül az egyenletrendszert egyetlen egyenletre redukálhatjuk, amelyben legalább két ismeretlen szerepel, ennek viszont nyilván végtelen sok megoldása van. II. megoldás. Jelöljük halmazunkat -vel, a kiválasztott részhalmazok halmazát pedig -lel. Feladatunk valójában a véges geometriák témakörébe tartozik, ezért az ott szokásos elnevezéseket fogjuk használni. A továbbiakban elemeit pontoknak, elemeit pedig egyeneseknek nevezzük. Ha feltesszük, hogy legalább kételemű, akkor a párra teljesülnek a következők: | bármely két különböző ponthoz pontosan egy olyan egyenes van, amely őket tartalmazza, |
| minden egyenes legalább két pontot tartalmaz, |
| legalább két egyenes van. |
2. ábra Az ilyen struktúrát lineáris térnek nevezik. Feladatunk tehát annak belátása, hogy bármely lineáris térben az egyenesek száma legalább annyi, mint a pontok száma. (Ez a lineáris terekre vonatkozó alapvető egyenlőtlenség, melyet De Bruijn‐Erdős egyenlőtlenségnek neveznek, mivel az első bizonyítások e két matematikustól származnak. Az itt közölt bizonyítás megtalálható Kiss Gy. ‐ Szőnyi T.: Véges geometriák című könyvében.) A továbbiakban tegyük fel, hogy , és jelölje a ponton átmenő egyenesek számát esetén, esetén pedig az elemszámát, azaz a -edik egyenesre illeszkedő pontok számát. Ezekre az értékekre egyszerű leszámlálás segítségével felírhatunk három egyenlőséget. Ha az illeszkedő pont‐egyenes párokat először úgy számoljuk össze, hogy megnézzük, hogy egy rögzített ponton hány egyenes megy át, másodjára pedig úgy, hogy megszámoljuk, hogy egy rögzített egyenesre hány pont illeszkedik, akkor a kétféle leszámlálás eredményének meg kell egyeznie, ezért Ugyanilyen módszerrel kétféleképpen leszámolva az illeszkedő pontpár‐egyenes rendezett hármasokat, felhasználva, hogy két különböző pontnak egyértelműen létezik összekötő egyenese, a következő egyenlőséget kapjuk: Ha pedig egy pontot fixálunk és az (1) egyenlőséget csak az azon átmenő egyenesekre alkalmazzuk, akkor az egyenlőséghez jutunk. Ez szemléletesen azt tükrözi, hogy a pont minden további ponttal egy egyértelmű egyenessel van összekötve. Ha , akkor készen vagyunk. Tegyük fel, hogy . Azt kell belátnunk, hogy ekkor itt egyenlőség áll fenn. Először megmutatjuk, hogy ha a pont nincs rajta az egyenesen, akkor , és egyenlőség pontosan akkor áll, ha minden -n átmenő egyenes metszi -t. Ez abból következik, hogy -t össze tudjuk kötni minden pontjával, s az így kapott darab egyenes páronként különböző lesz, mert két különböző pontnak egyértelműen létezik összekötő egyenese. Ha egyenlőség áll, akkor pedig -n át nem is megy több egyenes. Mivel és minden nem-illeszkedő pont‐egyenes párra, így , azaz teljesül minden nem-illeszkedő pont‐egyenes párra. Adjuk össze ezeket az egyenlőtlenségeket minden ilyen párra. Ha a bal oldalakat pontról pontra összeadjuk, akkor a következőt kapjuk: | | (4) | mivel minden ponthoz pontosan olyan egyenes található, amely őt nem tartalmazza. Hasonlóan, ha a jobb oldalakat egyenesről egyenesre adjuk össze, akkor azt kapjuk, hogy Vagyis a (4) egyenlőtlenség miatt itt viszont az (1) egyenlőség miatt egyenlőségnek kell fennállnia. Ez viszont csak úgy lehet, ha , ami éppen a bizonyítandó állítás.
Megjegyzés. Ha az egyenlőség esetét tovább vizsgáljuk, akkor azt kapjuk, hogy valamennyi nem-illeszkedő pont‐egyenes párra az egyenlőségnek is teljesülni kell. Ez azt jelenti, hogy esetén a lineáris tér bármely két egyenese metszi egymást. Ha van olyan egyenes, amely két pontból áll, akkor nem nehéz belátni, hogy a lineáris terünk csak az 1. ábrán látható lehet. Itt ha , és . Ha viszont minden egyenes legalább három pontból áll, akkor struktúránk ún. véges projektív sík lesz. Erre a legegyszerűbb példa a 2. ábrán látható Fano-sík. Ebben az esetben , az egyenesek pedig , , , , , és .
|