|
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 | MathML |
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 |
|
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 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 sakktáblát festünk rá egy sorban, és az asztal egyik oldalán levő felüket balról jobbra megszámozzuk -től -ig, a túlsó oldali féltáblákat pedig ugyancsak balról jobbra -től -ig. (A sorszámú féltábla a sorszámúval együtt alkot egy teljes táblát.) Ugyancsak -től -ig számozzuk meg a sakkozókat, és az . versenynapra mindenkit a magáéval egyező sorszámú féltáblához ültetünk le játszani. A sorszámú játékost minden további játéknapon is a -es féltáblához ültetjük. A többi játékosokat napról napra a -edik versenynapig ‐ ennyi mérkőzést kell mindegyiküknek játszania ‐ az előző napi helyüknél -gyel kisebb sorszámú féltáblához ültetjük, kivéve azt, aki az -es féltáblánál ült, őt másnapra a -eshez ültetjük. 2. Így mindenkinek mind a 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 -edik játékosra teljesül, ő a sorszámú versenynapon a -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 -es ott sincs, a -edik napon a -edik játékos szabadnapos; ezáltal programunk számú játékos körmérkőzésére is alkalmazható. Úgy vesszük, hogy a szabadnaposé az -esen felül a -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 versenyzőt sorszámaik rendjében, az -est és a -est is szomszédnak véve. A körben a kiszemelt , 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 is lehet. Keressük meg az előbbi ívet ,,megfelező'' játékost (ti. akit -től és -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 mérkőzést. Mármost -t rögzítve, -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 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 számú sakkozó esetére mindig megfelel a játékosra készített program. Tegyük fel, hogy számú játékos esetére már beláttuk az állítást, erre támaszkodva számú játékos esetére bizonyítunk. Vehetjük, hogy számú fiú és számú leány játszik. Először az egyneműek játszmáit bonyolítjuk le. Ha páros, akkor a feltevés alapján az egyneműek játszmái a verseny -edik napján befejeződnek. Az -edik naptól kezdve egy körgyűrű alakú asztal belső 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 hellyel tovább ültetjük ugyanabban a körüljárási irányban. Így a hátra levő nap alatt minden egyes fiú minden egyes leánnyal lejátssza a mérkőzését, a verseny az -edik napon befejeződik. Ha pedig páratlan, akkor az egyneműek mérkőzései napig tartanak, viszont napról napra leány és 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 -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 hellyel tovább léptetjük. Így a különneműek mérkőzései csak napig tartanak és a teljes nap alatt mindenki mindenkivel egyszer szembekerül. játékosra a program egyetlen mérkőzésből áll. Ebből bizonyításunk szerint és játékos esetére létezik program, majd és , valamint és játékosra, ezekből nyilvánvalóan a -ig, , -ig terjedő számokra, és így tovább. Lásd a megoldást K. M. L. 51. (1975) 13. oldal. |
|