Author |
Topic: Last Man Standing (Read 6299 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Last Man Standing
« on: May 22nd, 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 26th, 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 22nd, 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 23rd, 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 23rd, 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 25th, 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: 13730
|
|
Re: Last Man Standing
« Reply #5 on: May 25th, 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: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..
|
| « Last Edit: May 25th, 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 25th, 2003, 7:36am » |
Quote Modify
|
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.
|
| « Last Edit: May 25th, 2003, 7:37am by phobos » |
IP Logged |
|
|
|
redPEPPER
Full Member
Posts: 160
|
|
Re: Last Man Standing
« Reply #7 on: May 25th, 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 25th, 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 26th, 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 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) = SUMkP(n,k)Ps(k)
SUMk 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) = SUMi<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.
|
| « Last Edit: May 27th, 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: 13730
|
|
Re: Last Man Standing
« Reply #10 on: May 26th, 2003, 11:36pm » |
Quote Modify
|
on May 26th, 2003, 1:13pm, 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
|
|
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 27th, 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 23rd, 2003, 1:49pm » |
Quote Modify
|
on May 25th, 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
|
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: 13730
|
|
Re: Last Man Standing
« Reply #14 on: Jun 24th, 2003, 3:46am » |
Quote Modify
|
on May 26th, 2003, 1:13pm, 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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Last Man Standing
« Reply #15 on: Jun 24th, 2003, 5:58am » |
Quote Modify
|
N(n, n-2) = n(n-1) * 2n-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
|
| « Last Edit: Jun 24th, 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 12th, 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)/(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.
|
|
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 13th, 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: 13730
|
|
Re: Last Man Standing
« Reply #19 on: Nov 14th, 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 17th, 2003, 7:15pm » |
Quote Modify
|
on Nov 13th, 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: 13730
|
|
Re: Last Man Standing
« Reply #21 on: Nov 18th, 2003, 1:06am » |
Quote Modify
|
on Nov 17th, 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 20th, 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 20th, 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 groups1 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 induction2).
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 20th, 2003, 6:27am by Dudidu » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Last Man Standing
« Reply #24 on: Nov 20th, 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?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove