wu :: forums - Print Page


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

        riddles >> hard >> Last Man Standing
        
(Message started by: THUDandBLUNDER on May 22^nd, 2003, 9:35am)

Title: Last Man Standing
Post by THUDandBLUNDER on May 22^nd, 2003, 9:35am

In a roomful of N people each person has a gun with an unlimited supply of ammunition. They are all sure shots. On the count of three, each person shoots a randomly selected person (other than themselves) in the room.
This continues until either everyone is dead or exactly one person is left alive. As N tends to infinity, what is the limit of the probability that exactly one person will survive?

Title: Re: Last Man Standing
Post by jade_conundrum on May 22^nd, 2003, 8:31pm

is the room infinitly large? Because if not then the n amount of people would turn into so much red paste after a while, that is, if the walls don't give out first. Also, what are the penetration power of the bullets? Are they using sniper rifles or BB guns? In addition, given that the room is infinitly large, couldn't the n amount of people position themselves in such a way as to have the bullets never reach their targets?

Title: Re: Last Man Standing
Post by jade_conundrum on May 23^rd, 2003, 7:59pm

Does each person have the same gun? Do they have body armour? Are they smart people? (if so, then maybe they could quickly work out their differences and shoot at a wall with their infinite number of bullets in order to break through and escape; or do the aforesaid positioning thing). Do they all speak the same language?

I am sorry about ruining your puzzle, but one simply must know these facts in order to accurately calculate the probability of their demise. So if you would be so kind as to answer these questions then maybe I could start work upon an answer. Thank you in advance for understanding the plight of your readers.

Title: Re: Last Man Standing
Post by phobos on May 23^rd, 2003, 8:55pm

Just a wild guess...could it be 50%? Because either we have one survivor, or we have none. For any number of survivor > 1, the shooting will continue.

Title: Re: Last Man Standing
Post by redPEPPER on May 25^th, 2003, 5:04am

Jade: I think we're supposed to keep it simple. The riddle says "they are sure shot" which means they never miss. Whoever they will target will die. Assume everybody is seeing everybody else and has a line of fire on each of them. They don't move, they don't talk, they just shoot all at the same time (assume that's possible to synchronize them all). Whoever was targeted dies. And then they do it again with the survivors.

Phobos: either we have one survivor, or we have none. But can you say that these possibilities are equiprobable?

If we have two survivors, they're as good as dead. If we have three, there could be one survivor (p=3/4) or zero (p=1/4) on the next round. With 4 survivors, p=11/27 that there's no survivor after one or two rounds, and p=16/27 that there's one survivor on the next round... And it gets worse from there.

Title: Re: Last Man Standing
Post by towr on May 25^th, 2003, 6:14am

I'm thinking:

ps(n) = probability of there being 1 survivor starting with n

ps(0) = 0
ps(1) = 1
ps(n) = sum(k=1:n-2, p(n,k)*ps(k));

where p(n,k) = probability of there being k survivors after one round with n people (so sum(k=0:n-2, p(n,k)) = 1)

I'm not sure what formula p(n,k) is though..

Title: Re: Last Man Standing
Post by phobos on May 25^th, 2003, 7:36am

Yeah redpepper, I was wrong, the odds would have been anything but 50-50.
But how did you work out the 4-person case? I followed your logic but I can't get p=11/27.

Title: Re: Last Man Standing
Post by redPEPPER on May 25^th, 2003, 4:24pm

I just counted all the possibilities.

I'll take one of them arbitrarily, and name it A. A will shoot at another one, that I will call B. If B shoots at someone else than A, we'll call that person C. If not, C is any of the remaining two chosen arbitrarily. D is the last person. Here are the possible cases from here. A->B means A shoots B.

A->B: p=1
B->A: p=1/3
C->A or C->B: p=2/9
D->A or D->B: p=4/27 => C and D survive. They both die the next round.
D->C: p=2/27 => D survives.
C->D: p=1/9
D->A or D->B: p=2/27 => C survives.
D->C: p=1/27 => no survivor.
B->C p=2/3
C->A: p=2/9=6/27 => D survives.
C->B: p=2/9
D->A: p=2/27 => D survives.
D->B or D->C: p=4/27 => A and D survive. They both die the next round.
C->D: p=2/9
D->A: p=2/27 => no survivor.
D->B or D->C: p=4/27 => A survives.

Total:
no survivor: p=11/27
1 survivor: p=16/27

There's probably a way to generalize or simplify.

Title: Re: Last Man Standing
Post by visitor on May 25^th, 2003, 6:55pm

I wrote a program to check it out, and if I didn't screw it up, it looks like the answer really is .5. At low values the answer goes up and down,
.59 for 4
.47 for 5
.42 for 6
.44 for 7
.49 for 8
.53 for 9
.55 for 10 and 11
dropping back to .45 fo 18
rising to .53 at around 30
Every round of blasting away reduces the number of shooters by a factor of about e, i think, so the final answer for any given n depends somewhat on where it tends to land when it gets down to low double digits. You have to get a pretty high n before that completely disappears (higher than my cheap old basic program would go). But averaging all the results from 100 to 1000 gave me an answer of .500+/-

But what happens when you get an infinite number of men shooting? How do they pick a target, and how many men are left over after one round?

Title: Re: Last Man Standing
Post by Icarus on May 26^th, 2003, 1:13pm

Visitor: I'm not sure whether this is a point of confusion for you, or if you know this well and are simply posting a question which is related to T&B's, but some readers will definitely be confused on the issue, so I will try to clarify it for their sake:

T&B's question only deals with what happens with finite numbers of shooters. The limit as N goes to infinity only expresses the behavior of (using towr's notation) Ps(n) for very large finite values of n. This limit is independent of what happens for n=oo. For that case, the problem description breaks down, as Visitor has indicated. It is impossible to pick from a countable number of choices "entirely at random" - i.e. so that all choices are equally likely. And thus for an infinite situation, the means of picking a target must be more clearly specified before any sort of answer is possible.

Concerning the original finite problem:
towr's formulas (with a few cosmetic alterations - I don't want to bother with tracking summation limits. All sums are over all non-zero values of the summand):
Ps(n) = Probability that when starting with n people, 1 will remain. (any n >= 0)
P(n,k) = Probability that a single round starting with n people will have k survivors. (any n>=0, any integer k).
Ps(0) = 0; Ps(1) = 1
Ps(n) = SUM_kP(n,k)Ps(k)
SUM_k P(n, k) = 1 for every n.
P(n,k) = 0 for k<0 and (for k>n-2 if n>=2).
[edited to correct the error pointed out by towr in the next post.]

The next step is figure out the values of P(n,k). Let N(n,k) be the number of ways of assigning a target to each of n shooters so that there will be k survivors. Each such assignation is equally likely, so P(n,k)=N(n,k)*(n-1)^-n. Number the shooters, to keep track of who is shooting who. I will use C(n,k) = "n choose k" = n!/k!(n-k)!

Consider k=0 first. For everyone to be killed in a single round, targeting must divide the shooters into a number of simple cycles (#1 -> #2 -> #4 -> #1, #3 -> #5 -> #3). Pull off the cycle that #1 belongs to. For each cycle length t, the number of possible cycles of length t containing #1 is the number of possible lists of members for the cycle times the number of ways of arranging those members, starting with #1. I.e. C(n-1,t-1)*(t-1)! = (n-1)!/(n-t)! Since the shooters not in the same cycle with #1 must all kill each other, and making the change i=n-t:

N(n,0) = SUM_i<n-1 ((n-1)!/i!) * N(i,0)
N(0,0)=1, N(1,0)=0

For k>0, there is at least one surviving shooter, WLOG - shooter #1. If the target of #1 is also the target of someone else, then there are N(n-1,k-1) possible target assignations among the other shooters. If #1's target is targeted solely by him, there are N(n-1,k) possible target assignations among the other shooters. Thus

N(n,k) = (k-1)*N(n-1,k) + (n-k)*N(n-1,k-1)

Assuming I haven't made an error somewhere, this provides recursion formulas from which Ps(n) can be calculated.

Title: Re: Last Man Standing
Post by towr on May 26^th, 2003, 11:36pm

on 05/26/03 at 13:13:18, Icarus wrote:

P(n,k) = 0 for k<1 and (for k>n-2 if n>=2).

P(n,k) needn't be 0 if k < 1
P(2,0) = 1 for instance

Title: Re: Last Man Standing
Post by Icarus on May 27^th, 2003, 5:31pm

Thanks! I'm not sure where that "<1" came from.

Title: Re: Last Man Standing
Post by Rujith de Silva on Jun 23^rd, 2003, 1:49pm

on 05/25/03 at 18:55:54, visitor wrote:

I wrote a program to check it out, and if I didn't screw it up, it looks like the answer really is .5. ... But averaging all the results from 100 to 1000 gave me an answer of .500+/-

Visitor: Did your program really try all possibilities? For n people,
there's something like O(n^n) different ways for them to target each
other. That's a VERY LARGE number for n = 1000, which you say your
program handled. Or did it merely do a Monte Carlo simulation? -
Rujith.

Title: Re: Last Man Standing
Post by visitor on Jun 23^rd, 2003, 1:56pm

No, I didn't try every possibility, just played the game randomly and ran it 10,000 times to get a good average.

Title: Re: Last Man Standing
Post by towr on Jun 24^th, 2003, 3:46am

on 05/26/03 at 13:13:18, Icarus wrote:

N(n,k) = (k-1)*N(n-1,k) + (n-k)*N(n-1,k-1)

Assuming I haven't made an error somewhere, this provides recursion formulas from which Ps(n) can be calculated.

N(3,1) is supposed to be 6, but your formula, using
N(2,1)=0 and N(2,0)=1, gives 0*0+ 2*1 = 2

Title: Re: Last Man Standing
Post by towr on Jun 24^th, 2003, 5:58am

N(n, n-2) = n(n-1) * 2^n-3

and the first 6 rows of N(n,k) are
n\k 0 1 2 3 4 5 6 1 0 1 2 1 0 0 3 2 6 0 0 4 9 48 24 0 0 5 44 420 480 80 0 0 6 265 3840 7920 3360 240 0 0

Title: Re: Last Man Standing
Post by SWF on Nov 12^th, 2003, 7:03pm

The result I am getting for this problem is suprising to me: the probability does not reach a limit, but for large N, probability remains between 47% and 53%. The probability oscillates between these two values with a period that increases by a factor of e for each cycle.

The approach of finding an exact probability distribution starting with N=1, quickly gets messy. One simple result turned out to be: probability of N people being reduced to 0 after only 1 round is floor(N!/e+0.5)/(N-1)^N.

A more useful approach is to start with a large N and make some approximations that bound the problem. I will omit the gory details, since nobody seems to read them, but after a few rounds of shooting, the probability distribution for the number of people left is very close to a normal distribution. After k rounds of shooting, the mean of this normal distrubtion is N*exp(-k) and the variance is less than N*exp(-k)*(1-exp(-k)). This is assuming that k is small enough for this value of N such that the probability of the game being over is small.

From the above result, if the mean of this normal distribution is some value, m, the variance will be less than
m*(1-m/N). Start with a very large N, and do many rounds of shooting until m is a relatively small number. For example, I will look at m=18 to make use of the results given visitor. If starting with an N>>18 and after many rounds of shooting m reaches a value of 18, standard deviation would be less than [surd]18=4.2. visitor determined that starting with a value of 18 gives a local minimum probablity of 1 survivor with maximums at 11 and 30. The standard deviation is small compared to the distance between the maximums. Thus, if the mean is 18, the narrow normal distrubtion focuses on the low probabilites and the final probablity of one person standing will be on the low side. Same if the mean after the previous round of shooting was on 18*e=49 or 49*e, ... If N was such that the mean hit visitor's maximum points, like 11 and 30, probability of one person standing would be high.

In summary for large N: if ln(N) is close to an integer, probability of one person left standing will be low: around 47%. If ln(N) is close to halfway between two integers, probability will be high: around 53%. This is also a pretty good approximation for N greater than 20 or so.

Title: Re: Last Man Standing
Post by SWF on Nov 13^th, 2003, 6:29pm

To verify the above calculations I ran a Monte Carlo simulation and plotted probability as a function of ln(N) for up to N=1000000. Seems consistent with the minimums falling near integer values of ln(N), and no limiting value being reached:

Title: Re: Last Man Standing
Post by Icarus on Nov 13^th, 2003, 6:59pm

Looks good! But couldn't you have done this two days ago, before I cleaned out the finished stuff from my list? Now you may have to wait for another month or two before I get around to updating again! :D

Title: Re: Last Man Standing
Post by towr on Nov 14^th, 2003, 1:07am

It'd still be nice to find that formula we were working on.. So it's not all finished yet..
I really ought to take some time to look at this again..

Title: Re: Last Man Standing
Post by SWF on Nov 17^th, 2003, 7:15pm

on 11/13/03 at 18:59:22, Icarus wrote:

Looks good! But couldn't you have done this two days ago, before I cleaned out the finished stuff from my list?

I like to keep one in my back pocket until the time is right. ;D Don't worry, you can include this in next week's update of your list. In the meantime that will give plenty of time to work on lists for the unsolved Easy and Medium riddles.

Towr, the question didn't call for this problem to be solved with a particular method, so why insist on using a difficult approach. Although it would be interesting, to see if it can be done. The formula for probability of no survivors after one round was not especially complex, but the formulas for more survivors rapidly get unwieldy.

Was anybody else surprised by the result that a limit is not reached? In the posts above, even Icarus seemed to refer to a limit, and he is never convinced a limit exists until proven.

Title: Re: Last Man Standing
Post by towr on Nov 18^th, 2003, 1:06am

on 11/17/03 at 19:15:05, SWF wrote:

Towr, the question didn't call for this problem to be solved with a particular method, so why insist on using a difficult approach.

I'm not really insisting, it's just
Quote:

it would be interesting, to see if it can be done.

Besides, it'd be nice to see something I start actually finished for once ;)

Title: Re: Last Man Standing
Post by THUDandBLUNDER on Nov 20^th, 2003, 5:50am

Related question:

There are an odd number of people milling around at random in a field. At a signal each person simultaneously shoots the person nearest to themselves. Prove that there will always remain at least one survivor.

Title: Re: Last Man Standing
Post by Dudidu on Nov 20^th, 2003, 6:23am

on 11/20/03 at 05:50:16, THUDandBLUNDER wrote:

Related question:
There are an odd number of people milling around at random in a field. At a signal each person simultaneously shoots the person nearest to themselves. Prove that there will always remain at least one survivor.

First of all, we can notice that if the number of people is even then there is a possibility that no one survives (e.g. divide them into groups of two people, which each person in each group is closest to its couple).
However, if the number is odd then in any partition of the people into groups¹ there is at least one odd-sized group. Now, it is left to prove that in any odd-sized group there is at least one person that nobody shots at (and this can be proved by induction²).

¹ When I say a group I mean a minimal set of people that every individual in that group shots another individual in the same group.
² I will only show the base case and anyone who wants can do the rest :P - look at the figure below, n=3 (I assume that the number of people > 1 since o/w its trivial) there can not be a case where (w.l.o.g) x shots y, y shots z and z shots x since

x shots y [to] A < B

y shots z [to] C < A

z shots x [to] B < C
[bigto] B < B (contradiction).

Sorry for the ugly (lelijk ;)) figure (if someone wants to replace it, he/she is welcomed).

Title: Re: Last Man Standing
Post by James Fingas on Nov 20^th, 2003, 6:37am

There are exactly N bullets shot, so for everybody to die, each person must be shot with exactly one bullet. Consider the two people who are closest together. They must shoot at each other.

But for everybody to die, nobody else can shoot at either of them. So those people form a "group" as Dudidu says, and we can eliminate them. We will keep eliminating two people at a time, until we get down to just one person left, who cannot shoot at himself, so he must survive.

This analysis breaks down if some people jave two other people "closest" to them, in which case they could all die.

Title: Re: Last Man Standing
Post by frantic on Nov 20^th, 2003, 6:39am

Not in the rare case that all people are standing in a circle with equal distances between the neighbours. At this moment shooters have to choose wether to shoot the right or left neighbour. There's a chance everybody dies, isn't there...?

Title: Re: Last Man Standing
Post by Dudidu on Nov 20^th, 2003, 6:50am

on 11/20/03 at 06:39:05, frantic wrote:

You're right, if all the people are placed on the vertecies of a regular polygon (with n vertices) and they choose randomly in which nearest neighbor to shot, then it is possible that everybody will die :-[.

Title: Re: Last Man Standing
Post by aero_guy on Nov 20^th, 2003, 8:55am

Yeah, I was wondering what you would do if you evenly space all the people around the edge of a circle. Each person has two targets to choose from.