I bet you can't solve this sci

10 armed killers convene in a room.
At the word "go" they all simultaneously shoot a random other person.
This is repeated with the survivors until either everyone is dead or only one remains.
What is the probability of each end state?

Other urls found in this thread:

paste.debian.net/plain/917732
paste.debian.net/plain/917739
twitter.com/SFWRedditGifs

50%

either it's the end state or it isn't

there are two different end states retard

Then it's 100% right? 2*50%

just because there are two doesn't mean they have an equal chance. obviously the sum would be 100%, but op's question asks for the chance of each, not the sum

Fucking 5% or something?

> 2 killers
both killed

> 3 killers
50-50

> 4 killers
0 survivor : 1/9
1 survivor : 16/27
2 survivors : 8/27
----
0 survivor : 11/27
1 survivor : 16/27

done with trees, but I guess graph theory can make it easier

Hold on faggots, I'm gonna solve this shit. Should take about 2 hours

you're already going about this the wrong way

im pretty sure 3 people is 1/4 not 1/2

right

care to share your strategy? obviously you can program a monte carlo sim to approximate it but i feel like there has to be some rigorous mathematical way to solve this using combinatorics

The goal is to find the probability that a game beginning with n killers will assume a state with m killers

Then after that it's plug and chug;
A game with 10 killers can proceed to a game with 8,7,6,5,4,3,2,1 or 0 players remaining after the shots are fired. Each outcome has its own associated probability.

If the game goes from 10 to 8 after the first shots, then we can just treat it as a new game which has only 8 players, and calculate the probability that there will be 6,5,4,3,2,1 or 0 survivors in the next state.

The problem is made simpler by the fact that no killer is allowed to commit suicide, and therefore at least 2 players have to die in each round. But it's made more complicated in the fact that there are many different combinations that can lead to the same state in a single round, owed to the fact that you only have to be shot once to die, but can be shot multiple times anyway.

was going to brute force it but that wouldn't solve the problem for n killers and would become exponentially harder as he approached n=10. I would know because I gave up brute forcing it when n=5.

>The problem is made simpler by the fact that no killer is allowed to commit suicide,

It would be much simpler if they could. Some binomial coefficient and it would be over.

Shit, this is interesting.

Anyone has a solution here?

Hold up,
I might just be retarded,
but are we in agreement that the greatest number of possible rounds would be 9 rounds and that always ends in total elimination?
Presuming that the killers must always shoot someone else?

they have to shoot, and no suicide. so, if it simplifies to 2 people, both will die and there will be nobody left.

the greatest possible number of rounds is 5; at least 2 players die each round

For example, in the first round with 10 killers, even if 9 of them all aim at one player, that player has to shoot one of the shooters. So 8 will remain.

In the astronomically low chance that only 2 players die per round each round, the max is 5 rounds.

Update on the general solution: It's really fucking hard to decide what the odds of a killer being shot only once is. I thought it was (1/(n - 1) ((n - 2)/(n - 1))^(n - 2)) but this leads to an indeterminate form when n=2.

So, guys... what's 0^0?

/thread

an answer without explanation is meaningless, and 5% is not correct.

In real life there are more than two outcomes.
If everyone is committed to shoot everyone else, then there are more than one occasion for all to die.In the first round everyone can get paired up, and shoot each other simultaneously, or everyone can shoot the next guy, There may be symmetrical rounds and asymmetrical, of 10 people 3 may die in the first round, then seven people left. also not all guns are made equal. fire rate and projectile energy determine if you can shoot more than one person in the time someone else shoots only one. in that case there are no clear rounds or semi-finals if you like, to the game. in practice 1 is probably more likely. the possibility to use a human shield should also be considered.

well its a good thing this isnt real life then you fucking brainlet

Found the probability of everyone dying: 1/893025

Will be back with probability of 1 person living and my proof

there are only two options, so if you actually have the probability p of everyone dying then the probability of one living is just (1-p), im pretty sure your solution is wrong but im interested to see your logic

my brain was too small to solve this within 2 hours

dont feel bad, it took me much longer than that

Thanks for catching me user. Revised coming soon.

This is an info graphic displaying all possible scenarios of each round.

2 people must be shot every round at the very least, or everyone can be shot. The graph is a continuous string for every possibility.

Since having two people results in 2 deaths it is just the same as ending in zero.

After following through with every possibility and adding up the totals of 2 and 0's; then adding together the total possibilities that end in 1, the results are:

21/55 rounds will end with 1 person left alive

And

34/55 rounds will end in everyone dying.

I apologize for the rediculous fraction I posted earlier

although i appreciate the effort, you are missing something. this answer is incorrect.

cant more than 2 people die per round? and dont different numbers of deaths have different probabilities?

Can't you solve this with Markov chains?

I suppose the graph is confusing. Ten is at the top displaying the number we started.

The numbers at the top of every tree represents one of the possibilities of the # of people left over.

Each of those strings goes all the way down from the possibilities branching off of it to the possibilities off of another.

For example 5 can either result in 3 2 1 or 0. 2 1 and 0 are then counted as finished. 3 then can either become 1 or 0 which are then counted as end results. Every end result possible is shown, and accounted for.

1/11

ok, but you aren't accounting for the fact that some outcomes are more likely than others, due to there being more combinations that result in them, the same way rolling two six sided dice will more likely result in a sum of 7 than 2. It was already established earlier in this thread that in a 3 person scenario, there was a 1/4 chance that everybody dies. you can figure this out using basic logic, but for your model a 3 person scenario is 1/2.

Not really. You could solve it by using markov chains for the 4 and 3 chain sequences if you don't count the "upon itself" possibilities.

Markov chains are better suited for possibilities of movement and likewise situations that can repeat themselves.

If there are 3 people there is a fifty fifty. 2 people die resulting in 1 person alive, or 3 people die resulting in 0 people alive.

The nature of the question is random, meaning that all ending must be accounted for.

I'm not saying that one specific random order of executions is equally likely to every other.
What is true is that once a sequence ends in a 2 1 or 0 it is a possible solution.

The answer comes from the ratio of conclusions that end in 1 to the total #of solutions.
This is the way the likelyhoods were calculated

With two people left its an automatic zero. using that i calculated for 3.
ABC
A>B>B>C> X
A>C>B> X
A>C> B
A>

this is incorrect though, the only way everyone will die in a 3 person scenario is if they each target the guy next to them with no overlap, which will only happen 3/4 of the time. you have to consider the number of combinations that result in these outcomes, not just the outcomes themselves. otherwise, rolling two dice would result in a sum of 7 just as often as they would a sum of 2, even though there are lots of combinations that add up to 7 and only 1+1 adds up to 2. you can run a computer program simulation of this or look up combinatorics if you don't believe me.

unfortunately it does not scale nicely that way, i calculated the chance of everybody dying in a 4 person scenario to be 11/27

Ok I got an idea. i will go to sleep so I won't try now how it works out.

Lets model this with a directed graph. There is a single vertex starting at each node, with a random target.
Given an instance, we are interested in knowing how many nodes have no incomming edge.


What I propose is this :
1 Starting from a node, calculate the probability of forming a cycle of a given length (for all lengths)
2 Start again, except there's now a chance to reach an already made cycle, so stop there
3 Repeat until no more node


I know this is not well put, but I'm pretty sure the solution will have something to do with this.

If you have [math]n[/math] people with [math] n \geq 2 [/math] then the probability for exactly 2 people dieing in the next iteration is:
[eqn] {n \choose 2} \frac{2^{n-2}}{(n-1)^n} [/eqn]

The problem is how to generalize this formula for [math] k [/math] people dieing with [math] k>2 [/math].

To precise a bit :
I propose to do a tree, except you collapse some of the stuff in it to reduce the combinatorial explosion.

A dice roll doesn't fit this decription. It's just not the same problem.

Maybe it does.
10 people in a room are assigned a number 1-10
Everyone has a dice with nine sides that excludes their number.

When their number is rolled they are eliminated. Every side of the die has an equal chance of being rolled meaning everyone has an equal chance of being eliminated.

The dice are replaced every round with a dice with the numbers of the other players left

sorry dude, but it seems like you just dont understand basic combinatorics. you can draw out every possibility for a 3 person scenario and see for yourself. There are two ways that everyone dies, and 6 ways that one person survives, for a 1/4 chance that everyone dies.

For just one round, the probability that exactly k out of n survive to the next round is
[math]p_{n, k} := \binom{n}{k} \frac{(n-k)^k (n-k-1)^{n-k}}{(n-1)^n}[/math]
Now, if we define [math]q_n[/math] to be the probability of ultimately everyone dying if you start with n people, we have the recurrence
[math]q_n = \displaystyle\sum_{k=0}^{n-1} p_{n, k}q_k [/math]

Those formulars are wrong.
If they were correct then you should have
[eqn] \sum_{k=0}^{n-1} p_{n,k} = 1[/eqn]
for all n. But that sum is over 14 for n=10.

I guess you have to separately define [math]p_{1, 0}= 0[/math] and initialize [math]q_0=1[/math]
but then you can just churn out the value of [math]q_10[/math]

Is there a more beautiful or intuitive way to do this? Is there a nicer way to describe the sequence of q?

yeah I goofed

None. They would all die.

i used inclusion exclusion to get this
p(n,m) = C(n,m) sum((-1)^k C(m,k) (m-k-1)^m-k (m-k)^n-m+k, {k,0,m}) / (n-1)n
and then
q(n)=sum(p(n,m) q(n-m), {m,1,n}).

Hi OP, nice question, the answer according to my simulation is approximately 30.3% of the time 0 will remain.

You're welcome to run my script to calculate it yourself or see how I did it here: paste.debian.net/plain/917732

If you have any questions or complaints, please let me know!

PS: here are the values for other inputs:

0 1.0
1 0.0
2 0.499645
3 0.27961
4 0.260745
5 0.30433
6 0.334325
7 0.34125
8 0.32953
9 0.317
10 0.30431
11 0.29825
12 0.29646
13 0.299
14 0.304125

I capped this because it was funny

im not good with coding, so im not sure exactly what your mistake was. but i can tell you for certain your numbers are wrong, starting from 2 people onwards. 2 should be 1.0, 3 should be .25

Good catch m8

Fixed paste.debian.net/plain/917739

Results:
0 1.0
1 0.0
2 1.0
3 0.249915
4 0.407905
5 0.532995
6 0.582875
7 0.56038
8 0.510135
9 0.46912
10 0.44567
11 0.44491
12 0.454415
13 0.474105
14 0.49484

so it was basically 50% all along

answer is:
[math]
0: 28477/45360 \approx 63\%
\\
1: 16883/45360 \approx 37\%
[/math]

don't know the general formula. did it by hand.

So I made a script that finds the probability of each number being left each round, results:

[code]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

2 1 0
3 1/4 3/4 0
4 1/9 16/27 8/27 0
5 11/256 105/256 15/32 5/64 0
6 53/3125 768/3125 1584/3125 672/3125 48/3125 0
7 103/15552 6335/46656 2555/5832 1015/2916 805/11664 7/2916 0
[code]

For 10 survivors I confirmed

[code]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

2 1 0
3 1/4 3/4 0
4 1/9 16/27 8/27 0
5 11/256 105/256 15/32 5/64 0
6 53/3125 768/3125 1584/3125 672/3125 48/3125 0
7 103/15552 6335/46656 2555/5832 1015/2916 805/11664 7/2916 0
[/code]

answer is roughly although programming a monte carlo simulation is somewhat cheating, finding the exact result through a rigorous mathematical formula that works for any n people is much harder.

came pretty close