Solution to the Alice-Bob-Box problem.

In my last blog I solved one problem and asked another (when will it end!).  Damien Roberts provided an answer in the comments to the last blog, so kudos to Damien! I summarize the question asked and answer it (same answer as Damien, though more long winded)  and then some comments and further questions.

Peter Winkler told me this problem at the Joel Spencer 70th Bday conference.  He got it from Sergui Hart who does not claim to be the inventor of it.

PROBLEM:
Alice and Bob play the following (non-fun) game:

Alice puts natural numbers in the boxes 1,2,3,4,... She can put any number in any box. She can put the number 12 in two boxes. She can refuse to put primes in any box. The world is her burito!

Bob opens all but a finite number of  boxes. He chooses one of the boxes that is NOT opened and guesses what is in it and then opens it.  If his guess is correct he wins! (not clear what he wins, but he wins).If not he is, as one of our candidates for prez would say, a LOOOOOOOSER.

Would you rather be Alice or Bob?
END OF PROBLEM

(Added Later- below is an answer that I believe to be correct. Some people disagree. See some of the comments below and also the comments on this)

ANSWER:
I would rather be Bob:

As you might have guessed, Bob takes the set of all infinite sequences of natural numbers and looks at the equivalence x==y iff x and y differ on only a finite number of positions. He then picks a representative from each part of the induced partition.

(When I tried to solve the problem thats as far as I got. Some commenters thought that was the solution, or the solution was obvious from that point. I don't see how.)

Here is what Bob does;

STEP 1: (I used to have Bob takes a random perm of the naturals and relabels the boxes but commenters pointed out that this was not needed and might not even make sense. So there is no Step 1, but I keep
it in case someone sees this post and wonders what happened to step 1.)

STEP2: Bob rearranges the boxes into (say) 100 rows.  We'll say

ROW1: BOXES: 1,101,201,301,...

ROW2: BOXES: 2,102,202,302,...
...
ROW100: BOXES: 100,200,300,...

STEP3: Bob picks a Row AT RANDOM (second use of probability). We will say ROW8:

STEP4: Bob opens the boxes in all of the rows EXCEPT ROW8 (he will open some in ROW8 later). For each Row i NE 8 he does the following:

ROWi is in one of the parts of the partition. Bob had ahead of time chosen a representative in that part. Let x(i) be such that from the x(i)th element on ROWi and the Representative AGREE.

Let x  = max of the x(i).

So, for all rows i NE 8, if you look past the xth position, ROWi and the represenative for that equivalance class are the same.

STEP5: Bob opens up, in ROW8, the boxes x+2, x+3,...

STEP6: Bob knows the part that ROW8 is in the partition. Bob looks at the representative. Bob guesses that the number in box x+1 of ROW8 is the same as the number in the (x+1)th position of the representative.

WHY is this a good idea?

Consider ROWi. Let x(i) (as above) be such that past x(i) ROWi agrees with its rep. In order for the guess to be wrong you would need x(8) > all other x(i). How likely is that? Since we began with a random perm, the prob that x(8) is the largest (for that matter, the prob that any particular i_o has max x(i_0) ) is 1/100. So Bob wins with prob 1- 1/100

Bob can do even better with 1000 rows or 10,000 rows, etc. For any eps>0 he can make the prob that he'll win 1-eps.
END OF ANSWER

One issue I've been trying to get at in this post and the last one was, is this a real solution? I think so, but some students don't like it. Even those that understand it. What do you think?

There is no deterministic solution to the Alice-Bob-Box problem since if the adversary knows what box Bob will guess he can make it so that Bob gets it wrong.

Some asked if there was a computable solution. For both the infinite-hats problem and the box-problem if the players have a strategy depending on only a finite number of inputs they can't win. There are ways to measure the complexity of a strategy and it would be interesting to get upper and lower bounds on the complexity of a strategy. And one can look at the following: If the adversary's strategy is of complexity BLAH then what complexity do the players need to beat it?

Also, in both games AC is used by the players. Eddie Fisher pointed out that if you toss out AC and instead have the AC AM (all sets are measurable) then the Adversary wins the hat game. Not sure about the box game.  One can look at what happens in various axiom systems.

So many open questions, so little time!