4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Will person B try to maximize the sum or do they pick x and y at random. $\endgroup$ – hexomino Dec 16 '18 at 12:43
  • $\begingroup$ @shA.t I just realized I asked for person As strategy. I intended to ask for person Bs strategy though. I fixed it now. $\endgroup$ – Finni Dec 16 '18 at 12:53
  • $\begingroup$ @hexomino person B will not pick random but with a certain strategy. The question is, which strategy person B should follow. $\endgroup$ – Finni Dec 16 '18 at 12:54
  • $\begingroup$ Does A pick at random, or is A trying to maximize u+v? $\endgroup$ – gogators Dec 16 '18 at 15:42
  • $\begingroup$ When thinking of person Bs strategy, I assume A picks randomly, but it would also be interesting to come up with a strategy for person A. Knowledge of As possible strategies may affect Bs strategy... But in this question I focused on Bs strategy assuming A picks randomly. $\endgroup$ – Finni Dec 16 '18 at 15:48
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ How did you find the expected value? $\endgroup$ – Finni Dec 16 '18 at 19:49
  • 2
    $\begingroup$ I included the calculation of the expected values. $\endgroup$ – gogators Dec 17 '18 at 14:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your thoughts about more guesses really tempts me to post the puzzle again, but generalize it to n guesses and numbers between 1 and m... very interesting! $\endgroup$ – Finni Dec 16 '18 at 19:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ah ok- I realize I have just restated your answer, which I think is correct.... but I was confused by one of your statements where you mentioned "random choice between them", which I read the wrong way... I read it as allowing an intermediate value between these two options, but now I see that reading is incorrect... -- so now I realize that my answer is just yours expressed differently.... so you get my plus one.... $\endgroup$ – tom Dec 16 '18 at 16:58
  • $\begingroup$ 1. Where does the 2(x-1) in your equation come from? 2. The worst result when choosing x = 4 is 9. Example: x = 4, n = 1, => u = 3 => A chooses y = x + u = 4 + 3 = 7 => v = 6 => u + v = 9 $\endgroup$ – Finni Dec 16 '18 at 21:17
  • $\begingroup$ I don't think I understand. You say "A chooses y = ..." but y is chosen by B not A, and in this situation B would choose y=4 not y=7. The total error would then be 3+3=6. $\endgroup$ – Gareth McCaughan Dec 17 '18 at 12:35
  • $\begingroup$ A chooses randomly. $\endgroup$ – gogators Dec 18 '18 at 16:52
  • 1
    $\begingroup$ When I wrote this answer, the question did not say that A chooses randomly. $\endgroup$ – Gareth McCaughan Dec 19 '18 at 0:15
1
$\begingroup$

@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")

$\endgroup$
  • $\begingroup$ Why is the chance of u being either 0 or 9 50%? Isn't it 1/10 for 0 and for 9 and all the numbers between respectively? $\endgroup$ – Finni Dec 16 '18 at 20:04
  • $\begingroup$ @Finni - both A and B are flipping a coin and picking the extreme values. $\endgroup$ – deep thought Dec 16 '18 at 20:05
  • $\begingroup$ Wow. I just realized that is indeed the best strategy, assuming that A does not pick randomly. That surprised me, actually... (Even though we do not know wether this strategy is just better than picking randomly, or if it is the best strategy for A) So you get my +1, but in the comments I stated that we assume A does pick randomly, which is why I cannot accept your quite unexpected (at least for me) discovery as the solution. $\endgroup$ – Finni Dec 16 '18 at 20:15
  • $\begingroup$ @Finni ok I see :-) perhaps you could edit that comment into the question? $\endgroup$ – deep thought Dec 16 '18 at 20:21
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you explain the terms in your equations? $\endgroup$ – gogators Dec 17 '18 at 15:24
  • $\begingroup$ @gogators sure, editing now. $\endgroup$ – Oray Dec 17 '18 at 16:55
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

I think the answer is:

Strategy for B: selects 5 or 6 as x and u+x as y

Reason:

When difference in talking is always positive so u and v are positive.
To reduce value of an add operation of two positive number you should minimize both. Maximum differences between n and x can be 10-1=9 so middle of that is 9/2+1=5.5 that nearest values are 5 and 6.
If B selects 5 or 6 as x; he will minimize the risk.
To minimize v as B knows n=u+x then by saying u+x as y then v=0 and then u+v=u and it will become minimal.

$\endgroup$
  • $\begingroup$ I guess this is right for person As strategy. Unfortunately I asked for person As strategy, but I meant to ask for person Bs strategy. When thinking of person Bs strategy, the optimal strategy for person A might also be affected. $\endgroup$ – Finni Dec 16 '18 at 12:59
  • $\begingroup$ Why do you think this is the best strategy for person B? Keep in mind that when x is 5 and u is 2, n can be both 3 or 7! Always choosing u+x as y creates a 50/50 scenario: either v = 0, or v = 2*u. Furthermore, what should B pick as x? $\endgroup$ – Finni Dec 16 '18 at 13:04
  • $\begingroup$ B will selects 5 or 6 as x ;). $\endgroup$ – shA.t Dec 16 '18 at 13:09
  • $\begingroup$ n ≠ u+x! instead n= u±x. When keeping this in mind, 5 or 6 might not be the best choice for x, as n might be 10. For example: If x is 5, and n is 9, u is 4. Now A has 3 options: x + u and x - u for trying to minimize v, or y = x, for choosing the safe option. In the worst case, A ends up with u + v = 12! There are definitely strategies with a better worst case. $\endgroup$ – Finni Dec 16 '18 at 13:15
  • $\begingroup$ I think this is the correct answer for one guess, but I think for more than one guess it is not correct, because you don't learn anything with your first guess that could help with the second guess... $\endgroup$ – tom Dec 16 '18 at 16:57
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "If 4 scores 1,2,3pts, the next guess of 3 will be at most 4 out for a total of 7pts." If who scores (does "score" mean u and v?) on what? Your answer sounds plausible, but I don't quite get which of your points and numbers represent which number... Could you maybe use the letters I used in the question? I think this will make your answer more understandable $\endgroup$ – Finni Dec 16 '18 at 14:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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