Problem B. 5492. (November 2025)
B. 5492. Kornél thinks about a closed subinterval of \(\displaystyle I=[0, 2^k]\) (where \(\displaystyle k\) is a positive integer) with integer endpoints and length at least \(\displaystyle 1\). Kristóf can ask the following question: he can choose an arbitrary closed subinterval with integer length, but not necessarily integer endpoints, and Kornél tells him the length of the intersection of the interval he picked and the interval chosen by Kristóf. (The answer is \(\displaystyle 0\) if the intersection of the two intervals is empty or consists of a single point.) Find the smallest number of questions with which Kristóf can guess the interval chosen by Kornél in all cases.
Proposed by Dávid Matolcsi, Berkeley/Brussels
(6 pont)
Deadline expired on December 10, 2025.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
41 students sent a solution. 6 points: Holló Martin, Takács András, Tóth László Pál. 5 points: Sarusi-Kis Balázs, Tóth Luca, Vályi Nagy Ádám András, Wiener Marcell. 4 points: 6 students. 3 points: 10 students. 2 points: 10 students. 1 point: 3 students. 0 point: 3 students. Unfair, not evaluated: 1 solutions.
Problems in Mathematics of KöMaL, November 2025