Az A. 860. feladat (2023. október)

A. 860. Adott egy \(\displaystyle 2^k\) darab tagból álló 0\(\displaystyle \,\)–\(\displaystyle \,\)1 sorozat. Alíz megkapja ezt a sorozatot, majd elárulhatja a sorozat egyik tagját (a tag helyét és értékét) Bobnak. Határozzuk meg azt a legnagyobb \(\displaystyle s\) számot, melyre Bob biztosan tud választani \(\displaystyle s\) darab tagot a sorozatból, és mindegyiknek meg tudja állapítani helyesen az értékét, akármilyen sorozatot is kapott Alíz.

Alíz és Bob a játék előtt összebeszélhetnek azzal a céllal, hogy Bob minél több jegyet biztosan meg tudjon mondani a sorozatból. Bob semmi más információt nem tud a 0\(\displaystyle \,\)–\(\displaystyle \,\)1 sorozatról a hosszán és az Alíz által választott tagon kívül.

Javasolta: Szűcs Gábor (Szikszó)

(7 pont)

A beküldési határidő 2023. november 10-én LEJÁRT.

A \(\displaystyle 0-1\) sorozatokat bitsorozatnak hívjuk, a sorozat tagjait biteknek. Legyen \(\displaystyle x\) egy \(\displaystyle 2^k\) hosszú bitsorozat, jelölje \(\displaystyle \sigma(x)\) az utolsó \(\displaystyle k\) jegye által alkotott számot. Legyen \(\displaystyle E\) az olyan \(\displaystyle k\) hosszú bitsorozatok halmaza, amelyekben pontosan egy bit értéke egyes. Legyen \(\displaystyle H\) az \(\displaystyle E\) halmaz komplementere. Mivel \(\displaystyle |H|=2^k-k\), ezért van bijekció \(\displaystyle H\) és \(\displaystyle \{1, 2, \ldots, 2^k-k\}\) között, jelölje ezt \(\displaystyle g:H\rightarrow \{1, 2, ..., 2^k-k\}\).

A következő stratégiát fogjuk alkalmazni, ha egy \(\displaystyle x\) bitsorozatot kapunk.

• a. Ha \(\displaystyle \sigma(x)\in H\), akkor Alíz a \(\displaystyle g(\sigma(x))\)-edik számjegy értékét árulja el.
• b1. Ha \(\displaystyle \sigma(x)\in E\) és \(\displaystyle x\) első számjegye \(\displaystyle 1\), akkor Alíz megmondja \(\displaystyle \sigma(x)\) \(\displaystyle 1\)-es jegyét.
• b2. Ha \(\displaystyle \sigma(x)\in E\) és \(\displaystyle x\) első számjegye \(\displaystyle 0\), akkor Alíz megmondja \(\displaystyle \sigma(x)\) \(\displaystyle 1\)-es utáni \(\displaystyle 0\)-as jegyét. (Ha \(\displaystyle \sigma(x)\) utolsó jegye \(\displaystyle 1\), akkor \(\displaystyle \sigma(x)\) első jegyét mondja meg.)

Miért jó ez a stratégia?

• a. Ha az első \(\displaystyle 2^k-k\) jegy valamelyikét hallja Bob, akkor tudja, hogy az a) eset forog fenn. Így meghatározhatja \(\displaystyle \sigma(x)\)-et, és ismerni fogja a felfedett jegyet elölről is. Vagyis ebben az esetben \(\displaystyle k+1\) jegyet ismer Bob.
• b. Ha az elárult számjegy az utolsó \(\displaystyle k\) jegy között szerepel, akkor Bob tudja, hogy a bitsorozat első jegye megegyezik az elárult jegy értékével, és tudja, hogy \(\displaystyle \sigma(x)\) pontosan egy \(\displaystyle 1\)-est tartalmaz, és hogy hol van ez az \(\displaystyle 1\)-es. Azaz így is \(\displaystyle k+1\) bit értékét ismeri Bob.

Most gondoljuk meg, hogy \(\displaystyle k+1\)-nél több bitet nem lehet elküldeni. Indirekten tegyük fel, hogy Bob mindig meg tud határozni \(\displaystyle k+2\) jegyet. Bob \(\displaystyle 2^{k+1}\)-féle üzenetet kaphat, mivel a kapott bit helye \(\displaystyle 2^k\)-féle, értéke \(\displaystyle 2\)-féle lehet, legyen ezen (hely, érték) párok halmaza \(\displaystyle A\). Minden ilyen információra, Bob meg tudja mondani \(\displaystyle k+2\) bit értékét. Legyen minden \(\displaystyle a \in A\) esetén \(\displaystyle S_a\) azon \(\displaystyle 2^k\) hosszú bitsorozatok halmaza, melyeknek azon \(\displaystyle k+2\) jegye amit Bob tippel \(\displaystyle a\) esetén egyezik a Bob által tippelt értékekkel. Világos, hogy \(\displaystyle |S_a| \leq 2^{2^k-(k+2)}\). Továbbá tetszőleges \(\displaystyle x\) \(\displaystyle 2^k\) hosszú bitsorozat esetén Alíz küld egy \(\displaystyle a \in A\) üzenetet melyre Bob helyesen megad \(\displaystyle k+2\) jegyet a sorozatból, azaz \(\displaystyle x \in S_a\). Emiatt \(\displaystyle \bigcup_{a \in A} S_a\) éppen az összes \(\displaystyle 2^{2^k}\) darab \(\displaystyle 2^k\) hosszú bitsorozat. Ám

\(\displaystyle \left|\bigcup_{a \in A} S_a \right| \leq \sum_{a \in A} |S_a| \leq 2^{k+1} \cdot 2^{2^k-(k+2)}<2^{2^k},\)

ami ellentmondás.

Statisztika:

32 dolgozat érkezett.
7 pontot kapott:	Czanik Pál, Duchon Márton, Fekete Aron, Fórizs Emma, Hodossy Réka, Nguyen Kim Dorka, Simon László Bence, Szakács Ábel, Tarján Bernát, Varga Boldizsár, Wiener Anna.
6 pontot kapott:	Baran Júlia, Horák Zsófia, Szabó 810 Levente.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	9 versenyző.

A KöMaL 2023. októberi matematika feladatai