PUZZLE: Group Strategy
Coming back from Montreal yesterday, Peyman
told me the following puzzle which is probably the coolest of its kind I've ever heard. Quite the like that you try hard proving to be wrong first. Anyway:
(I first tried to write it down as prisoners and all, but gave up. Here it goes bare:)
There are 2k men numbered 1 to 2k. And a room with 2k boxes inside (also numbered 1 to 2k), and each man's number is written on a paper and placed in one of the boxes, such that every box has a number in it and the distribution is uniform.
Now there is a game (trial, whatever): each man goes into the room, opens and sees the number inside k of the boxes of his choice, and comes out, altering nothing in the room, and not communicating with anyone during the experience. Before the game starts the men have a chance to develop a strategy, but other than that they can't communicate at all. Anyway, after everyone has visited the room, if all
of the men can tell in which box their number is placed, they win, otherwise they lose.
Show that the men can develop a strategy with a expected winning probability that is not less than a positive constant regardless of k.