Finni's tricky game

Question

Finni’s game:

Person A thinks of a number (1 to 10). This number is called n.
Person B says a number (1 to 10). This number is called x.
Person A tells the absolute difference of n and x. This difference is called u.
Person B says a new number (1 to 10). This number is called y.
Person A tells the absolute difference of n and y. This difference is called v.

Person B's Goal: u + v shall be as small as possible.
Which strategy should person B follow? Why?

Notes:

1. A "good strategy" is a balance between the lowest average and the best worst-case result. However, I have not yet found a strategy that is good on average but has a bad worst-case score or vice versa, so I there are only strategies that are good in both aspects.

2. Person A selects n randomly.

Answer 1

Assuming that A picks randomly from a uniform distribution, B should pick for $x$:

$8$ or $3$ due to symmetry

and for $y$:

$(8-u)$ or $(3+u)$ respectively

The expected value of $u+v$ is then:

$\frac{1}{10}\sum\limits^{10}_{n=1} (2|n - 8| + (n-8) )= 3.7$
or
$\frac{1}{10}\sum\limits^{10}_{n=1} (2|n - 3| - (n-3) )= 3.7$

Answer 2

This is probably similar to other answers, but I don't think it is expressed quite this way....

EDIT - ok so reading more closely it is the same as Gareth McCaughan's answer, but expressed a little bit differently

B should start with 4 - then if the difference is 0,1,2 or 3 B should repeat 4 and then the total will be either 0,2,4 or 6 and the unknown number was between 1 and 7

looking at the other possibilities

If the first difference is 4,5 or 6 then B knows the unknown number was 8,9 or 10 and so for B's second number B can choose 8, 9 or 10 and then the total of the two differences will be 4,5,6.

Thus the result is

the largest sum of differences is 6

and

the same effect could be had starting with 7

Note that

If B starts with 5 (or 6) then a difference of 4 initially may mean the unknown number is 1 or 9 and so B will be unsure how to minimize the total and will need to stick with 5 and get a total difference of 8

and also note

If the first guess is less than 4 (or more than 7) then the first difference could be greater than 6 and so the total of the differences could be greater than 6.

Thus in conclusion

must start with 4 (or 7)

If there were more guesses then it would be better to start with

3 - if there were 3 guesses. and probably 2 if there were 4 or more guesses.

Answer 3

First, a remark: The question may not have a well-defined answer: is B trying to make u+v as small as possible in the worst case where A gets lucky, or on average in some sense, or what? I'll assume that each player is trying to optimize their worst case.

[EDITED to add:] Some time after I wrote the above, OP edited the question to specify that A chooses at random. If B is trying to minimize u+v in the worst case then actually it doesn't matter whether A is playing at random or trying to thwart B; B has to assume that A might get lucky. So the following applies without modification, as far as finding B's strategy goes, to the case where B is trying to optimize for the worst case and A is playing randomly.

After A announces the number u,

B knows that A's secret number n must be either x+u or x-u. (Perhaps only one of these is possible, e.g. if x=1.) B will then pick y to make max(|y-(x+u)|, |y-(x-u)|) as small as possible. What value of y does this? Always x itself, when both values are actually possible. If not, then B knows the value of n and will pick it.

So, let's suppose B picks x with 1 <= x <= 5. (The other choices are equivalent by symmetry.) Then

if A responds with something =x, in which case B now knows what n is and can hit it on the nose; worst case is where n=10 and the total difference is 10-x.

Now

as we increase x, one of these gets worse and the other gets better. The best worst case will be where they are equal: 2(x-1) = 10-x or x=4. Then the worst possible total difference is 6.

So B should pick

either 4 or 7 (or some random choice between them)

and A should pick

either 1 or 10 (better pick at random, else B can do better!)

after which

the total difference will always be 6.

Answer 4

@GarethMcCaughan gave the answer for when B is trying to minimize the maximum value of u+v, and A is doing the opposite.

I will assume that B is trying to minimize the average (ie. expected) value of u+v and A is trying to maximize that. [EDIT: OP pointed out this was not what we were supposed to assume. Oh well, I'll leave this answer up anyway.]

Then I claim:

A should flip a coin and choose either 1 or 10 for n. B should do likewise for x. u will be either 0 or 9, and then B will know what n is, so picks y=n.

The expected value of u+v is

4.5 (50% chance of u being either 0 or 9, and 100% chance of v being 0).

If A sticks to the strategy, B cannot reduce the expected value of u+v:

If B picks a different x, then the expected value of u does not change: 50% chance it is 10-x and 50% chance it is x-1, expected value 4.5, and v obviously can't be less than 0, so there can't be any improvement for B.
And B randomizing between different values of x, all of which give the same expected result, will give the same expected result.

If B sticks to the strategy, A cannot increase the expected value of u+v:

Similar logic for A says if A picks a different n, the expected value of u is still 4.5, and B will still know what n is after u is revealed, so v will still be zero.

(aka "Nash equilibrium")

Answer 5

If you choose

$1$ or $10$, you will find the next number for sure,

so in average,

you would have $4.5$ expected value which is found all distances between chosen corner number to all numbers.

as a formula from $1$,

$\frac{0+1+2+3+4+5+6+7+8+9}{10}=4.5$,

How did I find this value?

It is taking every possibilities of A's chose and find the average value. (in other words the expected value/outcome of the game since A randomly chooses the number of him/her.) For this particular example above, we choose $1$ (it could be $10$ too, because of symmetry, it doesnt matter) and if A randomly chooses $1$, the distance would be 0, and since you found the number, our S will be 0. If A choose $2$, our $u$ will be $1$ and since we know what I guessed after this distance value, the next guess's distance (which is $v$) would be 0, and so on. so if we add all (u+v) distances and take the average of them, it will give us the expected value of choosing $1$/$10$ of the game.

So

From now on, the order of the number from left to right represents the $u+v$ value for $1$ to $10$, respectively.

If you choose

$2$ or $9$, If the distance from B's numbers to A's is more than 2 we can apply the same rule above, but if the distance is just $1$, you need to stick the original number again for your guess, because the expected value trying to guess the number would not change the average expected value. For example, let say B chooses $2$ and A chooses $1$, on first guess, $u$ will be 1, then B will know that A's number is $1$ or $3$ but the chance of the number being $1$ or $3$ is actually the same, if B choose $3$, it could cost $2$ points to him, or if he B choose $1$, 0 points. Since the chances are the same, choosing $2$ again would be the same thing.

so

$\frac{2+0+2+2+3+4+5+6+7+8}{10}=3.9$, so choosing $2$ or $9$ makes more sense :)

let's try

$3$ or $8$, which are again mirror, with the same logic,

we get

$\frac{4+2+0+2+4+3+4+5+6+7}{10}=3.7$

which is better than the previous chosen couple.

let's try now

$4$ or $7$,

we get

$\frac{6+4+2+0+2+4+6+4+5+6}{10}=3.9$

which is worse average than before.

lastly,

$5$ and $6$, (chosing distance from $5$)

and we get

$\frac{8+6+4+2+0+2+4+6+8+5}{10}=4.5$

so as a result, we can conclude that

Choosing $3$ or $8$ is the most optimal chosen number for this game, because strategy aftering getting equidistance two possibilities and using any strategy after that would not change the expected outcome value, so just sticking is actually the same in those cases.

Answer 6

First, let's note that:

$X$ is given as a completely random number. B has no idea of what A's number could be at this time.

Also that:

The probabilities involved in choosing $1$ are the same involved in choosing $10$. The probabilities for $2$ are the same as for $9$. $3$ with $8$. $4$ with $7$. $5$ with $6$. So, we need to analyze only $5$ cases of the initial analysis of $X$ and the other five are symmetric.

We will need to evoke a concept:

Expected value is the topic at statistics that will help us. The expected value of a variable $M$ is represented as $E(M)$. In this problem, we are looking for $E(U + V)$, which is the value that we want to minimize.

Let's start with 1:

If $X = 1$, then each value in $[0, 9]$ has $10\%$ of probability of being $U$. Make $Y = X + U$ and then $V = 0$. The error is then $U$. Since each value of the interval $[0, 9]$ has $10\%$ of probability of being $U$ (and also $U + V$), then: $$\begin{array}{rl} E(U + V) = & (10\% \times 0) + (10\% \times 1) + (10\% \times 2) + (10\% \times 3) + (10\% \times 4) + \\ & (10\% \times 5) + (10\% \times 6) + (10\% \times 7) + (10\% \times 8) + (10\% \times 9) \\ = & 10\% \times (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) \\ = & 10\% \times 45 \\ = & 4.5 \end{array}$$ The same reasoning could be applied for $X = 10$, but using $Y = X - U$ instead of $Y = X + U$.

Now, 2:

If $X = 2$, then each value in $[2, 8]$ has $10\%$ of probability of being $U$. $0$ also have $10\%$. $1$ has $20\%$.

If $U = 0$, that is great, Make $Y = X$ and then $V = 0$. This has $10\%$ of probability of happening. So $U + V = 0$ in $10\%$ of the cases.

If $U \ge 2$, fine. Make $Y = X + U$ and then $V = 0$. This has $70\%$ of probability of happening.

If $U = 1$, then we'll need to guess. $Y$ could either be $1$ or $3$. One will give us $U + V = 1$ and the other $U + V = 3$ with $10\%$ of probability for each one.

In the end, we have $20\%$ of probability of getting $U + V = 3$ and $10\%$ of probability of getting $U + V$ as any other value in the interval $[0, 8]$. So, the expected value is: $$\begin{array}{rl} E(U + V) = & (10\% \times 0) + (10\% \times 1) + (10\% \times 2) + (20\% \times 3) + (10\% \times 4) + \\ & (10\% \times 5) + (10\% \times 6) + (10\% \times 7) + (10\% \times 8) \\ = & 10\% \times (0 + 1 + 2 + (2 \times 3) + 4 + 5 + 6 + 7 + 8) \\ = & 10\% \times (0 + 1 + 2 + 6 + 4 + 5 + 6 + 7 + 8) \\ = & 10\% \times 39 \\ = & 3.9 \end{array}$$ The same reasoning could be applied for $X = 9$, but using $Y = X - U$ instead of $Y = X + U$.

Now, 3:

If $X = 3$, then each value in $[3, 7]$ has $10\%$ of probability of being $U$. $0$ also have $10\%$. $1$ and $2$ have $20\%$ each.

If $U = 0$, that is great, Make $Y = X$ and then $V = 0$. This has $10\%$ of probability of happening. So $U + V = 0$ in $10\%$ of the cases.

If $U \ge 3$, fine. Make $Y = X + U$ and then $V = 0$. This has $50\%$ of probability of happening.

If $U = 1$, then we'll need to guess. $Y$ could either be $2$ or $4$. One will give us $U + V = 1$ and the other $U + V = 3$ with $10\%$ of probability for each one.

If $U = 2$, then we'll also need to guess. $Y$ could either be $1$ or $5$. One will give us $U + V = 2$ and the other $U + V = 6$ with $10\%$ of probability for each one.

In the end, we have $20\%$ of probability of getting $U + V = 3$, $20\%$ of probability of getting $U + V = 6$ and $10\%$ of probability of getting $U + V$ as any other value in the interval $[0, 7]$. So, the expected value is: $$\begin{array}{rl} E(U + V) = & (10\% \times 0) + (10\% \times 1) + (10\% \times 2) + (20\% \times 3) + \\ & (10\% \times 4) + (10\% \times 5) + (20\% \times 6) + (10\% \times 7) \\ = & 10\% \times (0 + 1 + 2 + (2 \times 3) + 4 + 5 + (2 \times 6) + 7) \\ = & 10\% \times (0 + 1 + 2 + 6 + 4 + 5 + 12 + 7) \\ = & 10\% \times 37 \\ = & 3.7 \end{array}$$ The same reasoning could be applied for $X = 8$, but using $Y = X - U$ instead of $Y = X + U$.

Now, 4:

If $X = 4$, then each value in $[1, 3]$ has $20\%$ and each value in $[4, 6]$ has $10\%$ of probability of being $U$. $0$ also have $10\%$.

If $U = 0$, that is great, Make $Y = X$ and then $V = 0$. This has $10\%$ of probability of happening. So $U + V = 0$ in $10\%$ of the cases.

If $U \ge 4$, fine. Make $Y = X + U$ and then $V = 0$. This has $30\%$ of probability of happening.

If $U = 1$, then we'll need to guess. $Y$ could either be $3$ or $5$. One will give us $U + V = 1$ and the other $U + V = 3$ with $10\%$ of probability for each one.

If $U = 2$, then we'll also need to guess. $Y$ could either be $2$ or $6$. One will give us $U + V = 2$ and the other $U + V = 6$ with $10\%$ of probability for each one.

If $U = 3$, then we'll once again will need to guess. $Y$ could either be $1$ or $7$. One will give us $U + V = 3$ and the other $U + V = 9$ with $10\%$ of probability for each one.

In the end, we have $20\%$ of probability of getting $U + V = 3$, $20\%$ of probability of getting $U + V = 6$ and $10\%$ of probability of getting $U + V$ as any other value in the interval $[0, 5]$. And also, $10%$ of probability of getting $U + V = 9$. So, the expected value is: $$\begin{array}{rl} E(U + V) = & (10\% \times 0) + (10\% \times 1) + (10\% \times 2) + (20\% \times 3) + \\ & (10\% \times 4) + (10\% \times 5) + (20\% \times 6) + (10\% \times 9) \\ = & 10\% \times (0 + 1 + 2 + (2 \times 3) + 4 + 5 + (2 \times 6) + 9) \\ = & 10\% \times (0 + 1 + 2 + 6 + 4 + 5 + 12 + 9) \\ = & 10\% \times 39 \\ = & 3.9 \end{array}$$ The same reasoning could be applied for $X = 7$, but using $Y = X - U$ instead of $Y = X + U$.

Finally:

If $X = 5$, then each value in $[1, 4]$ has $20\%$ of probability of being $U$. $0$ and $5$ also have $10\%$ each.

If $U = 0$, that is great, Make $Y = X$ and then $V = 0$. This has $10\%$ of probability of happening. So $U + V = 0$ in $10\%$ of the cases.

If $U = 5$, fine. Make $Y = X + U$ and then $V = 0$. This has $10\%$ of probability of happening.

If $U = 1$, then we'll need to guess. $Y$ could either be $4$ or $6$. One will give us $U + V = 1$ and the other $U + V = 3$ with $10\%$ of probability for each one.

If $U = 2$, then we'll also need to guess. $Y$ could either be $3$ or $7$. One will give us $U + V = 2$ and the other $U + V = 6$ with $10\%$ of probability for each one.

If $U = 3$, then we'll once again will need to guess. $Y$ could either be $2$ or $8$. One will give us $U + V = 3$ and the other $U + V = 9$ with $10\%$ of probability for each one.

If $U = 4$, guess once more. $Y$ could either be $1$ or $9$. One will give us $U + V = 4$ and the other $U + V = 12$ with $10\%$ of probability for each one.

In the end, we have $20\%$ of probability of getting $U + V = 3$, $10\%$ of probability of getting $U + V$ as any other value in the interval $[0, 6]$. And also, $10\%$ of probability of getting $U + V = 9$ and $10\%$ for $U + V = 12$. So, the expected value is: $$\begin{array}{rl} E(U + V) = & (10\% \times 0) + (10\% \times 1) + (10\% \times 2) + (20\% \times 3) + (10\% \times 4) + \\ & (10\% \times 5) + (10\% \times 6) + (10\% \times 9) + (10\% \times 12) \\ = & 10\% \times (0 + 1 + 2 + (2 \times 3) + 4 + 5 + 6 + 9 + 12) \\ = & 10\% \times (0 + 1 + 2 + 6 + 4 + 5 + 6 + 9 + 12) \\ = & 10\% \times 45 \\ = & 4.5 \end{array}$$ The same reasoning could be applied for $X = 6$, but using $Y = X - U$ instead of $Y = X + U$.

General rule:

After B chooses some $X$ and was given some $U$, this is what B should do:

1. Compute $P = X + U$ and $Q = X - U$.
2. If $P = Q$, then $Y = P$.
3. If only one of $P \in [0, 9]$ and $Q \in [0, 9]$ is true, choose that one as $Y$.
4. Otherwise, guess either $P$ or $Q$ as the answer. One is a good guess and the other is a terrible one. If you prefer to not be cold nor hot and stay warm, you might just choose a middle ground and make $Y = X$.

The best numbers to choose as $X$ are:

$3$ and $8$. Their expected value is lower than the other choices.

Answer 7

I think B picks:

either 3/8 or 4/7.

Why?

Let's say B picks x=4, (the argument is similar for x=7) then if A had picked n=1,2,3,4,5,6,7 u=3,2,1,0,1,2,3pts respectively. B now knows the range is n=1,...,7, and on their next guess should pick either y=3 or y=5, which at worst will be at most 4pts, a total of 7pts. If not, say A chose from 8,9,10, B already knows the result, for a maximum total of 6pts (from n=10). Result: $u+v\le7$.

If B picks x=3, the worst case is 7pts from A having chosen n=10 (next guess from B is 0pts).

The other two cases: If B picks x=5, worst case is 9pts (n=9 incurs 4pts, B goes for y=6 but n=1 gives another 5pts).

If B picks x=1 or x=2, worst case is at least 8pts.