Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Allow me to propose a modification of a previously asked puzzle. I would like to replace 100 in that puzzle by $\omega$ and replace $99$ by "all but one". A version of the puzzle was also discussed on MathOverflow. Is there still a winning strategy for my modification?

In detail:

There are infinitely many rooms $\{R_n : n \geq 1\}$. Inside each $R_n$ there are boxes $\{B_{n, m} : m \geq 1\}$ each containing a real. For every $k, l, m$, boxes $B_{k, m}$ and $B_{l, m}$ have the same real. In other words, all the rooms are identical with respect to the boxes and real numbers.

Knowing the rooms are identical, mathematicians $\{M_n : n \geq 1\}$ play a game. After a time for discussing strategy, the mathematicians will simultaneously be sent to different rooms, not to communicate with one another again. While in the rooms, each mathematician may open up all but one boxes to see the real numbers contained within. Then each mathematician must guess the real number that is contained in the unopened box of his choosing.

All but one must correctly guess their real number for them to (collectively) win the game.

Is there a winning strategy?

share|improve this question
    
Are n and m real numbers, or integers? I mean the n and m indicating a room and a box. –  user72372 Dec 20 '13 at 1:29
    
Very nice question! –  JDH Dec 20 '13 at 2:36
1  
Is your question the same as this one on Math Overflow? –  bof Dec 30 '13 at 9:47
    
Thanks. That is a very nice winning strategy. –  hot_queen Dec 30 '13 at 15:26
add comment

1 Answer

There can be no such winning strategy that works in all configurations of the boxes.

First, one should remark that the solution method of the other puzzle to which you link shows that under the axiom of choice, assuming that the mathematicians are able to hold suitable information in mind, there is a strategy that will guarantee that at most finitely many of them are wrong.

The idea is this. Say that two $\omega$-sequences of reals are $\sim$-equivalent if and only if they agree on all but finitely many of their elements; or in other words, that as sequences they eventually agree. By the axiom of choice, select a representative from each equivalence class. Let the mathematicians all agree on these representative choices. Let the $n^{th}$ mathematician look at all the boxes except the box $n$ in room $n$. From this information, the mathematician learns the $\sim$-equivalence class of the sequence of reals. He or she now simply guesses the value that the representative of that class has for the unopened $n^{th}$ box. At most finitely many of the mathematicians will be wrong, since at most finitely many of the actual box values can differ from the values in the representative of that class. Thus, we have a strategy where all but finitely many of the mathematicians guess correctly.

But second, I claim that there can be no strategy that ensures at most one of the mathematicians is wrong. Suppose there is such a strategy. What is a strategy? It is a function that assigns to each $n$ which box they must leave unopened and for each $n$ assigns a function telling them what to guess depending on the observed values in the other boxes. Suppose we have such a strategy. Fix some pattern of values for the boxes. If two mathematicians are leaving the same box unopened, then clearly by changing that value, we can make them both wrong. So all the mathematicians must be leaving different boxes unopened. Pick any two mathematicians, say, $0$ and $1$, and let $n_0$ and $n_1$ be the boxes at which they will look. Let's entertain the idea of changing the values of those boxes to $x$ and $y$. Let $f(y)$ be the guess that $0$ will make if $n_1$ is changed to $y$, and let $g(x)$ be guess that $1$ will make if $n_0$ is changed to $x$. What we need are values $x$ and $y$ such that $f(y)\neq x$ and $g(x)\neq y$, for then if we change the values of the boxes to $x$ and $y$, respectively, then both of their guess will be wrong. But I claim that for any two functions $f$ and $g$ on $\mathbb{R}$, we can find values like that.

Lemma. If $f,g:\mathbb{R}\to\mathbb{R}$, there are $x,y$ with $f(y)\neq x$ and $g(x)\neq y$.

Proof. Pick any $x$ and note that all but one $y$ have $y\neq g(x)$. If all those $y$ have $f(y)=x$, then $f$ has at most two values in its range. In this case we may pick a different $x\notin\text{ran}(f)$, and then simply select any $y\neq g(x)$. QED

So we can change the values of the boxes at those values to make both the guess wrong, so there is an arrangement in which at least two mathematicians are wrong. This can clearly be improved to make more of them wrong, but not infinitely many as the previous argument shows.

share|improve this answer
    
I guess the argument shows that for any proposed strategy, we can design a configuration in which both $0$ and $1$ are wrong. And similarly for any finitely many $0$ through $n$. –  JDH Dec 20 '13 at 2:33
    
and I apologize, I should have used mathematicians $1$ and $2$, since you had said $n\geq 1$. –  JDH Dec 20 '13 at 3:04
    
Joel, when you say that $M_1$ and $M_2$ are opening boxes $n_1$ and $n_2$ with $n_1 \neq n_2$, it seems that you are assuming that $n_1$ and $n_2$ do not depend on what is inside boxes $B_{n_2}$ and $B_{n_1}$ resp., but that may not be true of the (non-adaptive) strategy the mathematicians might be following. Does this make sense? –  hot_queen Dec 20 '13 at 3:32
    
Yes, I was assuming that they know which box to leave unopened before opening any boxes. But a more dynamic idea of strategy might change things. Let me think about it. –  JDH Dec 20 '13 at 3:34
    
Let me just add for the convenience of other readers that the strategy for previous version (100 rooms and 100 mathematicians) of the problem was non adapative. –  hot_queen Dec 20 '13 at 3:43
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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