Feladat: Pontversenyen kívüli P.166 Korcsoport: 18- Nehézségi fok: -
Megoldó(k):  Bara Tamás ,  Császár Gyula ,  Erdős Péter ,  Jakab Tibor ,  Kiss Emil ,  Kollár János ,  Kópházi József ,  Krisztin Tibor ,  Pálffy László ,  Pócsi György ,  Rapp Ferenc ,  Remsei Ferenc ,  Szaplonczay Sarolta 
Füzet: 1975/november, 149 - 150. oldal  PDF file
Témakör(ök): Sakktáblával kapcsolatos feladatok, Teljes indukció módszere, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1973/február: Pontversenyen kívüli P.166

Bizonyítsuk be, hogy készíthető 2n sakkozó számára olyan program, hogy mindenki egyszer játszik mindenkivel, és minden versenyző minden versenynapon pontosan egy játszmát játszik.

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. 1. Az 1458. gyakorlatban* n=3 esetére bizonyítottuk az állítást. Az ottani II. megoldás általánosításaként megmutatjuk, hogy a következő utasításokkal egy, a követelményeknek megfelelő programot bonyolítunk le.

 
α) egy hosszú asztalra n sakktáblát festünk rá egy sorban, és az asztal egyik oldalán levő felüket balról jobbra megszámozzuk 1-től n-ig, a túlsó oldali féltáblákat pedig ugyancsak balról jobbra (n+1)-től (2n)-ig. (A t sorszámú féltábla a (2n+1-t) sorszámúval együtt alkot egy teljes táblát.)
β) Ugyancsak 1-től 2n-ig számozzuk meg a sakkozókat, és az 1. versenynapra mindenkit a magáéval egyező sorszámú féltáblához ültetünk le játszani.
γ) A (2n) sorszámú játékost minden további játéknapon is a (2n)-es féltáblához ültetjük.
δ) A többi játékosokat napról napra a (2n-1)-edik versenynapig ‐ ennyi mérkőzést kell mindegyiküknek játszania ‐ az előző napi helyüknél 1-gyel kisebb sorszámú féltáblához ültetjük, kivéve azt, aki az 1-es féltáblánál ült, őt másnapra a (2n-1)-eshez ültetjük.
2. Így mindenkinek mind a (2n-1) napon van ellenfele, és csak azt kell belátnunk, hogy bármely két kiszemelt játékos pontosan egy napon ül egymással szemben. Nyilvánvaló, hogy ez a (2n)-edik játékosra teljesül, ő a d sorszámú versenynapon a d-edik sakkozóval mérkőzik meg; tehát fordítva, a többiek is mind játszanak vele. Erre tekintettel tovább úgy vesszük, hogy (2n)-es ott sincs, a d-edik napon a d-edik játékos szabadnapos; ezáltal programunk (2n-1) számú játékos körmérkőzésére is alkalmazható. Úgy vesszük, hogy a szabadnaposé az 1-esen felül a (2n)-es féltábla is.
Tetszőleges sakkozópár mérkőzésének napját az alábbiak szerint kapjuk. Gondoljuk zárt körbe állítva a (2n-1) versenyzőt sorszámaik rendjében, az 1-est és a (2n-1)-est is szomszédnak véve. A körben a kiszemelt i, j játékosok közti húr egyik partján páratlan számú sakkozó alkotja az ívet, a másikon páros számú, ami 0 is lehet. Keressük meg az előbbi ívet ,,megfelező'' játékost (ti. akit i-től és j-től ugyanannyi játékos választ el), és ültessük le a játékosok körét asztalunk köré úgy, hogy a ,,felező'' játékos legyen a szabadnapos. Az ő sorszáma adja meg, hányadik versenynapon játsszák az i:j mérkőzést.
Mármost i-t rögzítve, j-vel bejárva a többi játékosokat, a páratlan számú játékost tartalmazó ívet felező játékos napról napra más lesz, így az i játékos minden versenytársával megmérkőzik és mindegyikkel más versenynapon. ‐ Ezzel az állítást bebizonyítottuk.
 

II. megoldás. Teljes indukcióval bizonyítjuk az állítást, az I. megoldásból csak azt használva fel, hogy (2n-1) számú sakkozó esetére mindig megfelel a 2n játékosra készített program.
Tegyük fel, hogy s számú játékos esetére már beláttuk az állítást, erre támaszkodva 2s számú játékos esetére bizonyítunk. Vehetjük, hogy s számú fiú és s számú leány játszik. Először az egyneműek játszmáit bonyolítjuk le.
Ha s páros, akkor a feltevés alapján az egyneműek játszmái a verseny (s-1)-edik napján befejeződnek. Az s-edik naptól kezdve egy körgyűrű alakú asztal belső s helyére ültetjük tetszőleges rendben a leányokat ‐ és az ő helyüket a hátra levő napokra rögzítjük ‐, majd velük szembe a fiúkat ugyancsak tetszőlegesen ‐; ezeket pedig napról napra 1 hellyel tovább ültetjük ugyanabban a körüljárási irányban. Így a hátra levő s nap alatt minden egyes fiú minden egyes leánnyal lejátssza a mérkőzését, a verseny az (s-1)+s=(2s-1)-edik napon befejeződik.
Ha pedig s páratlan, akkor az egyneműek mérkőzései s napig tartanak, viszont napról napra 1 leány és 1 fiú szabadnapos, ővelük már ekkor játszatjuk le mérkőzésüket, tovább pedig úgy módosítjuk a fentieket, hogy az (s+1)-edik napon előkészítésül minden egyes fiút azzal az (egyetlenegy) leánnyal ültetünk szembe, akivel már játszott, és a fiúk így kialakított körét azonnal 1 hellyel tovább léptetjük. Így a különneműek mérkőzései csak (s-1) napig tartanak és a teljes (2s-1) nap alatt mindenki mindenkivel egyszer szembekerül.
s=2 játékosra a program egyetlen mérkőzésből áll. Ebből bizonyításunk szerint 4 és 3 játékos esetére létezik program, majd 8 és 7, valamint 6 és 5 játékosra, ezekből nyilvánvalóan a 16-ig, ..., 2r-ig terjedő számokra, és így tovább.
*Lásd a megoldást K. M. L. 51. (1975) 13. oldal.