Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

My Photo
Location: Toronto, Ontario, Canada

Ask Google.

Contact info
Hacker Emblem Become a Friend of GNOME I Power Blogger
follow me on Twitter
July 2003
August 2003
October 2003
November 2003
December 2003
March 2004
April 2004
May 2004
July 2004
August 2004
September 2004
November 2004
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008
May 2008
June 2008
July 2008
August 2008
October 2008
November 2008
December 2008
January 2009
March 2009
April 2009
May 2009
June 2009
July 2009
August 2009
November 2009
December 2009
March 2010
April 2010
May 2010
June 2010
July 2010
October 2010
November 2010
April 2011
May 2011
August 2011
September 2011
October 2011
November 2011
November 2012
June 2013
January 2014
May 2015
Current Posts
McEs, A Hacker Life
Monday, May 07, 2007
 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.


My solution would be the following.

The man are numbered 1 to 2k so they decided each looks at exactly one box, the one he is numbered.
Then after each one looked they line up from left to right standing in the position of the number they saw in the box. E.g. The one who saw the number 1 will be at the leftmost, than the one who saw number two lines up next etc.

The only flaw is that this means that they don't communicate verbal but through another channel.

if all of the men can tell in which box their number is placed, they win, otherwise they lose.
How they tell that? Is it ordered and do other mens inform when man number x tells in which box his number is placed?
If they really cannot communicate in any way (nothing non-verbally, no change in the distribution of the pieces of paper allowed, no nothing) every person is presented with exactly the same situation. Hard to image that there can exist any kind of strategy in that case. The best solution would be to open half the boxes - with chances of winning course depending on k.

So maybe the are allowed to modify the papers, or their distribution?

Or maybe I just don't get it. :-)
Is 'k' a variable here or does it replace '1000' as I read this I thought you were saying 1 - 2000, not 1-2(variable k).
k is a variable. At the end each reports to a judge or something. No communication, really. And there exists a solution. As I said, this is the kind of puzzle that you try hard to prove wrong, but it isn't.
If everyone looks in all boxes and thus finds the correct box for themselves then the probability of success is 1 - independent of k.

(However note that the number of trials is not independent of k)

ps. I've had a bit to drink so may be missing something obvious!
You missed the fact that there are 2k men/boxes, but each man can look into only k boxes, that is, only half of the boxes.
When reporting the number of the box containing their own number, can they choose the order in which to report to the judge (or whatever) or are they called in a fixed order one by one, and at the first fail the game is lost? Can other prisoners see prisoner number n saying something "I know mine, I'll go now"?
That's a _very_ important detail of the game rule set :)
kitty, "no communication" includes that too. Each one reports to the judge without others seeing/hearing/whatever.
I think I got it after reasoning in terms of lists... but it is horribly counterintuitive, especially because my approximate calculation gives a _huge_ minimal chance of success for k->oo (about 30%)
Nice one, anyway, I'll be talking about it to a few friends of mine :)
About 30% sounds right. The strategy itself is very elegant, but getting a good bound is a bit harder.

I didn't want to give the 30% away at first. It's very surprising though when you find it out.
Post a Comment

Links to this post:

Create a Link

<< Archive
<< Home