Problem B. 5066. (December 2019)

B. 5066. Thirty students were taking an exam in a subject called ``Tautologics''. The students were sitting down in a classroom, and the teacher asked them a single question, ``How many of the students sitting in this room are going to fail this exam altogether?'' The students had to name a number, one by one, in a row. After each answer, the teacher immediately announced the result which was either ``pass'' or ``fail''. When the exam was over, the Student Union requested an inspection by the School District. If it turns out that any student gave the correct answer but still failed the exam, all the results will be cancelled, and everyone will receive a ``pass'' grade. Is there a strategy for the students to achieve that everyone should pass the exam?

Russian problem

(5 pont)

Deadline expired on January 10, 2020.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

117 students sent a solution.
5 points:	82 students.
4 points:	18 students.
3 points:	3 students.
0 point:	14 students.

Problems in Mathematics of KöMaL, December 2019