3
$\begingroup$

I have a question about the finite analog of the puzzle proposed here involving mathematicians guessing the contents of boxes.

Specifically, suppose there are $k$ unopened boxes each containing a single symbol from an alphabet of $r$ symbols, where $k$ and $r$ are possibly finite nonzero cardinals. A mathematician wants to guess the contents of an unopened box by opening some proper subset (or subsets, if he wants) of the boxes, examining those symbols, and then selecting an unopened box to guess.

Denote the mathematician's guessing strategy (which may of course be randomized) by $\sigma$. For an initial box configuration $C$, let $P_\sigma(C)$ be the probability that the mathematician guesses correctly when using strategy $\sigma$ on configuration $C$. Let $\pi_\sigma$ be the infimum of $P_\sigma(C)$ over all initial box configurations $C$.

When $k=\omega$, it was shown that for any $0\le p \lt 1$, there is a strategy $\sigma$ satisfying $\pi_\sigma\ge p$. (Actually, this was shown for $r=2^{\aleph_0}$, but the same argument works for arbitrary $r$. Compare as well this question , where Eric Naslund showed that $\omega$ mathematicians who independently try the game can guarantee that there is at most one wrong guess between them).

Can someone please explain a simple reason that, for finite $k$ and $r$, $\pi_\sigma\le 1/r$?

This is intuitively obvious, of course - but of course, it's also intuitively obvious when $k=\omega$.

$\endgroup$
2
  • $\begingroup$ The finite analog of the infinite-version puzzle is: open a subset of the boxes, and guess a majorant for an unopened one. Then you can win with probability $\frac{k-1}{k}$. It can be used as a warm-up for the infinite version, as it gives one of the ideas needed. $\endgroup$
    – Denis
    Jan 2, 2014 at 11:52
  • $\begingroup$ Good point. I should have asked, thus, how to prove that ${k-1}\over{k}$ is optimal here. That is, suppose we have finite $k\gt 1$ and box contents reals. Then for any strategy $\sigma$ there is a configuration $C$ such that the $\sigma$ guesses a value that is smaller than the contents of the selected unopened box with probability $\ge {1/k}$ $\endgroup$
    – user44653
    Jan 3, 2014 at 2:42

1 Answer 1

3
$\begingroup$

It follows from the fact that, for any strategy $\sigma$, then the average over configurations of a correct guess is precisely $1/r$: $$\frac{1}{r^k}\sum_CP_{\sigma}(C)=\frac{1}{r}.$$ This is true for deterministic strategies because if you partition configurations into sets of $r$ that differ only in the content of the box that the mathematician chooses, then the strategy works on precisely one configuration from each set of $r$. (In fact, this is pretty much equivalent to Bjorn's answer.) It follows for probabilistic strategies since they are weighted averages of deterministic strategies.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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