Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5066. feladat (2019. december)

B. 5066. Harminc diák a ,,Tautologika'' nevű tantárgyból vizsgázik. A diákok egy teremben ülnek, és a tanár egyetlen kérdést tesz fel nekik: ,,Az itt ülő 30 diákból összesen hányan fognak megbukni ezen a vizsgán?'' A diákoknak sorban egy-egy számot kell mondani. Minden egyes válasz elhangzása után a tanár azonnal kihirdeti az eredményt is, ami ,,megfelelt'' vagy ,,megbukott'' lehet.

A hallgatói önkormányzat elérte, hogy a vizsga után egy szakfelügyelő ellenőrizze az eredményeket. Ha van olyan diák, aki helyesen válaszolt, de mégis megbukott, a vizsga összes eredményét érvénytelenítik, és mindenki ,,megfelelt'' minősítést kap.

Van-e a diákoknak olyan stratégiája, ami biztosítja, hogy mindegyikük átmenjen a vizsgán?

(Orosz feladat)

(5 pont)

A beküldési határidő 2020. január 10-én LEJÁRT.


Megoldás. Megmutatjuk, hogy a diákoknak van megfelelő stratégiája, éspedig a következő stratégiát követve biztosan célt érnek:

Az éppen soron következő diák megszámolja, eddig hányan buktak meg, majd bemondja az ennél 1-gyel nagyobb számot. (Másképpen fogalmazva úgy válaszol, mintha ő maga megbukna, de a később következők már mind átmennének a vizsgán.)

Belátjuk, hogy ez a stratégia garantálja, hogy átmenjenek a vizsgán. Ha a tanár mindenkinek megfelelt minősítést ad, akkor nincs szükség a szakfelügyelő segítségére, a diákok elérték céljukat. (Bár a feladat megoldásához nem tartozik hozzá, de megjegyezzük, hogy ebben az esetben annak ellenére lett mindegyikük vizsgája sikeres, hogy a helyes értéket – ami a 0 – senki nem találta el, ugyanis mindenki az 1 választ adta.)

Ha legalább egyvalakit nem engedett át a tanár, akkor tekintsük azt a diákot, aki utolsóként bukott meg. Utána már mindenki átment, ő maga megbukott, így a vizsgán megbukók száma éppen annyi, amennyit ő mondott. A szakfelügyelő ellenőrzése után tehát a vizsga összes eredményét érvénytelenítik, és mindenki megfelelt minősítést kap.

Ezzel igazoltuk, hogy a diákoknak van megfelelő stratégiája.

Megjegyzés. Valójában ez az egyetlen megfelelő stratégia. Tegyük fel ugyanis, hogy a diákok egy másik stratégiát követnek. A tanár egészen addig tetszés szerint enged át vagy buktat, amíg a diákok a fent megadott stratégia szerinti válaszokat adják. Az első diákot, aki nem aszerint válaszol, viszont megbuktatja, majd utána mindenkit átenged. Az utolsóként megbukott diák válasza nem helyes, hiszen akkor a fenti stratégia szerinti választ kellett volna adnia, de másként válaszolt. A korábban megbukott diákok a fenti stratégiának megfelelő választ adták, azonban mindegyikük után megbukott még más is (például az előbb vizsgált, utolsóként megbukó diák), így az ő válaszuk is helytelen. Tehát egyetlen olyan bukott diák sincs, aki helyesen válaszolt volna, vagyis a vizsga eredményét nem érvénytelenítik. Ez azt jelenti, hogy a tanár bárhogyan is buktatja, illetve engedi át őket, a diákoknak a fenti stratégia szerint kell válaszolniuk, hogy biztosan elérjék céljukat.


Statisztika:

A B. 5066. feladat értékelése még nem fejeződött be.


A KöMaL 2019. decemberi matematika feladatai