Coins on chess-board puzzle
in [Theory]
|
From: Risto Lankinen on 24 Nov 2009 02:22 On 23 marras, 22:41, Risto Lankinen <rlank...(a)gmail.com> wrote: > In fact, I think 64 squares can accommodate 8 different > states (all four corners plus, say, all mirror images). Mind lapse - forget the thing about mirror images. Rotations should still be doable. - Risto -
From: olivernash on 12 Dec 2009 22:15 Yes indeed that's a good strategy alright. However it raises the question of whether there is a better strategy. I notice that this hasn't been discussed here so maybe people might be interested to see the proof that this is the optimal strategy. I recently wrote a short account of this here: http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/ On Nov 20, 3:08 am, Tim Little <t...(a)little-possums.net> wrote: > On 2009-11-20, Risto Lankinen <rlank...(a)gmail.com> wrote: > > > If he finds his own picture, OK; else he next opens the picture > > having the index of the prisoner portrayed by the previously opened > > one. > > Nicely done. His number will always be part of some cycle. If the > cycle length is 25 or less, he succeeds. Every prisoner has an > individual 50% chance of success, but their chances are very much > correlated. > > > The probability of success is equal to the probability of the > > picture arrangement having a displacement loop at most 25 nodes. > > Intuitively this is about 1/2 . > > The probability of a permutation of size n having a cycle of length > exactly k is 1/k (for k > n/2). So the probability of an overall > success is about 31.7%. > > If the permutation has a cycle of length k > 25, then exactly k > prisoners fail to find their own photo. > > > N.B. if the prisoners are worried about jailer deliberately > > arranging the pictures against their success, they should simply > > randomize their indexes before "playing". > > Yes, making sure to agree on the same shuffling beforehand. > > - Tim
From: Remysun on 9 Jan 2010 12:52 If both prisoners are reasonably assured of seeing the board right away, either a little saliva or cigarette ash on the first one's fingers, or hiding a lighter to heat the coin up with could work.
From: Gilles LAFORME on 8 Feb 2010 10:05
"Remysun" <remysun2000(a)yahoo.com> a �crit dans le message de news: 81a5daf7-e1cc-4b81-b380-9f4f022091bb(a)21g2000yqj.googlegroups.com... > If both prisoners are reasonably assured of seeing the board right > away, either a little saliva or cigarette ash on the first one's > fingers, or hiding a lighter to heat the coin up with could work. |