7
$\begingroup$

I came across the following interesting puzzle in a magazine.

Suppose we have $101$ suitcases, numbered $0, \dots, 100$, with a bottle of rum in suitcase $x$, and a bottle-opener in suitcase $y$ such that $|x-y|\leq 50$.

We have $2$ players playing the $T$-suitcase game, where player $A$ is allowed to choose $x$, and $y$ in the above described manner. Player $B$ is allowed to open $T$ suitcases, but they all have to be consecutive numbers. The first suitcase he is allowed to choose any number $0,1,\dots, 100$, and for the other suitcases he is only allowed to open a suitcase left or right from an already opened suitcase. Player $B$ wins if he can find both the rum and the bottle-opener, and player $A$ wins if he doesn't.

What are the chances of winning for player $A$, and $B$ in the cases $T=60, 70, 80$, considering the fact they both try to optimize their winning chances?

I found this extremely interesting, but I didn't get further than a few observations. For example, it is clear that $2T-101$ suitcases in the middle will always be opened, so player $A$ will never put both the rum, and opener in these suitcases.

I've been reading a little about game theory, and I was wondering if maybe some ideas concerning the Nash-Equilibrium can be used, and try to come up with an equilibrium situation where both player $A$, and $B$ will not change their current strategy since it would result in a lower winning chance. The prisoners dilemma is a nice illustration of such principle. To use an idea of a Nash Equilibrium, I guess I need to make a list of possible strategies for $A$, and $B$, but I'm not sure how.

I'm not interested in detailed solutions, but I wonder if someone could provide some enlightening ideas, or insight into the problem. I really like this problem.

$\endgroup$
  • 2
    $\begingroup$ Does Player $B$ announce the entire range of suitcases to be opened in one go, or open one suitcase after another and then decide which others to open? (I believe the latter would be considerably more difficult to solve than the former.) $\endgroup$ – joriki Jul 29 '16 at 23:10
  • $\begingroup$ The players are going to have to be using a mixed strategy NE, with randomization over the placement of the objects and randomization of the suitcases opened. $\endgroup$ – smcc Jul 29 '16 at 23:13
  • $\begingroup$ Excuse me, suddenly im not so sure, since i havent even considered that. I believe actually they should be opened one by one. So if player $B$ finds $x$, he can still optimize his strategy to find $y$. That does make a big difference to the problem, right? I restated it. $\endgroup$ – DinkyDoe Jul 29 '16 at 23:16
  • 1
    $\begingroup$ I believe where it says "randomely", you mean "arbitrarily"? After several edits and some confusion about a central aspect of the puzzle, I'd suggest that you quote it verbatim from the magazine so we're sure there are no further misunderstandings. $\endgroup$ – joriki Jul 29 '16 at 23:30
  • 1
    $\begingroup$ Are you sure that the first suitcase opened isn't allowed to be number $0$? That would be an odd restriction. $\endgroup$ – joriki Jul 29 '16 at 23:47
2
$\begingroup$

Below I will provide a full solution, but in an attempt to honor the spirit of the question, I will first try to provide some ideas and hints about how one can think about this problem.

Ideas

In a vacuum, it is hard to say what $B$ should do. However, if we assume that $B$ knows $A$'s strategy, it is generally much easier to see what $B$ should do. (Of course, this will be trivial unless $A$'s strategy is random.) Thus, we can analyze a strategy of $A$ by assuming $B$ knows that this strategy is being used. This will provide a lower bound on the effectiveness of $A$.

On the other hand, we can also try to analyze a strategy of $B$ without respect for the strategy of $A$. Certain strategies of $B$ will have some probability of guessing correctly no matter what strategy $A$ chooses. (Again, in the non-trivial case, such a strategy will be random.) This can provide an upper bound of the effectiveness of any strategy of $A$.

If the lower bound and upper bound meet, then the problem is solved.

Simple strategies

One simple strategy of $A$ is to choose with equal probability between $(0,50)$ and $(50,100)$. Even if $B$ knows that $A$ is employing this strategy, guessing $50$ provides no information, and $0$ and $100$ cannot both be covered (assuming $T < 101$), so $B$ must resort to guessing. Thus, $A$ can certainly always win with at least probability $\frac{1}{2}$.

One simple strategy of $B$ is to break up the suitcases into overlapping intervals such that any possible pair chosen by $A$ is in at least one such interval. If there are $n$ intervals, then $B$ can certainly always win with at least probability $\frac{1}{n}$.

(However, these strategies are not always optimal, depending on $T$.)

Full solution

Case 1: $100 \ge T\ge 76$

In this case, $B$ can cover all possibilities with only $2$ intervals: $[0,75]$ and $[25,100]$. For example, if $A$ tries to avoid the first interval, $76$ may be chosen, but in this case the smallest second choice is $26$ which is also in the second interval. This means $A$ has an upper bound of $\frac{1}{2}$, and with the same lower bound provided above, the optimal chance of winning for $A$ is indeed $\frac{1}{2}$.

Case 2: $75 \ge T \ge 67$

$A$ has an improved strategy available. Since $B$ can no longer cover all possibilies with $2$ intervals, $A$ should introduce a possibility that is covered by neither $[0,74]$ nor $[26,100]$. In fact, the only choice is $(25,75)$. So, the proposed strategy for $A$ is to choose with equal probability between $(0,25)$, $(25,75)$, and $(75,100)$.

Suppose $B$ knows this strategy is being used. Then $B$ gains no information from guessing any suitcase except $0$, $25$, $75$, or $100$. Guessing $0$ or $100$ only allows $B$ to win if those guesses are correct, so only with probability $\frac{1}{3}$. Consider then if $25$ is guessed. If the guess is wrong, then $B$ is out of luck because $100$ is unreachable. If the guess is right, then both $(0,25)$ and $(25,75)$ are still possibilities, and $B$ must choose between them. Thus, there is still only a $\frac{1}{3}$ chance for $B$ to succeed. The situation is the same for guessing $75$.

Thus, this strategy ensures that $A$ can win with probability at least $\frac{2}{3}$.

$B$ can still cover all possibilities with only $3$ intervals. In the case of $67$, these will be $[0,66]$, $[17,83]$, and $[34,100]$. This means $A$ also has an upper bound of $\frac{2}{3}$, so answer is $\frac{2}{3}$.

Case 3: $66 \ge T \ge 51$

This case is trickier.

In fact, $B$ now has a more complicated strategy still ensures victory with probability at least $\frac{1}{3}$. Consider, $B$ must still cover the possibility that $A$ may choose $0$ or $100$, so $[0,50]$ and $[50,100]$ are still good guesses. So, when will these possibilities fail?

The third possibility, of course, is that one of $x$ and $y$ is in $[0,49]$ and the other is in $[51,100]$. $B$ can guarantee finding both $x$ and $y$ in such a case by exploiting the ability to open cases one at a time. $B$ should first guess $50$, then start going left until finding one of $x$ and $y$. Then $B$ should start going right from $50$ until finding the other.

$A$'s optimal strategy, then, remains the same as before, so the optimal chance of $A$ winning is still $\frac{2}{3}$.

Note that $B$'s strategy here also works for Case 2, so these cases can be combined if desired.

$\endgroup$
  • $\begingroup$ Brilliant and thorough answer - enjoyed reading this! $\endgroup$ – Thomas Russell Oct 8 '16 at 7:58
  • $\begingroup$ Thank you kindly. That's a great answer! $\endgroup$ – DinkyDoe Oct 20 '16 at 9:40
0
$\begingroup$

Well if I were A I would put the rum in suitcase 0 and the opener in 100. Then there is no contiguous selection of suitcases that would obtain both. I would always win.

$\endgroup$
  • $\begingroup$ The strategy set are the pairs (x,y) such that $|x-y|\le 50$ so your suggestion is not a feasible strategy $\endgroup$ – Sergio Parreiras Aug 8 '16 at 14:54

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.