wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> 3 logicians and 8 stamps
        
(Message started by: Altamira_64 on Jan 22^nd, 2012, 7:00am)

Title: 3 logicians and 8 stamps
Post by Altamira_64 on Jan 22^nd, 2012, 7:00am

Three logicians and one moderator have decided to play a game. The moderator has a set of 8 stamps, of which 4 are red and 4 are black. He affixes two stamps to the forehead of each logician so that each of them can see all the other stamps except those two in the moderator's pocket and the two on his or her own head. He then asks them in turn if they know the colors of their own stamps. Target of the game is to have at least one of the logicians guess the correct colours of his own dots (and of course explain his reasoning). If the 1st player does not know the answer, the 2nd is asked and then the 3rd, then 1st again etc (1-2-3-1-2-3 etc).
Before the beginning of the game, the first logician is asked to which of the 3 positions he wants to sit. What should be his choice and why?

Title: Re: 3 logicians and 8 stamps
Post by towr on Jan 22^nd, 2012, 12:40pm

[hide]First player wins 18 out of 70 times, second player 42 out of 70, third wins 10 out of 70. So it's best to be second player, provided the stamps are assigned randomly.

You can find it fairly easily by applying a possible worlds model (attached); the lines connect worlds that a player can't distinguish between. So each round the player knows when he's in a given world if it doesn't have any outgoing lines of his color (and the game stops with a win for him). This way you can eliminate worlds each rounds, and the problem becomes easier for the next player.
In the fifth round, the second (blue) player knows which of the remaining worlds he's in; these represent 40 out of 70 possible games (because red-black and black-red are equivalent those games map to the same world).[/hide]

[edit]Updated attachment; now with improved symmetry.[/edit]

Title: Re: 3 logicians and 8 stamps
Post by Altamira_64 on Jan 23^rd, 2012, 9:34am

Well, I am not very familiar with the "worlds" approach, so please, could you explain a bit more?
Also, where do the 70 times come from??
Thanks!!!

Title: Re: 3 logicians and 8 stamps
Post by towr on Jan 23^rd, 2012, 11:02am

There are 70 ways to arrange 4 red and 4 black dots. This is 8!/4!/4! (Where 4! = 4*3*2*1)

However, for the logicians it's equivalent to their thinking if they see someone with black and red, or someone with red and black. So that means there are fewer distinct worlds/states, only 19 in fact, but at the same time the probabilities of each world are not equal (so e.g. BR,BR,BR,BR has a probability of 16/70, because you can switch the B and R in each group, but BB,BB,RR,RR has probability 1/70).
In the image (pdf) in my previous post the small number in parenthesis gives the number of arrangements the world represents (so dividing it by 70 gives you the probability).

I've made a number of slides here (http://towr.home.fmf.nl/stampspuzzle_slides.pdf) which show how the different rounds change the possible-worlds model. As rounds pass, knowledge propagates and fewer worlds remain "possible". At each point you can see who in which world should be able to deduce the stamps on his head (because there is no line of his color to another world, i.e. that world is distinguishable from all the others to him).

An interesting twist might be to actually let the logicians guess as well, so even if they don't know, they may be right with some probability. The model can accommodate that as well, but it's a bit more work.

Title: Re: 3 logicians and 8 stamps
Post by Altamira_64 on Jan 23^rd, 2012, 10:52pm

Many thanks towr!
Now it's clear!