3
$\begingroup$

You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2.

In order to increase your chances, you can coordinate with a friend. You do the coordination before the game starts. Then, the friend can see what's behind all the doors, and send you a single integer number between 1 and $n$.

You receive your friend's number, but, in addition to that number, you receive $k-1$ more numbers between 1 and $n$, which are selected at random without replacement between 1 and $n$. You don't know which of the $k$ numbers is the real message and which is fake.

What strategy can you and your friend can coordinate, such that your probability of finding a treasure is maximized?

EXAMPLE: suppose $k=2$. Then, one possible strategy is that the friend just selects a door with a treasure behind it, and sends its number to you. You receive your friend's number and another number, in random order. Suppose you just pick the first number that you receive and open the door with that number. If it is your friend's number then you win; if this is a fake number then you have a chance of 1/2 to win. Hence, your total chance of winning with this strategy is 3/4. Is this correct? Is there a better strategy?

$\endgroup$
  • 5
    $\begingroup$ This seems to be more of a puzzle than a computer science question. Could you clarify the computer science content, please? $\endgroup$ – David Richerby Oct 12 '15 at 10:59
  • $\begingroup$ @DavidRicherby I thought it might be related in some way to coding theory, where the goal is to send messages over a noisy channel. But maybe you are right and this question should be moved to puzzles.SE. $\endgroup$ – Erel Segal-Halevi Oct 12 '15 at 11:39
  • $\begingroup$ Let's see what happens. The question has some upvotes and the answer has some more, which suggests that some people think it's on-topic enough to stay here. $\endgroup$ – David Richerby Oct 12 '15 at 12:11
  • $\begingroup$ This looks like a pure math question to me. We aren't necessarily averse to pure math questions if they have a strong connection to CS or if they are best answered from a CS perspective, but we expect the question to explain that connection. Can you edit the question to explain the connection to CS? See meta.cs.stackexchange.com/q/704/755 and meta.cs.stackexchange.com/q/260/755 for our policy. Alternatively, you can flag for migration to Math.SE if you think it's more appropriate there. $\endgroup$ – D.W. Oct 12 '15 at 21:58
  • $\begingroup$ @D.W. The question is about an optimal algorithm (protocol/strategy). Although optimality is measured by mathematical means (- probability of success), there is still an algorithm here. But, if other members think that the question should be migrated, I do not object. $\endgroup$ – Erel Segal-Halevi Oct 13 '15 at 9:44
7
$\begingroup$

Suppose that $k \ll n$. In that case, your friend can send you the index of the first door containing a treasure. Of the $k$ numbers you get, you pick the smallest one. If $k$ is small enough compared to $n$, then it is very likely that the smallest of the $k$ numbers is the one that your friend sent you.

More concretely, suppose that $k$ is constant. With probability $1-1/n$, the number that your friend sends you is at most $\log n$. The probability that the other $k-1$ numbers are more than $\log n$ is $(1-\log n/n)^{k-1} \approx 1-k\log n/n$. We conclude that this strategy fails with probability at most roughly $1/n + k\log n/n$, which tends to $0$ as $n \to \infty$.

To determine how small $k$ should be, let us be a bit more careful. Denote by $m$ the number that your friend sends you; the distribution of $m$ is geometric (we ignore for now the event in which there are no treasures at all), and so $\Pr[m] = 2^{-m}$. The probability that one of the other $k-1$ numbers is smaller than $m$ is $1-(1-(m-1)/n)^{k-1}$. Overall, this strategy fails with probability $$ \frac{1}{2^n} + \sum_{m=1}^n 2^{-m} \left(1 - \left(1 - \frac{m-1}{n}\right)^{k-1}\right) = 1 - \sum_{m=1}^n 2^{-m} \left(1 - \frac{m-1}{n}\right)^{k-1}. $$ We can non-rigorously estimate this as $$ 1 - \sum_{m=1}^\infty 2^{-m}e^{-(m-1)k/n} = 1 - \frac{1}{2-e^{-k/n}} = \frac{1-e^{-k/n}}{2-e^{-k/n}} \approx \frac{k}{n}. $$ This suggests that if $k = o(n)$ then you win with probability $1-o(1)$.

$\endgroup$

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.