 |
A B. 5492. feladat (2025. november) |
B. 5492. Kornél az \(\displaystyle I=[0,2^k]\) intervallumnak (ahol \(\displaystyle k\) pozitív egész) egy egész kezdő- és végpontú, legalább \(\displaystyle 1\) hosszúságú, zárt részintervallumára gondol. Kristóf kérdezhet egy tetszőleges egész hosszúságú, de nem feltétlenül egész kezdő- és végpontú, zárt részintervallumot, és Kornél elárulja a kérdezett és a gondolt intervallum metszetének a hosszát. (A válasz \(\displaystyle 0\), ha a két intervallum metszete üres, és akkor is, ha csak egyetlen pontból áll.) Hány kérdésből tudja Kristóf biztosan meghatározni a gondolt intervallumot?
Javasolta: Matolcsi Dávid (Berkeley/Brüsszel)
(6 pont)
A beküldési határidő 2025. december 10-én LEJÁRT.
Megoldás. A kitalálandó intervallumot jelölje \(\displaystyle J\), míg a Kristóf által az \(\displaystyle i\)-dik lépésben megkérdezett intervallumot \(\displaystyle K_i\), a \(\displaystyle K_i\) intervallum hosszát pedig \(\displaystyle |K_i|\). A feladat során \(\displaystyle x\) szám egész részét (hogy ne legyen az intervallum jelével összekeverhető) az \(\displaystyle \lfloor x \rfloor\) alakban fogjuk megadni, míg \(\displaystyle x\) szám tört részét \(\displaystyle \lbrace x \rbrace\) jelöli. Továbbá jelentse a feladat során (a könnyebb leírhatóság kedvéért) \(\displaystyle c\) az \(\displaystyle \frac{1}{10}\) törtet (hamarosan nyilvánvaló lesz, hogy \(\displaystyle c\)-nek – az \(\displaystyle \frac{1}{2}\) kivételével – bármilyen \(\displaystyle 0\) és \(\displaystyle 1\) közötti valós szám megfelelő). Kristóf \(\displaystyle K_i\) kérdését \(\displaystyle K_i=[a_i+c;b_i+c]\) formában fogja majd feltenni (ahol \(\displaystyle a_i, b_i\) egész számok). Nyilván adott \(\displaystyle k\) esetén \(\displaystyle 0\)-hosszú, vagy a teljes \(\displaystyle 2^k\)-hosszú \(\displaystyle I\)-intervallumra nincs értelme rákérdezni.
Jó kérdezési stratégia megadása \(\displaystyle k\) kis értékeire.
– Ha \(\displaystyle k=1\), akkor a \(\displaystyle K_1=[0+c;1+c]\) kérdésre \(\displaystyle J=[0;1]\) esetén \(\displaystyle c\), \(\displaystyle J=[1;2]\) esetén \(\displaystyle 1-c(\neq c)\), míg \(\displaystyle J=[0;2]\) esetén \(\displaystyle 1\) a válasz, így egyetlen kérdés elegendő (és nyilván egy kérdés kell is).
– Ha \(\displaystyle k=2\), akkor ha az elsőként kérdezett intervallum hossza \(\displaystyle |K_1|=3\), akkor az ,,1'' válasz esetén legalább két lehetőség van \(\displaystyle J\)-re, ha \(\displaystyle |K_1|=1\), akkor az ,,0'' válasz esetén van legalább két lehetőség \(\displaystyle J\)-re, végül ha a \(\displaystyle |K_1|=2\) és \(\displaystyle K_1=[x;2+x]\), akkor bárhogyan is kérdezett Kristóf, vagy \(\displaystyle x\geq 1\) és ekkor az \(\displaystyle 1-\lbrace x \rbrace\) válasz esetén van legalább két lehetőség \(\displaystyle J\)-re (\(\displaystyle J_1=[\lfloor x \rfloor ; \lfloor x +1\rfloor]\) és \(\displaystyle J_2=[\lfloor x-1 \rfloor ; \lfloor x +1\rfloor]\)), vagy pedig \(\displaystyle x+2\leq 3\) és ekkor az \(\displaystyle \lbrace x \rbrace\) válasz esetén van legalább két lehetőség \(\displaystyle J\)-re (\(\displaystyle J_1=[\lfloor x+1 \rfloor ; \lfloor x +2\rfloor]\) és \(\displaystyle J_1=[\lfloor x+1 \rfloor ; \lfloor x +3\rfloor]\)), azaz legalább két kérdés kell. Két kérdés viszont elegendő is \(\displaystyle k=2\) esetén, ennek igazolásához azt mutatjuk meg, hogy \(\displaystyle k=3\) esetén is ki lehet találni két kérdésből a választ.
– Azaz legyen \(\displaystyle k=3\) és \(\displaystyle I=[0;8]\), az első kérdés pedig \(\displaystyle K_1=[0+c;4+c]\). Ekkor a lehetséges válaszok és a hozzájuk tartozó lehetséges \(\displaystyle J\) megoldások:
Ha a válasz ,,0'' \(\displaystyle \Rightarrow J_1=[5;6], J_2=[5;7], J_3=[5;8], J_4=[6;7], J_5=[6;8]\) és \(\displaystyle J_6=[7;8]\). Az újabb \(\displaystyle K_2=[5+c;7+c]\) kérdésre az egyes válaszok – az alábbi táblázat alapján – láthatóan mind különböznek, így elég a két kérdés.
| lehetséges \(\displaystyle J\) megoldás | \(\displaystyle J_1=[5;6]\) | \(\displaystyle J_2=[5;7]\) | \(\displaystyle J_3=[5;8]\) | \(\displaystyle J_4=[6;7]\) | \(\displaystyle J_5=[6;8]\) | \(\displaystyle J_6=[7;8]\) |
| válasz a \(\displaystyle K_2=[5+c;7+c]\) kérdésre | \(\displaystyle 1-c\) | \(\displaystyle 2-c\) | \(\displaystyle 2\) | \(\displaystyle 1\) | \(\displaystyle 1+c\) | \(\displaystyle c\) |
Ha a válasz ,,1'' \(\displaystyle \Rightarrow J_1=[1;2], J_2=[2;3]\) és \(\displaystyle J_3=[3;4]\). Az újabb \(\displaystyle K_2=[2+c;3+c]\) kérdésre adott válaszok (lásd a továbbiakban is a megfelelő táblázatot) alapján itt is elég két kérdés.
| lehetséges \(\displaystyle J\) megoldás | \(\displaystyle J_1=[1;2]\) | \(\displaystyle J_2=[2;3]\) | \(\displaystyle J_3=[3;4]\) |
| válasz a \(\displaystyle K_2=[2+c;3+c]\) kérdésre | \(\displaystyle 0\) | \(\displaystyle 1-c\) | \(\displaystyle c\) |
Ha a válasz ,,2'' \(\displaystyle \Rightarrow J_1=[1;3]; J_2=[2;4]\). Az újabb \(\displaystyle K_2=[2+c;3+c]\) kérdésre az egyes válaszok rendre: \(\displaystyle 1-c\), és \(\displaystyle 1\), itt is elég két kérdés.
Ha a válasz ,,3'' \(\displaystyle \Rightarrow J=[1;4]\), és nincs szükség újabb kérdésre.
Ha a válasz ,,4'' \(\displaystyle \Rightarrow J_1=[0;5], J_2=[0;6], J_3=[0;7]\) és \(\displaystyle J_4=[0;8]\). Az első esethez hasonlóan az újabb \(\displaystyle K_2=[5+c;7+c]\) kérdésre adott válaszok alapján itt is elég két kérdés.
| lehetséges \(\displaystyle J\) megoldás | \(\displaystyle J_1=[0;5]\) | \(\displaystyle J_2=[0;6]\) | \(\displaystyle J_3=[0;7]\) | \(\displaystyle J_4=[0;8]\) |
| válasz a \(\displaystyle K_2=[5+c;7+c]\) kérdésre | \(\displaystyle 0\) | \(\displaystyle 1-c\) | \(\displaystyle 2-c\) | \(\displaystyle 2\) |
Ha a válasz \(\displaystyle n+c\) (ahol \(\displaystyle 0 \leq n \leq 3\) egész), akkor a lehetséges intervallumok: \(\displaystyle J_1=[4-n;5], J_2=[4-n;6], J_3=[4-n;7]\) és \(\displaystyle J_4=[4-n;8]\). Itt (mivel a bal végpont biztosan \(\displaystyle 4-n\), azaz ismert, a jobb végpont pedig legalább 5) az újabb \(\displaystyle K_2=[5+c;7+c]\) kérdésre adott válaszok alapján megint csak elég két kérdés.
| lehetséges \(\displaystyle J\) megoldás | \(\displaystyle J_1=[4-n;5]\) | \(\displaystyle J_2=[4-n;6]\) | \(\displaystyle J_3=[4-n;7]\) | \(\displaystyle J_4=[4-n;8]\) |
| válasz a \(\displaystyle K_2=[5+c;7+c]\) kérdésre | \(\displaystyle 0\) | \(\displaystyle 1-c\) | \(\displaystyle 2-c\) | \(\displaystyle 3-c\) |
Ha pedig a válasz \(\displaystyle 1-c\), \(\displaystyle 2-c\), \(\displaystyle 3-c\), vagy \(\displaystyle 4-c\), akkor a bal végpont 0, és nincs is szükség további kérdésre, hiszen \(\displaystyle J\) egyértelműen kiderül, és az egyes esetekben rendre: \(\displaystyle [0;1]\), \(\displaystyle [0;2]\), \(\displaystyle [0;3]\), illetve \(\displaystyle [0;4]\).
(Rövid ellenőrzés: \(\displaystyle [0;8]\)-n összesen \(\displaystyle \binom{9}{2}=36\) megfelelő intervallum van, és az egyes válaszok során összesen \(\displaystyle 6+3+2+1+4+4\cdot 4 + 4=36\) intervallumot kaptunk.)
Azaz \(\displaystyle k=3\) (és így \(\displaystyle k=2\)) eset eldönthető \(\displaystyle 2\) kérdéssel (nyilván 1-gyel nem mindig).
Jó kérdezési stratégia – teljes indukcióval történő – megadása \(\displaystyle k\) nagyobb értékeire.
– Legyen a továbbiakban \(\displaystyle k \geq 3\). Teljes indukcióval megmutatjuk, hogy ekkor elegendő \(\displaystyle k-1\) darab kérdés. A \(\displaystyle k=3\) (bázis) esetet az előbb beláttuk, legyen a továbbiakban \(\displaystyle k>3\).
Tegyük fel, hogy ha az \(\displaystyle I=[0;2^{k-1}]\) intervallumon rejti el \(\displaystyle J\)-t Kornél, akkor elegendő a kitalálásához \(\displaystyle k-2 \) darab kérdés (indukciós feltevés).
Ekkor ha \(\displaystyle I'=[0;2^{k}]\) és az első kérdés \(\displaystyle K_1=[0+c;2^{k-1}+c]\), akkor a lehetséges válaszok (innen nagyon hasonlóan dolgozunk, mint \(\displaystyle k=3\) esetén):
– A \(\displaystyle 0<n<2^{k-1}\) egész szám, akkor \(\displaystyle J\) mindkét végpontja az \(\displaystyle [1;2^{k-1}] \left( \subset I=[0;2^{k-1}] \right)\) intervallumban van, és így az indukciós feltevés miatt további \(\displaystyle k-2\) kérdés már elég;
– \(\displaystyle 0\), akkor \(\displaystyle J\) mindkét végpontja a \(\displaystyle [2^{k-1}+1;2^{k}]\) intervallumban van, és mivel ennek hossza \(\displaystyle 2^{k-1}-1\) az indukciós feltevés miatt további \(\displaystyle k-2\) kérdés már elég;
– \(\displaystyle 2^{k-1}\), akkor \(\displaystyle J\) bal oldali végpontja 0, míg a jobb oldali végpont a \(\displaystyle [2^{k-1}+1;2^{k}]\) intervallumban van, és mivel ennek hossza \(\displaystyle 2^{k-1}-1\) az indukciós feltevés miatt további \(\displaystyle k-2\) kérdés elég;
– \(\displaystyle n+c\) (ahol \(\displaystyle 0 \leq n < 2^{k-1}\) egész), akkor \(\displaystyle J\) bal oldali végpontja \(\displaystyle 2^{k-1}-n\) (azaz egyértelműen kiderül), míg a jobb oldali végpont – az előző ponthoz hasonlóan – a \(\displaystyle [2^{k-1}+1;2^{k}]\) intervallumban van, így további \(\displaystyle k-2\) kérdés itt is elég; és végül
– \(\displaystyle n+1-c\) esetén (ahol \(\displaystyle 0 \leq n < 2^{k-1}\) egész) \(\displaystyle J=[0;n+1]\) (azaz \(\displaystyle J\) további kérdés nélkül egyértelműen kiderül).
Ezzel igazoltuk az állítást, \(\displaystyle k\geq 3\) esetén valóban elegendő \(\displaystyle k-1\) kérdés. Hátra van még annak a bizonyítása, hogy \(\displaystyle k\geq 3\) esetén (bizonyos esetben) szükséges is \(\displaystyle k-1\) kérdés.
A kérdezési stratégiánk minimalitásának igazolása.
Tegyük fel, hogy Kornél elárulja, hogy az általa gondolt intervallum 1 hosszúságú, azaz a \(\displaystyle [0,1], [1,2], [2,3], \ldots, [2^k-1,2^k]\) valamelyike.
Tegyük fel továbbá, hogy Kristóf \(\displaystyle i.\) kérdése után még \(\displaystyle \ell_i\) lehetőség él az 1 hosszú intervallumok közül. Ekkor Kristóf bármilyen \(\displaystyle [a+c,b+c]\) kérdése esetén (\(\displaystyle a,b\) egészek és \(\displaystyle 0 \leq c < 1\))
- legfeljebb 1 olyan lehetséges gondolt intervallum van, amelyre \(\displaystyle c\) a válasz (csak az \(\displaystyle [a,a+1]\) intervallum lehet ilyen, ha még korábban nem esett ki a lehetőségek közül);
- legfeljebb 1 olyan lehetséges gondolt intervallum van, amelyre \(\displaystyle 1-c\) a válasz (a \(\displaystyle [b,b+1]\) intervallum jön szóba);
- az összes többi esetben 0 vagy 1 a válasz.
Azaz van legalább \(\displaystyle \frac{\ell_i-2}{2} = \frac{\ell_i}{2}-1\) olyan lehetőség intervallum, amelyre ugyanaz a válasz. Így ha a Kérdezőnek pechje van, akkor az \(\displaystyle i+1\)-edik kérdése után még lehetséges intervallumok száma \(\displaystyle \ell_{i+1} \geq \frac{\ell_i}{2}-1\).
Mivel \(\displaystyle \ell_0 = 2^k \geq 2^k - 1\), így peches kérdések esetén \(\displaystyle \ell_i \geq 2^{k-i}-1\) minden \(\displaystyle 0 \leq i \leq k-1\) egész számra (hiszen \(\displaystyle \frac{2^{k-i}-1}{2}-1 = 2^{k-i-1}-\frac32\), de \(\displaystyle \ell_{i+1}\) csak egész lehet, tehát legalább \(\displaystyle 2^{k-i-1}-1\)). Tehát \(\displaystyle k-2\) kérdés nem lehet elég, mert peches válaszok esetén még legalább \(\displaystyle 2^{k-(k-2)}-1 = 3\) lehetőség jönne szóba.
Összefoglalva: ha \(\displaystyle k<3\), akkor \(\displaystyle k\) kérdéssel tudja, míg \(\displaystyle 3\leq k\) esetén \(\displaystyle k-1\) kérdéssel tudja biztosan megtalálni Kristóf a Kornél által választott intervallumot.
Statisztika:
41 dolgozat érkezett. 6 pontot kapott: Holló Martin, Takács András, Tóth László Pál. 5 pontot kapott: Sarusi-Kis Balázs, Tóth Luca, Vályi Nagy Ádám András, Wiener Marcell. 4 pontot kapott: 6 versenyző. 3 pontot kapott: 10 versenyző. 2 pontot kapott: 10 versenyző. 1 pontot kapott: 3 versenyző. 0 pontot kapott: 3 versenyző. Nem versenyszerű: 1 dolgozat.
A KöMaL 2025. novemberi matematika feladatai