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. 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:

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


A KöMaL 2020. áprilisi matematika feladatai