NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/rec/puzzles/8114

Text File | 1992-12-23 | 2.9 KB | 71 lines

Newsgroups: rec.puzzles
Path: sparky!uunet!usc!sdd.hp.com!hpscit.sc.hp.com!hplextra!hplntx!apollo.hp.com!potamian
From: [e-mail] (Spyros Potamianos)
Subject: Re: Killers & Pacifist (SPOILER)
Sender: [e-mail] (HPL News Posting Service)
Message-ID: <[e-mail]>
Date: Wed, 23 Dec 1992 19:34:59 GMT
Reply-To: [e-mail]
References: <[e-mail]> <[e-mail]>
Organization: Hewlett-Packard Company
Lines: 58

In article <[e-mail]>, [e-mail] (Chris Long) writes:
|> In article <[e-mail]>, Spyros Potamianos writes:
|>
|> > Now the new variation: Everything remains the same, except for a slight
|> > change in the algorithm for selecting the two persons:
|>
|> >     Randomly choose a killer. Then randomly select another person
|> >     (killer or pacifist).
|>
|> Let there be 2k killers, p pacifists.  If you choose to be a killer,
|> P(survival)=1/(2k+1) by symmetry.  If you choose to be a pacifist,
|> P(survival)=1/(k+1) since as before we may ignore any interaction
|> between a killer and a different pacifist, hence we may pretend
|> we are the only pacifist; it's clear now that P=1/(k+1) since
|> we survive iff we don't take part in the first k interactions.
|> --
|> Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
|>
|> "S.B., with an I.Q. of 161, failed to complete his course of study,
|> running away instead with his professor's wife."
|> H. J. Eysenck, _Know Your Own I.Q._

Hm... I tend to disagree... Lets say we have 4 killers and we are the only
pacifist. Then, the chance of surviving the first round is 3/4
(i.e. after the first killer is selected, the second person can either be
me or one of the 3 remaining killers).
Then if we survive the first round,in the second we have 2 killers, and
the chance of survival is 1/2. So, the total probability of survival is
3/4 * 1/2 = 3/8

Here is what I came up with:
Assume that I became a pacifist, and there are '2*K' killers and 'P'
pacifists (*including* myself)
Let a(k,p) be the probability of survival.

The first selected person is always a killer (according to the rules).
The probability of the second person being a killer is:
    (2*k-1)/(p+2*k-1)
The probability of the second person being me is:
    1/(p+2*k-1)
The probability of the second person being another pacifist is:
    (p-1)/(p+2*k-1)

In the first case the game continues with '2*K-2 = 2*(K-1)' killers and
'P' pacifists, in the second we die, and in the thrid we continue with
'2*K' killers and 'P-1' pacifists. So....

    a(k,p) = (2*k-1)/(p+2*k-1) * a(k-1,p) + (p-1)/(p+2*k-1) * a(k, p-1)

We also know that:
    a(0,p) = 1                    /* no killers */
    a(1,1) = 1/2                /* 2 killers and me */
    a(k,1) = (2*k-1)/(2*k) * a(k-1, 1)        /* 2*K killers and me */

I haven't solved this equation though... Can anybody help???

Spyros Potamianos
[e-mail]