Problem A. 860. (October 2023)

A. 860. A 0\(\displaystyle \,\)–\(\displaystyle \,\)1 sequence of length \(\displaystyle 2^k\) is given. Alice can pick a member from the sequence, and reveal it (its place and its value) to Bob. Find the largest number \(\displaystyle s\) for which Bob can always pick \(\displaystyle s\) members of the sequence, and guess all their values correctly.

Alice and Bob can discuss a strategy before the game with the aim of maximizing the number of correct guesses of Bob. The only information Bob has is the length of the sequence and the member of the sequence picked by Alice.

Submitted by Gábor Szűcs, Szikszó

(7 pont)

Deadline expired on November 10, 2023.

We call \(\displaystyle 0-1\) sequences bit sequences, and the elements of the sequence bits. Let \(\displaystyle x\) be a bit sequence of length \(\displaystyle 2^k\), and let \(\displaystyle \sigma(x)\) denote the number formed by the last \(\displaystyle k\) digits. Let \(\displaystyle E\) be the set of \(\displaystyle k\)-length bit sequences in which exactly one bit value is one. Let \(\displaystyle H\) be the complement of the set \(\displaystyle E\). Since \(\displaystyle |H|=2^k-k\), there is a bijection between \(\displaystyle H\) and \(\displaystyle \{1, 2, \ldots, 2^k-k\}\), denoted as \(\displaystyle g:H\rightarrow \{1, 2, \ldots, 2^k-k\}\).

We will use the following strategy when we receive a bit sequence \(\displaystyle x\).

• a. If \(\displaystyle \sigma(x)\in H\), then Alice reveals the value of the \(\displaystyle g(\sigma(x))\)-th digit.
• b1. If \(\displaystyle \sigma(x)\in E\) and the first digit is \(\displaystyle 1\), then Alice reveals the \(\displaystyle 1\)-digit of \(\displaystyle \sigma(x)\).
• b2. If \(\displaystyle \sigma(x)\in E\) and the first digit is \(\displaystyle 0\), then Alice reveals the \(\displaystyle 0\)-digit following the \(\displaystyle 1\)-digit of \(\displaystyle \sigma(x)\). (If the last digit of \(\displaystyle \sigma(x)\) is \(\displaystyle 1\), then we tell the first digit of \(\displaystyle \sigma(x)\).)

Why is this strategy good?

• a. If Bob gets any of the first \(\displaystyle 2^k-k\) digits, then Bob knows we are in case a). Thus, Bob can determine \(\displaystyle \sigma(x)\), and Bob will also know the revealed digit from the front. That is, in this case, Bob knows \(\displaystyle k+1\) digits.
• b. If the revealed digit is among the last \(\displaystyle k\) digits, then Bob knows that the first digit of the bit sequence matches the value of the revealed digit, and knows that \(\displaystyle \sigma(x)\) contains exactly one bit 1, and where that bit is. Thus, Bob know \(\displaystyle k+1\) bits in this case too.

Now consider why it's impossible to send more than \(\displaystyle k+1\) bits. Let's assume indirectly that Bob can always determine \(\displaystyle k+2\) digits. Bob can receive \(\displaystyle 2^{k+1}\) different messages, since the received bit can have \(\displaystyle 2^k\) locations, and it can have \(\displaystyle 2\) possible values, let this set of (location, value) pairs be \(\displaystyle A\). For each such information, Bob can tell the value of \(\displaystyle k+2\) bits. Let for every \(\displaystyle a \in A\), \(\displaystyle S_a\) be the set of \(\displaystyle 2^k\) long bit sequences whose \(\displaystyle k+2\) digits, which Bob guesses for \(\displaystyle a\), match the values guessed by Bob. Clearly, \(\displaystyle |S_a| \leq 2^{2^k-(k+2)}\). Furthermore, for any \(\displaystyle x\) bit sequence of length \(\displaystyle 2^k\), Alice sends a message \(\displaystyle a \in A\) for which Bob correctly gives \(\displaystyle k+2\) digits of the sequence, i.e., \(\displaystyle x \in S_a\). Therefore, \(\displaystyle \bigcup_{a \in A} S_a\) is precisely all \(\displaystyle 2^k\) long bit sequences. However,

\(\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},\)

which is a contradiction.

Statistics:

32 students sent a solution.
7 points:	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 points:	Baran Júlia, Horák Zsófia, Szabó 810 Levente.
4 points:	2 students.
3 points:	1 student.
2 points:	3 students.
1 point:	3 students.
0 point:	9 students.

Problems in Mathematics of KöMaL, October 2023