Feladat: 1977. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Cseri István ,  Knébel István ,  Kozma László ,  Pyber László ,  Spissich László ,  Surány Gábor ,  Zádori László ,  Zempléni András 
Füzet: 1978/február, 55 - 57. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Kombinatorikai leszámolási problémák, Teljes indukció módszere, Maradékos osztás, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1978/február: 1977. évi Kürschák matematikaverseny 3. 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.

I. megoldás. Megkérdezünk mindenkit, hány ismerőse van egy-egy iskolában. Legyen a legkisebb hallott szám k. Ez nem 0, mert mindenkinek több ismerőse van a másik két iskolából, mint ahány tanuló jár egy-egy iskolába.
Legyen mondjuk András az A iskolából egy tanuló, akinek k ismerőse van a B iskolában; ekkor a C iskolában n+1-k ismerőse van és k-1 tanulót nem ismer.
András egy B iskolabeli ismerőse, mondjuk Bálint legalább k tanulót ismer a C iskolából. Ezek közül legalább egy ismeri Andrást is. Ha Csongor egy közös ismerős, akkor hármuk közül mindenki ismeri a másik kettőt. A feladat állítása tehát igaz.

 
Megjegyzés. A feladat állítása akkor is igaz, ha a feltételt úgy módosítjuk, hogy minden tanulónak legalább n+1 ismerőse van a másik két iskolában. Ekkor a bizonyítás annyiban módosul, hogy Andrásnak a C iskolában legalább n+1-k ismerőse van, s így legfeljebb k-1 tanulót nem ismer. A gondolatmenet további része változatlanul érvényes.
Nem vezethetjük vissza a módosított állítást az eredetire úgy, hogy egyes ismeretségeket figyelmen kívül hagyunk. Lehetséges ugyanis, hogy Andrásnak pl. több mint n+1 ismerőse van a másik két iskolában, azonban mindegyik ismerőse csak n+1 tanulót ismer a másik két iskolából. Ekkor András bármelyik ismeretségét figyelmen kívül hagyva, volt ismerősének már csak n ismerőse marad a másik két iskolában.
 
II. megoldás. A megjegyzésben említett általánosabb állítást bizonyítjuk, amelyik szerint:
Ha minden tanuló a másik két iskolában együtt legalább n+1 tanulót ismer, akkor kiválasztható mindegyik iskolából egy-egy tanuló úgy, hogy mindegyikük ismerje a másik kettőt.
A bizonyítást teljes indukcióval végezzük.
Ha történetesen mindegyik iskolának csak 1‐1 tanulója van, akkor a feltétel éppen azt kívánja, hogy mindegyikük ismerje a másik kettőt.
Legyen most m>1 és tegyük fel, hogy minden n<m természetes számra igaz az állítás, ha az iskolákba n gyerek jár. Legyen továbbá A, B és C három iskola, amelyek mindegyikébe m tanuló jár és mindegyikük legalább m+1 tanulót ismer a másik két iskolából.
Az A iskola a1 tanulója ismerje a B iskolából b1-et, ő a C iskolából c1-et. Ha c1 ismeri a1-et, akkor ő hármukra teljesül a feladat állítása. Ha nem, akkor c1 egy A-beli ismerőse legyen a2 és folytassuk az eljárást mindig ugyanebben a sorrendben véve az iskolákat, míg egy olyan tanulóhoz nem érünk, aki egyszer már szerepelt a felsorolt ismerősök közt. Ez a tanuló és az utána felsoroltak egy olyan kört alkotnak, amelyben mindenki ismeri a szomszédait és amelyikhez mindegyik iskolának ugyanannyi tanulója tartozik. Legyen ez a szám k. Ha k=1, ez azt jelenti, hogy teljesül a feladat állítása.
Ha k=m (a kör tartalmazza az összes tanulót), akkor válasszunk ki egy tanulót, pl. az A-beli a1-et. A körben szomszédos B és C-beli tanulók m párt alkotnak, amelyek bi, c, (i=1,2,...,m) tanulói ismerik egymást. (A 6. ábra a tanulókat ponttal, az ismeretséget összekötéssel szemlélteti.)
 
 

6. ábra
 

Mivel a1-nek a két iskolában legalább n+1 ismerőse van, így legalább egy pár mindkét tagját ismeri. Ekkor azonban erre a 3 tanulóra teljesül a feladat állítása.
Ha 1<k<m, akkor nézzük az iskoláknak a körhöz nem tartozó tanulóit. Minden iskolában (m-k)-an vannak. Ha mindegyiküknek legalább m-k+1 ismerőse van a másik két iskola megmaradt tanulói közt, akkor az indukciós feltétel szerint kiválasztható a feladat állítását kielégítő három tanuló.
Ha pl. az A iskolabeli ak+1-nek a B és C iskolában megmaradt tanulók közt legfeljebb m-k ismerőse van, akkor a körnek legalább k+1B-be és C-be járó tanulóját ismeri. Ezeket azonban a kör most k darab ismerősökből álló párba sorolja, s így ak+1 ismer legalább egy ilyen párt. Minden esetben találtunk tehát a feladat állítását kielégítő hármast. Ezzel az indukciós bizonyítást befejeztük.
 
Megjegyzések. 1. Ez a bizonyítás nem alkalmas a feladatnak az eredeti formában való bizonyítására, mert a bizonyítás második részében, ha minden tanulónak m+1 ismerőse van, és az iskolánként k tanulót tartalmazó kört kivéve, a visszamaradó tanulók közül senki sem ismer a körből k-nál több tanulót, akkor lehetnek, akik a körből k-nál kevesebb tanulót ismernek és így a visszamaradók közül (m-k+1)-nél többet. Ha viszont bebizonyítottuk ezt az általánosabb állítást, az tartalmazza speciális esetként az eredetit is.
2. Nyilvánvalóan nem elég, ha csak annyit teszünk fel, hogy minden tanulónak n ismerőse van a másik két iskolában. Legyen minden iskolában páros számú tanuló, mondjuk mindegyikben m fiú és m lány. Ha az A iskola lányai ismerik a B iskolából a lányokat, a C-ből a fiúkat, az A-ba járó fiúk a B-ből a fiúkat, a C-ből a lányokat, továbbá a B-ből és C-ből a lányok a lányokat, a fiúk a fiúkat, akkor mindenkinek annyi ismerőse van, ahány gyerek egy-egy iskolába jár, de nincs a feladat követelményeit kielégítő három tanuló.
Ha az egy-egy iskolába járó tanulók száma páratlan, akkor nem is lehet mindenkinek pontosan annyi ismerőse, ahányan egy iskolába járnak, hiszen akkor mindenkit megkérdezve ismerősei számáról, minden ismeretséget kétszer vennénk számba, viszont páratlan számú tanuló mindegyike páratlan számú ismerőst említene, ami együtt ismét páratlan számot adna.
3. Felmerülhet az a kérdés is, hogy megvalósítható-e tetszés szerinti tanulószám mellett a feladat eredeti feltétele. A válasz igenlő. Egy lehetőség a megvalósításra a következő. Ha páratlan számú tanuló, n=2m-1 van iskolánként, akkor sorszámozzuk iskolánként a tanulókat. Az A iskola minden tanulója ismerje a B és a C iskola vele egyenlő sorszámú tanulója utáni m tanulót, úgy értve, hogy ha a sor végére érünk, akkor az elejéről folytatjuk. Ekkor a B és a C iskola minden tanulója A-ból a vele egyező sorszámú tanuló előtti m tanulót ismeri. Ismerje továbbá a B iskola minden tanulója C-ből a vele egyező sorszámú tanuló utáni m tanulót. (Ekkor a C-beli tanulók B-ből a velük egy sorszámú tanuló előtti m tanulót ismerik.) Ekkor minden tanulónak 2m=n+1 ismerőse van.
Ha viszont minden iskolába n=2m tanuló jár, mondjuk m fiú és m lány, akkor ismerjék egymást a különböző iskolabeli lányok a különböző iskolabeli fiúkkal, továbbá az A iskolabeli fiúk ismerjék a B iskolából a velük egy sorszámú lányt, a B-beli fiúk a C-beli velük egy sorszámú lányt, és a C-beli fiúk az A-beli velük egy sorszámú lányt. Ekkor mindenkinek 2m+1=n+1 ismerőse van. Természetesen számos más lehetőség is van a feltételek megvalósítására.