1

Here is a maths trick:

Bob, a magician ask his partner, Peter to leave the room. Then the audience tells Bob two numbers: $n$, which indicates a sign (and let’s consider that the possible signs are the positive integers from 1 to $k$), and $x$, a random positive integer. Then Peter comes in, and Bob tells exactly one number from the numbers

a) $x,x+1,x+2$, and $k=3$

b) $x,x+18,x+51, x+101$, and $k=4$

c) $x,2x,3x$, and $k=3$

d) $x+a, x+b, x+c$, and $k=3$ where $a,b,c$ are different, fixed positive integers

e) $x,2x,3x,\dots,yx$, and $k=y$

to Peter, and Peter knows the sign only from the number he heard.

For a) I have an example strategy. Note that for any $x$, Bob can say a number which is divisible by 3, so as he can always say a number, which makes 1 remainder $\pmod 3$, and he can also say a number, which makes 2 remainder $\pmod 3$. So if Bob wants to transfer sign 1, or the number 1, he says a number to Peter, which makes 1 remainder.

For b) a similar strategy works, just change $\pmod 3$ to $\pmod 4$.

Note that for c) this strategy doesn't work. Let $N=p-q$, where $x=2^p\times 3^q\times r$ ($2\not \mid r$, $3\not \mid r$). Also let $N\equiv M \pmod 3$. If Bob says $x$, then $M$ doesn't change. If Bob says $2x$, then $M$ increases by 1, and if says $3x$, then $M$ decrases by 1. So the three signs are the remainders of $M$ $\pmod 3$.

For d) my question is that how to deside if for a number triple $(a,b,c)$ it is possible to transfer three signs (for example for $(1,2,4)$ I don’t think it is possible, but how can I prove it??). For e) I have two question. First, is it true that for any positive integer $y$, Peter can find out the sign? Second, if $y=\infty$ (so Bob can say any multiple of $x$) then Peter can find out infinite many sign (Bob can transfer infinite many signs)?

Thanks in advance!

Pet123
  • 1,252

1 Answers1

1

Part (d): In general, NO

Wlog. $a<b<c$. Let Let $d=a+c-2b$.. If $d=0$, i.e., $b-a=c-b$, we can influence $\lfloor y/m\rfloor \bmod 3$ the same way we could influence $y\bmod 3$ in the solution to part (a). So assume from now on that $d\ne 0$.

Our magicians need to agree on a map $f\colon \Bbb N\to \{1,2,3\}$ such that for each $x\in\Bbb N$, the values $f(x+a)$, $f(x+b)$, $f(x+c)$ are different. Thus for all $y\gg 0$, we need $f(y)\ne f(y-b+a)$, $f(y)\ne f(y-c+a)$, and $f(y)\ne f(y-c+b)$. This means that two of the values $f(y-b+a)$, $f(y-c+a)$, and $f(y-c+b)$ must be equal.

  • If $f(y-b+a)=f(y-c+a)$ then $f(x+c)=f(x+b)$ for $x=y+a-b-c$, contradiction for $y\gg 0$.
  • If $f(y-c+a)=f(y-c+b)$ then $f(x+b)f(x+a)$ for $x=y-c$, contradiction for $y\gg 0$.

We conclude that $f(y-b+a)=f(y-c+b)$ for all $y\gg 0$. Consequently, $f(y)$ depends only on $y\bmod d$ for $y\gg 0$. In particular, if $0<|d|<3$, then no $f$ with the required properties exists.

I suspect that $3\mid d$ is a necessary and sufficient condition for a strategy function $f$ to exist.

Hagen von Eitzen
  • 374,180