Author 
Topic: Last Man Standing (Read 4410 times) 

ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Last Man Standing
« on: May 22^{nd}, 2003, 9:35am » 
Quote Modify

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?

« Last Edit: May 26^{th}, 2003, 1:50pm by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



jade_conundrum
Newbie
Gender:
Posts: 12


Re: Last Man Standing
« Reply #1 on: May 22^{nd}, 2003, 8:31pm » 
Quote Modify

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?


IP Logged 



jade_conundrum
Newbie
Gender:
Posts: 12


Re: Last Man Standing
« Reply #2 on: May 23^{rd}, 2003, 7:59pm » 
Quote Modify

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.


IP Logged 



phobos
Newbie
Gender:
Posts: 49


Re: Last Man Standing
« Reply #3 on: May 23^{rd}, 2003, 8:55pm » 
Quote Modify

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.


IP Logged 



redPEPPER
Full Member
Posts: 160


Re: Last Man Standing
« Reply #4 on: May 25^{th}, 2003, 5:04am » 
Quote Modify

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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13596


Re: Last Man Standing
« Reply #5 on: May 25^{th}, 2003, 6:14am » 
Quote Modify

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:n2, 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:n2, p(n,k)) = 1) I'm not sure what formula p(n,k) is though..

« Last Edit: May 25^{th}, 2003, 8:57am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



phobos
Newbie
Gender:
Posts: 49


Re: Last Man Standing
« Reply #6 on: May 25^{th}, 2003, 7:36am » 
Quote Modify

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

« Last Edit: May 25^{th}, 2003, 7:37am by phobos » 
IP Logged 



redPEPPER
Full Member
Posts: 160


Re: Last Man Standing
« Reply #7 on: May 25^{th}, 2003, 4:24pm » 
Quote Modify

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.

« Last Edit: May 25^{th}, 2003, 4:28pm by redPEPPER » 
IP Logged 



visitor
Guest

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?


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Last Man Standing
« Reply #9 on: May 26^{th}, 2003, 1:13pm » 
Quote Modify

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 nonzero 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_{k}P(n,k)Ps(k) SUM_{k} P(n, k) = 1 for every n. P(n,k) = 0 for k<0 and (for k>n2 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)*(n1)^{n}. Number the shooters, to keep track of who is shooting who. I will use C(n,k) = "n choose k" = n!/k!(nk)! 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(n1,t1)*(t1)! = (n1)!/(nt)! Since the shooters not in the same cycle with #1 must all kill each other, and making the change i=nt: N(n,0) = SUM_{i<n1} ((n1)!/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(n1,k1) possible target assignations among the other shooters. If #1's target is targeted solely by him, there are N(n1,k) possible target assignations among the other shooters. Thus N(n,k) = (k1)*N(n1,k) + (nk)*N(n1,k1) Assuming I haven't made an error somewhere, this provides recursion formulas from which Ps(n) can be calculated.

« Last Edit: May 27^{th}, 2003, 5:28pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13596


Re: Last Man Standing
« Reply #10 on: May 26^{th}, 2003, 11:36pm » 
Quote Modify

on May 26^{th}, 2003, 1:13pm, Icarus wrote: P(n,k) = 0 for k<1 and (for k>n2 if n>=2). 
 P(n,k) needn't be 0 if k < 1 P(2,0) = 1 for instance


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Last Man Standing
« Reply #11 on: May 27^{th}, 2003, 5:31pm » 
Quote Modify

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


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Rujith de Silva
Newbie
Gender:
Posts: 22


Re: Last Man Standing
« Reply #12 on: Jun 23^{rd}, 2003, 1:49pm » 
Quote Modify

on May 25^{th}, 2003, 6:55pm, 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.


IP Logged 



visitor
Guest


Re: Last Man Standing
« Reply #13 on: Jun 23^{rd}, 2003, 1:56pm » 
Quote Modify
Remove

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


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13596


Re: Last Man Standing
« Reply #14 on: Jun 24^{th}, 2003, 3:46am » 
Quote Modify

on May 26^{th}, 2003, 1:13pm, Icarus wrote:N(n,k) = (k1)*N(n1,k) + (nk)*N(n1,k1) 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


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13596


Re: Last Man Standing
« Reply #15 on: Jun 24^{th}, 2003, 5:58am » 
Quote Modify

N(n, n2) = n(n1) * 2^{n3} 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

« Last Edit: Jun 24^{th}, 2003, 6:00am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



SWF
Uberpuzzler
Posts: 879


Re: Last Man Standing
« Reply #16 on: Nov 12^{th}, 2003, 7:03pm » 
Quote Modify

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)/(N1)^{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)*(1exp(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*(1m/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.


IP Logged 



SWF
Uberpuzzler
Posts: 879

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:


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Last Man Standing
« Reply #18 on: Nov 13^{th}, 2003, 6:59pm » 
Quote Modify

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!


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13596


Re: Last Man Standing
« Reply #19 on: Nov 14^{th}, 2003, 1:07am » 
Quote Modify

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..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



SWF
Uberpuzzler
Posts: 879


Re: Last Man Standing
« Reply #20 on: Nov 17^{th}, 2003, 7:15pm » 
Quote Modify

on Nov 13^{th}, 2003, 6:59pm, 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. 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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13596


Re: Last Man Standing
« Reply #21 on: Nov 18^{th}, 2003, 1:06am » 
Quote Modify

on Nov 17^{th}, 2003, 7:15pm, 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


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Last Man Standing
« Reply #22 on: Nov 20^{th}, 2003, 5:50am » 
Quote Modify

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.


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



Dudidu
Full Member
Posts: 227

on Nov 20^{th}, 2003, 5:50am, 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^{1} there is at least one oddsized group. Now, it is left to prove that in any oddsized group there is at least one person that nobody shots at (and this can be proved by induction^{2}). ^{1} 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. ^{2} I will only show the base case and anyone who wants can do the rest  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). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed). Sorry for the ugly (lelijk ) figure (if someone wants to replace it, he/she is welcomed).

« Last Edit: Nov 20^{th}, 2003, 6:27am by Dudidu » 
IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Last Man Standing
« Reply #24 on: Nov 20^{th}, 2003, 6:37am » 
Quote Modify

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.


IP Logged 
Doc, I'm addicted to advice! What should I do?



