In my last post I asked the following question (I've shortened it here but its the same really.)
An infinite number of people, labelled 1,2,3,... have hats on their head, RED or BLUE. They must all shout at the same time a color. They want only a finite number of people to not guess their own hat color correctly. Can they do this?
YES they can manage to get all but a finite number of hats wrong. Here is what they do in their strategy meeting:
1) Define an equivalence class on infinite strings of R's and B's: x==y iff x and y differ on only a finite number of places. It is easy to show that this is an Equiv relation. We think of the string as telling us the hat colors of all the people.
2) An Equiv Rel induces a partition. Choose, for each part of the partition, a representative. They all know all of the representatives.
NOW, once the hats are put on here is how each person reacts:
Gee, I see all of those hats out there! Since I see all but my hat I KNOW which partition the hat coloring is in. I look at the representative of that partition. I guess the hat color that I have in that representative.
Note that ALL of the people will use the SAME rep, and that rep differs from reality in only a finite number of hats. Therefore the number of incorrect answers is finite.
POINT- when I show this to my class they often don't like it. Some of course do not understand it, but even those who do sometimes say that's not practical or the people would need infinite brains! These are both true, but I like it anyway. HOW ABOUT YOU- does the solution satisfy?
NEW PROBLEM (are any problems really new?) I heard this from Peter Winkler who heard it from Sergui Hart who does not claim to have invented it.
Alice and Bob play a game (My darling complains that when a math puzzle uses the word game its usually not a fun game. This problem will not be a counterexample.)
There are an infinite number of boxes labelled 1,2,3,....
Alice puts into each box a natural number.
(CLARIFICATION based on a comment- Alice an put any number she wants in any box.
She wants to put 18 in both box 199 and box 3999 she can do that. NO restriction on what
Alice puts in the boxes except that every box has SOME natural number. ALSO- she need not
use all the naturals- if she wants to put a 1 in every box, she can.)
Bob opens all but a finite number of boxes.
For one of the boxes Bob does NOT open he guesses what the number in it is.
They then open that box. If Bob is right, he wins. If not then Alice wins.
Would you rather be Alice or Bob?
Feel free to post thoughts in the comments, though if you want to solve it without help you may want to avoid the comments. I'll post the answer next week.
Two questions: are all the numbers Alice put in the boxes pairwise unique? And does Alice place every natural number in a box, or is she free to use a subset (say, just the odd numbers, or just the primes)?
ReplyDeleteI've added a clarification; however the answer is that Alice can put any number in any box without restriction.
DeleteSince the natural numbers are countably infinite, and since Bob has left only a finite number of boxes, does this mean the only natural numbers not seen yet reside in the unopened boxes? If so, I think Bob can calculate the exact probability of his guess.
ReplyDeleteBob guesses a number he has not already seen.
Bob calculates the probability of his chosen number being in the chosen box as being 1 / (number of unopened boxes).
Well, if the finite number of unopened boxes is arbitrary and left up to Bob, could he not leave only one unopened box and by the above formula have probability of unity for guessing the right answer?
Alice could put a 1 in every box if she wanted to.
DeleteShe need not use all or even most of the numbers.
Very nice problem - it feels like a paradox to me.
ReplyDeleteOn the one hand if Alice i.i.d. randomizes when choosing the natural number in each box, the number from any other box opend should not contain any information about the numbers in boxes not yet opend. This seems to suggest Alice can make her chance of winning arbitrarily close to one e.g. by choosing a sufficiently large number N and then uniformaly and indpendetly chosing random numbers from 1 to N for each box.
On the other hand, using the axiom of choice, an argument along the lines of the solution of the hat problem above seems to go through just fine and Bob can make the probability of winning arbitrarily close to one.
I am looking forward to the solution.
An argument along the lines of the solution of the hat problem above seems to go through just fine but is meaningless because it allows finite errors and this problem is about a finite set of size one.
DeleteThe infinite hats solution does NOT satisfy me.
ReplyDeleteWould any solution of it being possible really satisfy you? :)
DeleteI think I'd rather be Chris. Chris plays fun games with his/her friends.
ReplyDeleteA note about the hat problem: If instead of Axiom of Choice you use a less-commonly investigated Set Theory where all sets are measurable, then the answer reverses: The hat colours can all be drawn independently and uniformly at random, and a probabilistic analysis (which is doable, since now all sets are measurable and hence describable outcomes are events with probabilities) will give you Probability 0 for guessing all but a finite number of hat colours.
ReplyDeleteI read the statement of the problem as follows:
ReplyDelete"There exists Bob-strategy B such that, for all Alice-strategies A, B succeeds."
This is clearly false. Given a fixed Bob-strategy B, one can construct an Alice-strategy to defeat it -- namely, look at the boxes opened by B, see what B's prediction is, and choose to put a different value into the box.
Alternatively, one may ask:
"For all alice-strategies A, there exists a Bob-strategy B that succeeds against A"
But what is the definition of an Alice-strategy in this context? Is it a random distribution on box contents?
I saw this box problem in a logic exam :)
ReplyDeleteHere is the solution (spoiler): Bob fixes once and for all his
representative $r$. Now he splits the boxes into 100 columns, fixes a number $1 \le j \le 100$ and opens all the boxes in the other 99 columns $i \ne j$. For each of those columns $i$, Bob can check at which point $n_i$ his representative coincide with the values of the boxes. Then he asks to open all the boxes in column $j$ except the $max_{i \ne j}(n_i)$ one. He then uses $r$ to guess the value of this box. This strategy wins as long as $n_j \le max_{i \ne j}(n_i)$, so Bob succeeds at least 99% of the time.
In your answer, there are uncountably infinite equivalence classes, so even if players remember all the classes, to match the right representative of the right equivalence class could be uncomputable.
ReplyDeleteAm I right?
Can you actually put a probability measure on that solution though? My suspicion is no, in which case you can't say it's 99% certainty.
ReplyDeleteYes: the probability distribution is on the column that Bob select not to open. If he splits the boxes into m columns, only 1 of them *may* yield a wrong answer, so if he selects the column uniformly he has at least (m-1)/m chance of success. If he select the wrong column then of course we cannot define a probability of success in this case.
DeleteRight, I understood that. I'm still skeptical--I'd need to be convinced you can put a probability measure on which of the columns has the wrong answer. More details in my reply to the subsequent post.
DeleteThe solution to the hat problem does not work.
ReplyDeleteConsider the equivalence class where exactly half
of the people have Red hats and the other half
have Blue hats. (The easiest way to generate this
is by flipping a coin independently each time and
decicde the color of the hat.)
The representative of this class, whoever he maybe,
will differ with an infinite number of participants
by a finite number of hat colors!
This reminded me of a result of Hardin and Taylor (https://www.math.upenn.edu/~ted/203S10/References/peculiar.pdf) that I came across on Steven Landsburg's blog where they use the axiom of choice to show the following:
ReplyDeleteYou are given an arbitrary function f from reals to reals (need not be continuous, differentiable etc; any function). Just an arbitrary function). Now suppose someone gives you the values of f from [-infinity, alpha) and you are supposed to find the value of f(alpha). Can one find hope to find a strategy to predict the value of f at alpha given the values of all beta < alpha?
Thm: [Hardin-Taylor] There exists a strategy such that for an arbitrary function f: R -> R, the number of points alpha where the strategy will yield the wrong answer is countable. In other words, for an arbitrary function f, if the point alpha is chosen uniformly, the strategy outputs the right answer with probability 100%.
The paper actually proves more, and the proof is the most beautiful example of Occam's razor (basically the strategy is just look at the set of all functions that extend the observed values, and answer according to the "smallest" (via well-ordering)).
I felt this puzzle is a weaker form of this theorem but couldn't figure out the solution.