combinatoricsprobability
Your (honest) opponent choose a random number from 1 to 13 inclusive. You have to guess the number, and you win if the guess is correct. If not, your opponent either reduces the number chosen by one or increases it by 1, and you guess again.
The question is, what is the minimum # of attempts necessary to guarantee a win for you.
I am not able to get a handle on the problem.
Also, (a new variant just thought of), how many guesses should be allowed for a fair or "nearest to fair" game ?
First of all, the expected value for B (6) is not 2.83333 but rather 2.333333 as is stated in an example in the problem. Second of all, it's kind of against the spirit of project euler to just look up the solution, but here are some recursive formulas to help you along (you'll need a better approach for the full scale problem though.
For B (n), let $ i = \left \lfloor {n + 1 \over 2} \right \rfloor $. Then $$ B (n) = 1 + {i - 1 \over n} B (i - 1) + {n - i \over n} B (n - i) $$ This is one guess plus the number of guesses afterwords if the secret number is lower than the guess times the probability of the secret number being less than the guess plus the number of guesses afterwords if the secret number is higher than the guess times the probability of the secret number being higher than the guess.
For R (n), the randomization makes it less simple, but for any choice of the guess i the expected value for secret values below and above is easily defined recursively as the probability of the secret number being in that range times the recursively calculated expected value. We can't really choose i so we sum over all i and multiply by 1/n, the probability of each one being chosen. Then the above and below recursive terms combine and we get $$ R (n) = 1 + {2 \over n^2} \sum_{i = 1}^{n - 1}{i R (i)} $$
You can easily expand these by hand for n = 6 and I think you might see a pattern.
The key to this is that the ACTUAL sum of all the hats (mod 100) must be one of the numbers from 0 to 99.
Whichever number it is, that player will have guessed his/her hat color correctly.
A corollary: no one else will have guessed correctly. Only the person whose player number matches the actual sum of the hat colors (mod 100) will have guessed right.
Edit to answer this comment:
Your answer is clear in case that the hat color of each player are all different and in case that the hat color of all the players is just one color, say 100 green. But I'm not clear in case there are some repetition of colors, say 40 red, 30 green, 20 blue and 10 yellow. I think there will be 4 groups of 40, 30, 20, 10 different answers. What will guarantee the success ? Will there be more than one correct guess ? Please explain in more details on this point.
Let's work out your example. First, let's assume the colors are numbered like so:
(Remember, there are another 96 colors available that DON'T happen to be used, but could be.)
And let's say that the players are as follows:
Exactly one player will guess right. Who will it be?
To work that out, compute the sum of all the hat colors, mod 100:
$$(13\times40)+(36\times30)+(45\times20)+(79\times10) \mod 100$$ $$20+80+0+90\mod 100$$ $$90$$
Player 90 will guess his hat color right.
How will he do that? Well, player 90 (who is wearing a yellow hat) will see the following hats:
He will then total these to 11 (mod 100), and to make the total sum congruent to his own player number of 90, he will guess color 79 (which is yellow).
(Edit to add: regardless of which players are wearing which hats, if there are 40 red, 30 green, 20 blue and 10 yellow and the colors are numbered as above, player 90 will be the one to guess right no matter what color hat he is wearing. Because he will compute his guess, taking into account all 99 hats he sees, such that the sum of those hats plus the hat color he is guessing is congruent to his player number, mod 100.)
Note that player 56 will ALSO guess color 79 (yellow), but player 56 is wearing a RED hat.
Player 56 will compute the sum of all hats he can see like so:
$$(13\times39)+(36\times30)+(45\times20)+(79\times10) \mod 100$$ $$7+80+0+90\mod 100$$ $$77$$
To make the total sum congruent (mod 100) to his player number of 56, he will guess color 79. (Because $79+77=156\equiv56\mod100$)
By contrast, player 30 (who wears a yellow hat) will compute:
$$(13\times40)+(36\times30)+(45\times20)+(79\times9) \mod 100$$ $$20+80+0+11\mod 100$$ $$11$$
Note this is the same partial sum that player 90 reached. However, player 30 will not guess the color 79 (because 79+11 = 90 and he is not player 90). Instead, he will guess color 19, whatever that is. Maybe it's purple. Since he doesn't have a purple hat, his guess is wrong.
So it's NOT guaranteed that each color is guessed once. It's NOT guaranteed that each guess is different. (These statements are equivalent. And they can happen, for instance in the case where everyone wears a green hat.)
What is guaranteed, is that exactly and only one guess will be correct, and the rest will be wrong.
Let $a_i$ be the hat color number of player numbered $i$, where $i\in\{0, 1, \ldots, 99\}$
(Example: if player number $1$ wore the same color hat as player number $8$, we would write $a_1 =a_8$.)
Thus, any player $k$ knows the value of $k$, but not the value of $a_k$. (This is given in the puzzle and requires no proof.)
Let $S$ be the sum of all hat colors mod $100$; to be precise:
$$(S \in \{0,1,\ldots,99\}) \land (S \equiv \sum_{i=0}^{99} a_i \mod 100)$$
No player knows $S$. However, any player $k$ may compute the value $P_k$ (for "partial sum as known to player $k$") which we may compute as follows:
$$P_k \equiv S-a_k\mod100$$
The player computes this as follows:
$$P_k \equiv \sum_{0\le i\le99, i\ne k}a_k \mod100$$
In other words, by adding all hat colors visible to that player (and reducing it mod 100).
Each player $k$ assumes that the actual sum $S$ is equal to that player's player number: i.e. it's assumed by any player $k$ that $S=k$.
Thus player $k$ shall make guess $G_k$ (for the value of $a_k$) such that:
$$G_k \equiv k-P_k \mod 100$$
We can see (by adding $P_k$ to both sides) that $G_k + P_k \equiv k \mod 100$. In other words, the guessed color plus the sum of all visible hat colors, mod 100, equals the player's number.
But $S \equiv P_k + a_k$, so that $G_k = a_k$ (i.e. the guess is correct), if and only if $S\equiv k \mod100$.
By the pigeonhole principle, there is only one $k$ such that $S \equiv k \mod 100$.
Therefore, the only player who shall guess correctly is player number $S$, and the rest shall guess wrong.
Best Answer
The optimal strategy for $n=13$ (and similarly for any odd value of $n$) is to try $2,3,\ldots,n-1=12$ first, which will catch the opponent if and only if she started on an even number; if the opponent is still not caught, one is sure she started on an odd number. In that case one is now (after $n-2=11$ moves) on an even number (in particular not on $n=13$), and trying $12,11,\ldots2$ is sure to catch her, for a total of $2*11=2n-4=22$ tries.
The same scheme works for $n=12$ (and similarly for any even value of $n$): try $2,\ldots,n-1=11$ first, which will catch the opponent if and only if she started on an even number; if she still not caught, one is sure she is now (after $n-2$ moves) again an odd number (in particular not on $n=12$), and trying $n-1=11,\ldots2$ is sure to catch the opponent, for a total of $2*10=2n-4=20$ tries.
Added: Here is the full analysis of the game. It clearly splits into two parallel games, one where the opponent starts odd and another where she starts even. The opponent chooses a game at the start and has to stick to it, but we don't know which it is, so we need to reduce to number of remaining potential positions in both games to $0$. On each move we remove one of the potential positions, but then the remaining possible positions are replaced by the set of all their neighbours; this also happens in the game we didn't play in. If one switches back-and-forth between games (playing game $A$, then at leat once game $B$ then again game $A$), then the before the second move in game $A$ the number of potential positions in game $A$ (if the first move didn't reduce it to $0$) has again grown to at least the same number it was before the previous move in $A$, so this gains nothing; an optimal strategy therefore should avoid such switching. We must therefore choose a game to play in first, terminate that game entirely, and then start playing in the other game.
Now focussing on one game (so the parity of the possibilities at each point in time is known), one may verify that the only type of move that actually reduces the number of remaining possibilities is where those possibilities form an "interval" (in the sense of the numbers of a given parity in a given interval) containing one of the extremities of the total set: by playing the other end of the interval, the possibilities are reduced to those of the opposite parity between the ends of the original interval. (The claim "only" is not entirely true: (1) whenever the possibilities have been reduced to a singleton, one can play that to reduce it to $0$, and (2) if $n$ is odd and all odd numbers remain possible, their number is bound to decrease regardless of our move. However these possibilities are marginal and do not affect our analysis.) After such a move one cannot reuse the number again on the next move, but by playing again on the same end of the (new) interval one can at least prepare do decrease it on the move after that.
There are four types of games, according to the parity of $n$ and of the initial possibilities. The two variants with $n$ even are left-right mirror images, and the "initial even" one can be won in $n-2$ moves by playing $2,3,\ldots,n-1$. So can the "initial even" game with $n$ odd. The game with $n$ odd and initial possibilities odd however needs $n-1$ moves: the very first move makes no difference whatsoever, and then the "initial even" game remains. Since we have the choice which game to play in first, and since for $n$ odd the "initial even" game requires an odd number of moves, we can play that first and have transformed the other game into another "initial even" game, so in the end we can still win in $2(n-2)$ moves, regardless of the parity of $n$.