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