Feladat: B.3685 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bednay Dezső ,  Bitai Tamás ,  Bodnár József ,  Csajbók Bence ,  Csorba János ,  Czank Tamás ,  Dudás László ,  Dömötör Erika ,  Erdélyi Márton ,  Hegyháti Máté ,  Hubay Tamás ,  Jankó Zsuzsanna ,  Kirilly György ,  Kisfaludy-Bak Sándor ,  Kiss Gábor ,  Kiss Orsolya ,  Kiss-Tóth Christian ,  Korándi Dániel ,  Kunovszky Péter ,  Mészáros György ,  Nagy Csaba ,  Pálinkás Csaba ,  Poronyi Balázs ,  Rácz Miklós ,  Strenner Balázs ,  Sümegi Károly ,  Szabó Botond ,  Szabó Tamás ,  Szirtes Krisztina ,  Török Zoltán Bálint ,  Vaskó Richárd 
Füzet: 2005/április, 213 - 214. oldal  PDF file
Témakör(ök): Szöveges feladatok, Kombinatorikai leszámolási problémák, Természetes számok, Feladat
Hivatkozás(ok):Feladatok: 2003/december: B.3685

Egy számítógépes játékban minden egyes játék alkalmával egész pontszámot érhetünk el. A legjobb 30 eredményt számon tartó listán a játék megalkotója egy-egy fantázianév mellett a 30,29,28,...,1 pontszámokat tüntette fel. Egy játék során elért eredményünk ‐ saját nevünk alatt ‐ akkor kerül fel a listára, ha pontszámunk nagyobb, mint az aktuális listán szereplő legkisebb pontszám, amely ezután értelemszerűen lekerül a listáról. Egyenlő pontszámok esetén az utoljára felkerült pontszám kerül le a listáról. A besorolás ``alulról'' történik, tehát csak azokat az eredményeket fogjuk megelőzni a listán, amelyeknél nagyobb pontszámot értünk el. Feltéve, hogy minden egyes játék után feljutunk a listára, legalább hány játékot kell lejátszanunk ahhoz, hogy biztosan a mi nevünk szerepeljen a listán valamennyi pontszám mellett?
 

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. Vizsgáljuk meg, hogy egy adott pontszámot hányszor érhetünk el a játék során, hogy ezzel felkerüljünk a listára. Azt állítjuk, hogy ha 1p30, akkor p pontot legfeljebb (p-1)-szer érhetünk el. Valóban, a játék folyamán egy adott pontszámnál nagyobb eredmények száma a listán nem csökken, és kezdetben (31-p) darab (p-1)-esnél jobb eredmény szerepel a táblázaton. A játék programja pedig úgy működik, hogy ezek mind megelőzik a mi p pontunkat.
Mivel 1-nél kisebb pontszámmal nem kerülhetünk a listára, míg 30-nál nagyobb pontszámból 30 játék elég, azért

30+p=130(p-1)=465
játékot mindenképpen le kell játszanunk ahhoz, hogy már csak a mi nevünk szerepeljen a listán.
Most megmutatjuk, hogy ennyi játékra szükségünk is lehet, azaz alakulhat úgy a játékok sorozata, hogy csak a 465. játékkal foglaljuk el a teljes listát. Ha a fentiek szerint minden p30 értékre éppen (p-1)-szer érjük el a p pontszámot, mégpedig növekvő sorrendben, majd ezek után harminc egymást követő alkalommal szerzünk 30-nál több pontot, akkor (1+2+3+...+29+30)=465 játékot játszottunk, és csak az utolsó játékunk után tűnik el valamennyi álnév a listáról.
Legalább 465 játékot kell játszanunk, hogy biztosra menjünk, és ennyi elég is. Ezzel a bizonyítást befejeztük.
 
II. megoldás. Pontosan akkor kerülünk fel a listára, ha az utolsó, 30. helyezettet megelőzzük. Ebből következik, hogy ha a lista változik, akkor a pontszámok összege legalább 1-gyel nő. Kezdetben ez az összeg 465. Ha 31-pontosnak tekintjük a 30-pontos fantázianevet megelőző eredményeinket, akkor amíg szerepel fantázianév a listán, az összpontszám nőni fog. 465 sikeres játékot követően az összpontszám legalább 930-ra nő, de 930=3031, azaz ekkor 30-as pontszám már nem szerepelhet a listán.
Azt, hogy 465 játékra szükség lehet, az előző megoldásban látottak szerint igazolhatjuk.
 
Megjegyzések. 1. A második megoldás gondolatmenetéből következik, hogy csak a második részben megadott játékeredmény-sorrendben lehet szükségünk 465 játékra, hiszen ha a pontszámösszeget nem 1-gyel növeljük valamelyik játék során, akkor előbb érjük el a 930-as határt.
2. A feladat statisztikája szerint kiemelkedően sok hiányos megoldás érkezett. A rengeteg 3-pontos dolgozat szerzői lényegében helyes megoldásuk első felét azzal a kijelentéssel gondolták letudni, hogy ,,elegendő a legrosszabb'' esetet vizsgálni: ,,amikor  a lehető legrosszabb eredménnyel kerülünk fel''.  Valóban ez a ,,legrosszabb'' eset, de hogy miért, arra éppen a 2. megoldás világít rá. Hiába ,,látszik szemléletesen'', ennek bizonyítása lényeges része a feladatnak.