A B. 5098. feladat (2020. április)

B. 5098. Kezdő és Második a következő játékot játsszák:

Kezdő gondol egy 2020-nál nem nagyobb pozitív egészre, amit Második úgy szeretne kitalálni, hogy mindig egy konkrét számra kérdez rá.

Kezdő lehetséges válaszai Második kérdéseire: ,,Kisebb számra gondoltam.''; ,,Eltaláltad.''; ,,Nagyobb számra gondoltam.''

Ha a válasz ,,Kisebb számra gondoltam'', vagy ,,Eltaláltad'', akkor Második 10 forintot fizet Kezdőnek, míg abban az esetben, ha a válasz ,,Nagyobb számra gondoltam'', akkor 20 forintot fizet.

Mennyi az a legkisebb összeg, amennyiért Második biztosan ki tudja találni Kezdő számát és hogyan kell ehhez játszania?

(A játék az első ,,Eltaláltad'' válaszig tart, akkor is, ha a legutolsó kérdés előtt Második már tudja mi a gondolt szám.)

(5 pont)

A beküldési határidő 2020. május 11-én LEJÁRT.

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.

Statisztika:

62 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	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 pontot kapott:	3 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	11 versenyző.

A KöMaL 2020. áprilisi matematika feladatai