Feladat: 1960. évi Kürschák matematikaverseny 1. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bollobás Béla ,  Máté Attila ,  Mezei Ferenc 
Füzet: 1961/március, 98 - 100. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Logikai feladatok, Gráfelmélet, Természetes számok, Oszthatóság, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1961/március: 1960. évi Kürschák matematikaverseny 1. 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.

Megjegyzés. A feladat csak arra az esetre vonatkozik, amikor a társasutazásnak van legalább négy résztvevője. Ha ez nem áll fenn, akkor a feladat feltevése és állítása egyaránt semmitmondó.

 
I. megoldás. Legyen A és B két olyan résztvevő, akik korábban még nem találkoztak. Feltehetjük, hogy van két ilyen, hiszen különben bármely résztvevő megfelelne a feladat kívánalmának. Azt is feltehetjük, hogy van az AB pártól különböző utaspár, akik szintén először találkoznak, mert különben minden A-tól és B-től különböző résztvevő megfelelne, és bármely négy résztvevő között van ilyen (sőt legalább kettő).
Az AB-től különböző, ugyancsak először találkozó utaspárban szerepelnie kell A-nak vagy B-nek, mert ha ez a CD utaspár A-tól és B-től különböző útitársakból állna, akkor A, B, C, D közül egyik sem találkozott volna korábban a másik három mindegyikével, és ez ellentmond a feladat feltevésének. Legyen tehát AC ez az AB-től különböző, ugyancsak először találkozó utaspár, hiszen minden lehetséges eset ezzé az esetté betűzhető át.
Azt vizsgáljuk most, hogy mely AB-től és AC-től különböző utaspár állhat olyanokból, akik máskor még nem találkoztak. Az előző bekezdés szerint A-nak vagy B-nek az ilyen utaspárban is szerepelnie kell, de ugyanolyan indokolással szerepelnie kell benne A és C valamelyikének is. Eszerint ez a további először találkozó utaspár csak BC vagy pedig AD lehet, ahol D egy még nem említett résztvevő.
Az utóbbi eset azonban lehetetlen, mert akkor az A, B, C, D résztvevőkre nem teljesülne a feladat feltevése. Eszerint az AB, AC párokon kívül csak BC állhat egymással először találkozó útitársakból, tehát minden A-tól, B-től és C-től különböző résztvevőnek találkoznia kellett már minden útitársával. Minthogy bármely négy résztvevő között van ilyen, a feladat állítása helyes.
 
Megjegyzés. Egyszerűbbé válik feladatunk megoldása, ha ábrázoljuk a vizsgált viszonyokat, és megfelelő elnevezéseket vezetünk be.
Ábrázoljuk a társasutazás résztvevőit egy-egy ponttal, és kössünk össze kettőt-kettőt közülük egy vonaldarabbal akkor, ha a két pontnak megfelelő útitárs korábban még nem találkozott. Az összekötő vonalakat úgy választjuk meg, hogy ne haladjanak át más résztvevőt ábrázoló ponton. Ilyen módon egy gráfhoz jutottunk, amelynek szögpontjai az útitársaknak, élei pedig az először találkozó utaspároknak felelnek meg. Ha a gráf élei esetleg metszik vagy érintik egymást, közös pontjukat nem számítjuk a gráf szögpontjai közé. Az általunk bevezetett gráfnak véges sok szögpontja van, minden éle két-két egymástól különböző szögpontot köt össze, és ugyanazt a szögpontpárt csak legfeljebb egy él köti össze. Ha a következőkben gráfról lesz szó, mindig csak ilyen gráfra gondolunk.
Ha feladatunkat a most bevezetett gráfra szövegezzük meg, a feladat a következő alakot ölti: Egy gráfnak nincs négy olyan szögpontja, amelyeknek mindegyikéből kiindul él a másik három szögpont valamelyikéhez. Bebizonyítandó, hogy a gráf bármely négy szögpontja között van olyan, amelyből nem indul ki él. Semmitmondó esetek kizárása kedvéért hozzátehettük volna, hogy a gráfnak legalább négy szögpontja van.
Az így szövegezett feladat megoldása rövidebb és áttekinthetőbb. Ezt a közölt megoldás átszövegezésén mutatjuk be:
Feltehetjük, hogy a gráfnak van legalább két éle, a és b, mert különben legfeljebb két szögpont kivételével egyikből sem indul ki él, és bármely négy szögpont között van ilyen. Az a, b élek egyik végpontja közös, mert különben négy végpontjukra nem teljesülne a feladat feltevése. Ebből az is következik, hogy az a, b éleken kívül csak olyan él szerepelhet, amelynek van közös pontja a-val is és b-vel is. Az ilyen él tehát (1. ábra) vagy a és b szabad végpontját köti össze, vagy pedig közös végpontjukból indul ki. Az utóbbi eset lehetetlen, mert akkor a három él négy végpontja ellentmondana a feladat feltevésének. Ezek szerint csak az a, b élek három végpontjából indul ki él, bármely négy szögpont között van tehát olyan, amelynek nincs meg ez a tulajdonsága.
 
 
1. ábra
 

II. megoldás. Feltesszük, hogy van legalább négy olyan résztvevő, aki valamely útitársával a társasutazáson találkozik először, hogy tehát a feladat állítása nem teljesül, és bebizonyítjuk, hogy akkor a feladat feltevése sem teljesülhet, hogy tehát van négy olyan résztvevő, akik közül egyik sem találkozott korábban a másik három mindegyikével. Ez bizonyítja majd, hogy ha a feladat feltevése teljesül, állításának is teljesülnie kell.
Ismét abból indulunk ki, hogy A és B először találkozik egymással. Ha két tőlük különböző résztvevő korábban még nem találkozott, akkor máris találtunk az állításunkat bizonyító négy résztvevőt.
Legyen C és D két olyan további résztvevő, akik nem mindenkivel találkoztak korábban. Mostani feltevésünk szerint biztosan van két ilyen. Az előző bekezdés szerint csak azzal az esettel kell foglalkoznunk, amikor C is és D is csak már megbetűzött résztvevővel találkozik először. Ekkor azonban A, B, C és D négy olyan útitárs, akiknek egyike sem találkozott korábban a másik három mindegyikével, akik tehát állításunk helyességét bizonyítják.
 
Megjegyzések. 1. Második megoldásunk a gráfokra átültetett feladat szövegének további átfogalmazását teszi indokolttá. Ha a gráfból elhagyjuk azokat szögpontokat, amelyekből nem indul ki él, akkor a feladat következő megfogalmazásához jutunk: Egy gráf minden szögpontjából kiindul él, de nincs négy olyan szögpontja, amelyeknek mindegyikéből kiindul él a másik három valamelyikébe. Bebizonyítandó, hogy a gráfnak négynél kevesebb szögpontja van.
Ha ezt a feladatot ugyanúgy átszövegezzük, ahogyan az eredeti feladattal második megoldásunk elején tettük, akkor feladatunk következő újabb szövegéhez jutunk: Egy gráfnak legalább négy szögpontja van, és minden szögpontjából kiindul él. Bebizonyítandó, hogy van a gráfnak négy olyan szögpontja, amelyeknek mindegyikéből kiindul él a másik három valamelyikéhez. Az olvasóra hagyjuk, hogy második megoldásunkat e feladat megoldásává írja át.
2. Második megoldásunk mintájára bebizonyítjuk, hogy utolsó állításunk akkor is helyes, ha benne 4 helyett tetszőleges páros 2k természetes szám áll. Az általánosított feladat tehát a következőképpen szól: Egy gráfnak legalább 2k szögpontja van, és minden szögpontjából kiindul él. Bebizonyítandó, hogy van a gráfnak 2k olyan szögpontja, amelyeknek mindegyikéből kiindul él a többi 2k-1 szögpont valamelyikéhez.
Válasszunk ki gráfunkból lehetőleg sok független élt, azaz olyanokat, amelyeknek végpontjai mind különbözők. Ha van k független él, akkor ezek végpontjai máris bizonyítják állításunk helyességét. Ha csak j<k független élt választhattunk ki, ha tehát ezektől független (j+1)-edik él már nincs, akkor 2j végpontjukról tudjuk, hogy minden további szögpontból kiinduló él ennek a 2j végpontnak valamelyikébe fut. Ha tehát ehhez a 2j végponthoz bármely további 2k-2j szögpontot csatolunk, az állításunkat bizonyító 2k szögponthoz jutunk.
Megtehetnők, hogy a most bizonyított tényt annyiféleképpen fogalmazzuk át, ahányféleképpen ezt eredeti feladatunkkal megtettük. Megelégszünk azzal, hogy csak az eredeti megszövegezésbe öltöztetett eredményünket mondjuk ki: Ha egy társasutazás bármely 2k résztvevője között van olyan, aki a többi 2k-1 mindegyikével már máskor is találkozott, akkor bármely 2k résztvevő között van olyan, aki már minden útitársával találkozott. Semmitmondó eseteket zárunk ki, ha megköveteljük, hogy a társasutazásnak legalább 2k résztvevője van. Megemlítjük, hogy a k=1 esetben az állítás nyilvánvalóan helyes, a k=2 eset pedig eredeti feladatunk állítása.
3. Felmerül a kérdés, hogy helyes marad-e utolsó eredményünk, ha benne 2k helyett egy páratlan 2k+1 szám áll. Bebizonyítjuk, hogy így már hamis állításhoz jutunk, hogy tehát ez a módosítás az eddig említett különféle megszövegezések egyikénél sem megengedett. A 2k+1=1 esetet figyelmen kívül hagyjuk, mert ebben az esetben a feladat értelmét veszti.
Bizonyítás céljából elég egy kellően sok független élből álló gráfot tekintenünk. Ennek van legalább 2k+1 szögpontja, és minden szögpontjából kiinduló él. Nincs viszont 2k+1 olyan szögpontja, amelyek mindegyikéből kiindul él a többi 2k szögpont valamelyikébe. Akárhogyan szemelünk ki ugyanis 2k+1 szögpontot, az ezeket összekötő élek végpontjainak száma természetesen csak páros lehet, s így ezek nem meríthetik ki a 2k+1 szögpontot. .