Problem B. 5098. (April 2020)

B. 5098. Two players, First and Second, are playing the following game:

First selects a positive integer not greater than 2020, which Second is trying to find out by guessing (by naming a number as a guess).

The possible answers of First are as follows: ``My number is smaller than that.''; ``You are right.''; ``My number is greater than that.''

If the answer is ``My number is smaller than that'' or ``You are right'', then Second pays 10 forints (Hungarian currency) to First. If the answer is ``My number is greater than that'' then he pays 20 forints.

What is the minimum possible amount of money that Second needs to have in order to be certain that he can find out the number, and what strategy should he use?

(The game terminates with the first ``You are right'' answer, even if Second already knows the number before asking the last question.)

(5 pont)

Deadline expired on May 11, 2020.

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

Megoldás. Legyen \(\displaystyle x_n\) a legnagyobb olyan egész, amelyre ha \(\displaystyle 1,2,...,x_n\) a lehetséges (gondolt) számok, akkor biztosan elérhető, hogy a nyeremény legfeljebb \(\displaystyle n\cdot 10\). Az \(\displaystyle \{ x_n \}\) sorozat nyilván szigorúan monoton növő, továbbá \(\displaystyle x_1=1\), és \(\displaystyle x_2=2\) (ha \(\displaystyle 1,2\) a lehetséges számok, akkor először a 2-re kell kérdezni; ilyenkor az ,,1-es gondolt'' szám esetén fogunk 20 Ft-ot fizetni).
Tegyük fel innentől, hogy \(\displaystyle n\ge2\) és keressük \(\displaystyle x_n\) pontos értékét. Tegyük fel, hogy már ismerjük \(\displaystyle x_n\) értékét, ekkor az \(\displaystyle 1,2,...,x_n\) számok esetén legfeljebb \(\displaystyle n \cdot 10\) Ft-ot fizetünk.
– Ha ekkor a \(\displaystyle t\) számra tippelt Második, akkor ,,kisebb'' válasz esetén máris fizet \(\displaystyle 10\)-et, és \(\displaystyle t-1\) olyan lehetséges szám marad, amire Kezdő gondolhatott. A maradék \(\displaystyle t-1\) számot (\(\displaystyle x_n\) definíciója alapján) legfeljebb \(\displaystyle 10\cdot(n-1)\) Ft költséggel ki kell találnunk, tehát \(\displaystyle t-1\le x_{n-1}\).
–Ha a válasz ,,nagyobb'', akkor pedig \(\displaystyle 20\)-at fizet Második, és marad \(\displaystyle x_n-t\) lehetséges szám, amire Kezdő gondolhatott. A maradék \(\displaystyle x_n-t\) számot (\(\displaystyle x_n\) definíciója alapján) legfeljebb \(\displaystyle 10\cdot(n-2)\) Ft költséggel ki kell találnunk, tehát \(\displaystyle x_n-t\le x_{n-2}\). Összeadva \(\displaystyle x_{n-1}+x_{n-2} \geq t-1+x_n-t \geq x_n-1\). Azaz \(\displaystyle x_n \leq x_{n-1} + x_{n-2}+1\).
A fenti becslés éles, ugyanis, ha \(\displaystyle k=(x_{n-1}+x_{n-2}+2)\), azaz az \(\displaystyle 1,2,...,(x_{n-1}+x_{n-2}+2)\) számok a lehetséges számaink, akkor ha a Második által tippelt \(\displaystyle t\) számra \(\displaystyle t>x_{n-1}+1\), akkor ,,kisebb'' válasz esetén (\(\displaystyle x_{n-1}\) definíciója alapján) a maradék legalább \(\displaystyle x_{n-1}+1\) számot nem tudjuk kitalálni biztosan a megfelelő költséggel, míg ha \(\displaystyle t\leq x_{n-1}+1\), akkor ,,nagyobb'' válasz esetén (\(\displaystyle x_{n-2}\) definíciója alapján) a maradék legalább \(\displaystyle x_{n-2}+1\) számot nem tudjuk kitalálni biztosan a megfelelő költséggel. Azaz

\(\displaystyle x_n = x_{n-1}+x_{n-2} +1. \)

\(\displaystyle x_n\) első pár értékének (\(\displaystyle x_1=1; x_2=2;x_3=4;x_4=7;x_5=12;...\)) felírása után észrevehető, hogy \(\displaystyle x_n=f_{n+2}-1\) (ahol \(\displaystyle f_n\) az \(\displaystyle f_1=f_2=1; f_{n+2}=f_n+f_{n+1} \:(\text{ha }n>0)\) rekurzióval definiált Fibonacci-sorozat). Ezt teljes-indukcióval bizonyítjuk.
Áll.: \(\displaystyle x_n=f_{n+2}-1.\)

(1) (Bázis állítás) \(\displaystyle 1=x_1=f_3-1 =2-1 \quad \surd\).

(2) (Indukciós feltevés) Tegyük fel, hogy adott \(\displaystyle n=k\)-ra igaz az állítás, azaz \(\displaystyle x_k=f_{k+2}-1.\)

(3) Igaz-e \(\displaystyle n=(k+1)\)-re is?
\(\displaystyle x_{k+1}=x_k + x_{k-1} +1 =( f_{k+2}-1)+(f_{k+1}-1)+1=f_{k+3}-1\) (a Fibonacci-sorozat rekurzív definíciója alapján) és éppen ezt akartuk bizonyítani.

Innentől azt kell vizsgálnunk, hogy 2020 melyik két szomszédos Fibonacci-szám közé esik.
Mivel \(\displaystyle f_{17}=1597\) és \(\displaystyle f_{18}=2584\), \(\displaystyle x_{15}=1596<2020<x_{16}=2583\), tehát a válasz: \(\displaystyle \boxed{\: 16\cdot10\mathrm{~Ft} \:}\) az a legkisebb összeg, amennyiért Második biztosan ki tudja találni Kezdő számát.
A megoldásból kiolvasható az ,,optimális kérdezési stratégia'' is.

0) Ha Kezdőnek egyetlen lehetséges száma van, akkor arra rákérdezünk.

A) Ha Kezdő lehetséges számai valamely lehetséges legkisebb \(\displaystyle a+1\) kezdőszámmal az \(\displaystyle a+1,a+2,...,a+k\) (ahol \(\displaystyle 1<k\), és \(\displaystyle f_n < k \leq f_{n+1}\)), akkor elsőre a legnagyobb \(\displaystyle k\)-tól kisebb Fibonacci-szám és \(\displaystyle a\) összegét, azaz \(\displaystyle a+f_n\)-t kérdezzük meg;

– A1) ,,Kisebb'' válasz esetén (ha még legalább két lehetséges gondolt szám van) az A) pont szerint járunk el az \(\displaystyle a'=a\) és \(\displaystyle k'=f_n-1\) választással, azaz a lehetséges \(\displaystyle a+1,a+2,...,a+f_n-1\) számokkal folytatva; míg

– A2) ,,Nagyobb'' válasz esetén (ha még legalább két lehetséges gondolt szám van) az A) pont szerint járunk el az \(\displaystyle a'=a+f_{n}\) és \(\displaystyle k'=k-f_n\) választással, azaz a lehetséges \(\displaystyle a+f_n+1,a+f_n+2,...,a+k\) számokkal folytatva.

Statistics:

62 students sent a solution.
5 points:	Czett Mátyás, Fekete Richárd, Fleiner Zsigmond, Fülöp Csilla, Füredi Erik Benjámin, Jánosik Máté, Kercsó-Molnár Anita, Király Csaba Regő, Kovács 129 Tamás, Móricz Benjámin, Nagy 551 Levente, Németh Márton, Seres-Szabó Márton, Sztranyák Gabriella, Szűcs 064 Tamás, Terjék András József, Vámosi Boglár Tünde, Velich Nóra, Zempléni Lilla.
4 points:	Andó Viola, Argay Zsolt, Baski Bence, Beke Csongor, Bognár 171 András Károly, Farkas 512 Izabella, Gábriel Tamás, Hámori Janka, Hervay Bence, Kerekes Boldizsár, Lengyel Ádám, Lovas Márton, Mácsai Dániel, Mezey Dorottya, Nádor Benedek, Nagy 429 Leila, Nyárfádi Patrik, Páhán Anita Dalma, Sándor Péter, Szabó 991 Kornél, Szakács Ábel, Tóth 057 Bálint, Török Mátyás, Wiener Anna.
3 points:	3 students.
2 points:	2 students.
1 point:	3 students.
0 point:	11 students.

Problems in Mathematics of KöMaL, April 2020