Coins on chess-board puzzle
in [Theory]
|
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen on 20 Nov 2009 10:07 Tim Little <tim(a)little-possums.net> writes: > On 2009-11-18, Torben �gidius Mogensen <torbenm(a)pc-003.diku.dk> wrote: >> The prisoners will be told about the procedure beforehand and can agree >> on a strategy, but once the procedure starts, they can not communicate. >> >> What strategy can the prisoners use to maximize their survival chance, >> and how big can they make this chance? > > When you say that prisoners can turn over 25 cards, can they re-order > the cards they turn over or must the cards be turned over in place? They must stay in place. Torben
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen on 20 Nov 2009 10:12 Risto Lankinen <rlankine(a)gmail.com> writes: > On 18 marras, 14:48, torb...(a)pc-003.diku.dk (Torben �gidius Mogensen) > wrote: >> >> There are 50 prisoners and one jailer. �You can assume that the >> prisoners have been jailed together for a while, so they know each other >> by name and face. > > Assuming all names are unique they are easily indexed > with a running number. > >> The jailer has photos of all 50 prisoners, which he will lay out >> randomly face down in a row on a table. > > Again, row positions are easily indexed with a number. > >> Now, each prisoner will in turn be called in and be allowed to turn over >> 25 photos. �When he has done so, he is led to another room and the >> jailer will turn over the face-up photos again (without altering their >> order) so all are face-down again. �He then calls in the next prisoner >> and repeats the procedure untill all prisoners are moved into the other >> room. > > Each row position R has the picture of prisoner P. Each > prisoner starts by revealing the picture having their own > index i.e. R = P. 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. This he repeates > until he finds his own picture or hits the limit of 25 > attempts. This is, indeed, the solution I was thinking of. > 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 . As Tim noted, it is somewhat smaller than that, but still much larger than most expect. Torben
From: Eric Sosman on 20 Nov 2009 14:13 Tim Little wrote: > On 2009-11-20, Risto Lankinen <rlankine(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. I think you mean "exactly k prisoners are less than certain to find their own photos." Even if all the cards are in one cycle of length k = 50, each prisoner finds his own photo if he starts with any photo not more than 24 places before his own. So even in this extreme case each prisoner has a 25/50 chance of finding his own photo. -- Eric Sosman esosman(a)ieee-dot-org.invalid
From: Andrew B. on 20 Nov 2009 17:54 On 20 Nov, 19:13, Eric Sosman <esos...(a)ieee-dot-org.invalid> wrote: > Tim Little 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. > > I think you mean "exactly k prisoners are less than certain > to find their own photos." Even if all the cards are in one > cycle of length k = 50, each prisoner finds his own photo if > he starts with any photo not more than 24 places before his > own. So even in this extreme case each prisoner has a 25/50 > chance of finding his own photo. No, because by design they're each starting at the worst possible point of the cycle.
From: Tim Little on 20 Nov 2009 18:09
On 2009-11-20, Eric Sosman <esosman(a)ieee-dot-org.invalid> wrote: > Even if all the cards are in one cycle of length k = 50, each > prisoner finds his own photo if he starts with any photo not more > than 24 places before his own. An easy way to see that this cannot be true is to consider which photo they would turn immediately after their own. - Tim |