1
$\begingroup$

Two players guess code that is hidden in $2^n$ ($n\geq2$, n $\in$ $\Bbb N$) digits that each contain either 0 or 1 which makes a binary code that consists of zeros and/or ones, for example, '0010' is binary code, that has $2^2$ digits that consist only of 0's and 1's.

There are two players - first player and second player. The first player starts and guesses the digit. The second player only knows if the digit that was chosen by the first player contains 0 or 1 but the second player do not know which digit the first player chose. There are two rules that have to be followed:

A) If a player chooses digit and guesses right, he can choose three consecutive digits that contain one of the digits that he guessed this turn and send to other player those three consecutive digits as partial information.

B) If a player chooses digit and guesses wrong, he can choose two consecutive digits that contain one of the digits that he guessed this turn and send to other player those two consecutive digits as partial information.

After first player followed rules A and B, it is second player's turn and he does the same: guesses the digit, sends partial information by the rules A and B, but the difference is that the second player becomes the one that is sending information and the first player is the one who is receiving it. Then it is first player's turn again, then the second player's turn and so on until one of the players can tell whole code containing of $2^n$ digits of zeros or ones, but the player is considered to know the code when he knows all the digits for sure.

It seems to me that if we could find out strategy for trivial n=2 or n=3 we could just use the mathematical induction and prove that strategy works for all natural numbers n. Also, for clarification, by default first and last digit is not connected (the digits are not in a closed circle) - it would make the strategy more difficult or even impossible to find.

I probably should make myself more clear about the task.

Let us say we have 4 digits and the exact code is '0100'.

(I) First player guesses that 2nd digit is '1'. Public info: the first player guessed right about the '1'. Private info for first player: 2nd digit is '1'. Public info: either 1st, 2nd or 3rd is the digit containing '1' (first player guessed right so he chose 3 consecutive digits this way).

(II) Second player guesses that 1st digit is '1'. Public info: the second player guessed wrong about the '1'. Private info for second player: 1st digit is '0'. Public info: either 1st or 2nd is the digit containing '0' (it is forced to reveal this info because 1st digit is only near the 2nd)

(I) Since first player knew that 2nd is '1', so he already knows that 1st is '0' from the public info. First player guesses that 4th digit is '0'. Public info: the first player guessed right about the '0'. Private info for first player: 4th digit is '0'. Public info: either 2nd, 3rd or 4th is the digit containing '0'.

(II) Second player knows that 1st one is '0', either 2nd or 3rd is '1', either 2nd, 3rd or 4th is '0'. Basically, second player knows almost nothing. Public info: the second player guessed wrong about the '1'. Private info for second player: 3rd digit is '0'. Public info: either 2nd or 3rd is the digit containing '0'.

(I) Since the first player knew that 2nd digit contains '1', he knows then that 3rd contains '0'. But he figures out the code that is '0100' and the first player wins.

Now, talking about the quantity of digits. $2^n$ is the reason because of forward-backward induction idea that involves such numbers because we have to first assume that from every natural number n it follows for $2^n$ is true and then we have to prove that if for all n is true then for all n-1 is also true. It also is related to binary codes, so why not stick to $2^n$.

$\endgroup$
3
  • 4
    $\begingroup$ This is somewhat unclear. When players "guess a node" or "send a node", are they guessing/sending the node index or the value of the bit(s)? Examples would help. $\endgroup$
    – Karl
    Commented Dec 23, 2022 at 12:36
  • $\begingroup$ I second the comment of @Karl. This seems like a very interesting problem to work on. However, I request that you provide several clear examples, to illustrate fully what you have in mind. I suggest that you have one example with $2^1$ nodes, one example with $2^2$ nodes, and one example with $2^3$ nodes. There is a separate question. If I read the posting correctly, there seems to be the constraint that the number of nodes must be some element in $\{2,4,8,16,32, \cdots\}.$ Why? Why is it necessary to disallow having (for example) $3$ nodes, or $6$ nodes? $\endgroup$ Commented Dec 23, 2022 at 13:28
  • $\begingroup$ Good evening, I tried to explain myself by editing the task. $\endgroup$ Commented Dec 23, 2022 at 21:08

1 Answer 1

0
$\begingroup$

This is not an answer but an attempt to rewrite the task/rules in a simpler form. I think there are some translation issues. OP, if you agree this is useful, please feel free to copy/paste, and I'll delete later.


The rules are thus: Two players are attempting to discover a binary code of $2^n$ bits, unknown to either. Each turn, one player is active and the other is passive. A turn plays as follows:

  1. The active player chooses a bit, and guesses whether it is $0$ or $1$. The game system tells the active player whether their guess is correct or not.
  2. The active player then chooses several consecutive bits containing the guessed bit: they choose three if they guessed correctly, two otherwise.
  3. The game system then tells the passive player the true value of the guessed bit and the two or three bits selected by the active player.
  4. This ends the turn: the active player becomes passive and vice versa.

The end result of a turn, in terms of revealed information, is that the active player learns the true value of one bit, and the passive player learns that one of two (or three) consecutive bits has that value. The game ends when one player can determine the code correctly; that player wins.

As an example: the hidden code is $0100$. We will call the players X and Y, and label the bits $ABCD$.

  • Turn $1$X: X guesses that bit $B$ is $1$, and is told this is correct. X chooses to reveal that one of the bits $A,B,C$ is $1$.
  • Turn $1$Y: Y guesses that bit $A$ is $1$, and is told this is incorrect. Y has no choice but to reveal that one of the bits $A,B$ is $0$.
  • X now knows the code is $01CD$. Y knows the code is $0BCD$, where either $B$ or $C$ is $1$.
  • Turn $2$X: X guesses that bit $D$ is a $0$, and is told this is correct. X has no choice but to reveal that one of the bits $B,C,D$ is $0$.
  • Turn $2$Y: Y, lacking information, guesses that bit $C$ is a $1$, and is told this is incorrect. Y chooses to reveal that one of the bits $B,C$ is $0$.
  • Y now knows that the code is $010D$. But X now knows the entire code, and wins.

The question is: How can one develop a strategy for this game, for larger $n$?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .