5
$\begingroup$

The problem:

Two friends have $2$ natural written on their forehead. One of them is $2$ times the other + $1$. Let's call them $X$ and $2X + 1$. They have to come up with a strategy to guess their own number, and they can raise their hand or not (communicate $1$ bit of information to each other).

So for example if you see $23$ on your friends forehead, you have to decide by only communicating $1$ bit of information whether or not you have $11$ or $47$ on your forehead.

Do I have 11 or 47 on my forehead?

My attempt:

(Let's call the number each player sees on their friend's forehead $S$.)

Step $1$. If the number you see is even, immediately say "$2S+1$ is on my forehead!"

(Obviously $2X+1$ cannot be even, so we're good so far.)

Step $2$. If the number you see is of the form $4n+1$, say "$2S + 1$ is on my forehead!"

(This works too, since if $2X+1=4n+1 \ \rightarrow\ X=2n$, which was already covered in Step $1$. This means that the seen $S = 4n+1 \ne 2X+1$, instead $S = 4n+1=X$, so we our number must be $2X+1$.)

This is where it becomes problamatic, since:

  • If $X=4n+3 \ \rightarrow\ 2X+1=8n+7 \stackrel{also}{=} 4\hat{n}+3 \quad (\hat{n} = 2n+1)$
  • Not only that, but if $X=8n+7 \ \rightarrow\ 2X+1=16n+15 \stackrel{also}{=} 8\hat{n}+7 \quad (\hat{n} = 2n+1)$

I have also tried divisibility by $3$, $5$ and $6$, but none of those lead to a solution, for example:

  • If $X=3n \ \rightarrow\ 2X+1 \equiv 1 \ (\text{mod}\ 3)$ and $X=3n+1 \ \rightarrow\ 2X+1 \equiv 0 \ (\text{mod}\ 3)$, which is all good, if $S=3n$ or $S=3n+1$, you can determine what your number is, ...
  • But if $X=3n+2 \ \rightarrow\ 2X+1=6n+5=3\hat{n}+2 \quad (\hat{n} = 2n+1)$, so raising their hand when $S=3n+2$ doesn't work either.

I don't think I'm far from the solution, but i just can't figure it out, so any help would be appreciated!

$\endgroup$
8
$\begingroup$

The function $X\mapsto 2X+1$ partitions the positive integers into chains, as below. Each chain begins with either an even number, or one, and every number $X$ is joined by an arrow to $2X+1$. It is common knowledge to the two players which chain they are in. Furthermore, all the chains have the same structure. Therefore, we will assume without loss of generality the players are in the indicated chain.

\begin{align} &\boxed{1\to 3\to 7\to 15\to 31\to \dots} \\ &2\to 5\to 11\to 23\to47\to \dots \\ &4\to 9\to 19\to 39 \to 79\to \dots \\ &6\to 13\to 27\to 55\to 111\to \dots \\ &8\to 17\to 35\to 71\to 142\to \dots \\ &\hspace{3cm}\vdots \end{align} Color the elements of the chain alternately black and red in blocks of two, as shown. Each player communicates the color they see to the other player using their hand raise. This allows each player to deduce their number. For example, if you had $15$ and your friend had $31$, then you would be unsure whether your number was $15$ or $63$. But once your friend says that your number is red, you know your number is $15$. $$ 1\to 3\to \color{red}{7}\to \color{red}{15}\to 31\to 63\to \color{red}{127}\to \color{red}{255}\to 511\to \dots $$ The color can be described explicitly. The reverse function of $X\mapsto 2X+1$ is $X\mapsto (X-1)/2$, which is defined as long as $X$ is odd and greater than $1$. If you apply the reverse map over and over to the number you see, then you will eventually end up with an even number (or one). If it takes $n$ steps to do this, then you should raise your hand if $\lfloor n/2\rfloor$ is even.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.