Killville - The ultimate Survivor game

[bonanova]

Subtle variation on the

You are transferred to Killville, by your employer, for a one-year temporary assignment.

Its population comprises 10 Killers and 10 Pacifists.

A Killer immediately guns down any other person he meets.

A pacifist never harms a soul.

When you arrive at Killville, you are required to register, either as a Killer or as a Pacifist.

If you register as a Killer, you are issued a gun and required to act as a Killer.

If you register as a Pacifist, you are given the town's best wishes for good luck and advised to careful.

You desire to live long and prosper. Which way do you register?

Assume all encounters are 1-on-1 and random.

Use spoilers please.

[jim]

As long as the process reaches completition within the year--or as long as the probability of A meeting B in a short interval of time does not depend on how many other people there are (a kind of Ideal Gas Law) your chances of survival are the same whether you chose to be a killer or a pacifist. That is because the only encounters that matter for you are when two killers meet, or when a killer meets you. Whether a pacifist dies when meeting you are not is irrelevant to your survival.

[mmiguel]

Subtle variation on the

You are transferred to Killville, by your employer, for a one-year temporary assignment.

Its population comprises 10 Killers and 10 Pacifists.

A Killer immediately guns down any other person he meets.

A pacifist never harms a soul.

When you arrive at Killville, you are required to register, either as a Killer or as a Pacifist.

If you register as a Killer, you are issued a gun and required to act as a Killer.

If you register as a Pacifist, you are given the town's best wishes for good luck and advised to careful.

You desire to live long and prosper. Which way do you register?

Assume all encounters are 1-on-1 and random.

Use spoilers please.

I think the main difference here is that you are the 11th person for whatever group you decide to be in.

I notice that when you register as a pacifist, you are not required to act like a pacifist (the promise they make registered killers make), but I think that this problem likely has more depth in its true solution than just this - not sure if this can even offer you much of an advantage any way.

I'll assume after you register, the game proceeds like the last problem, except there are now 11 people in your group and 10 in the other.

The only real way to survive is if all the killers kill each other (other than you) without any of them meeting you.

How to model the randomness of these meetings?

Assume each valid configuration of pairings is equally likely in each round.

What if there are an odd number of people?

Then I guess one person doesn't meet with anyone.

First assume n is even.

Number of possible pairings is given by multinomial formula (divided by (n/2)! to make ordering of pairings not matter):

n!/((n/2)!2!*2!*2!...)

where there are n/2 many 2!s on the bottom, and (n/2)! i.e.

n!/(2^(n/2)*(n/2)!)

If there are k killers (excluding you) of those n, then the chance of you meeting with one of them is....

well, how many possible ways can you meet with a killer?

need to choose 1 of the k killers

k possibilities for that

The other pairings need to happen now. The rest of the folks now number n-2 and there should be n/2-1 pairings now.

The probability of you dying is therefore

k*(n-2)!/((n/2-1)!2^(n/2-1))/(n!/((n/2)!2^(n/2)))

This simplifies to:

k/(n-1)

This is the chance of you meeting a killer.

The chance of you surviving is one minus this.

1 - k/(n-1)

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

In the beginning, n = 21 and k=10, which gives you a 11/21 ~ 0.52 chance of surviving the first round.

The way you register does not affect your survival chances on the first round (k excludes you, so numerically your choice changes nothing).

Also, if you are a killer, it won't really help you, since you only get the opportunity to kill when you are dying.

In either case, your only hope is to never touch a killer.

If you are a killer and that happens, then each round you were either an odd man out or you killed some pacifists each round.

Are you better off with more pacifists or less pacifists?

Well, if we believe that at each round, if there are n people, the probability of you surviving is

given above, then it is better to have more pacifists around, since those equations increase with n (positive derivative).

Therefore, you don't want to kill pacifists, because they are protecting you by taking bullets for you.

You therefore want to be a pacifist to maximize the number of people who can take bullets for you in the hopes that the killers all kill eachother and other pacifists before ever meeting you.

Answer: Pacifist

Edited September 6, 2012 by mmiguel

[mmiguel]

I think the main difference here is that you are the 11th person for whatever group you decide to be in.

I notice that when you register as a pacifist, you are not required to act like a pacifist (the promise they make registered killers make), but I think that this problem likely has more depth in its true solution than just this - not sure if this can even offer you much of an advantage any way.

I'll assume after you register, the game proceeds like the last problem, except there are now 11 people in your group and 10 in the other.

The only real way to survive is if all the killers kill each other (other than you) without any of them meeting you.

How to model the randomness of these meetings?

Assume each valid configuration of pairings is equally likely in each round.

What if there are an odd number of people?

Then I guess one person doesn't meet with anyone.

First assume n is even.

Number of possible pairings is given by multinomial formula (divided by (n/2)! to make ordering of pairings not matter):

n!/((n/2)!2!*2!*2!...)

where there are n/2 many 2!s on the bottom, and (n/2)! i.e.

n!/(2^(n/2)*(n/2)!)

If there are k killers (excluding you) of those n, then the chance of you meeting with one of them is....

well, how many possible ways can you meet with a killer?

need to choose 1 of the k killers

k possibilities for that

The other pairings need to happen now. The rest of the folks now number n-2 and there should be n/2-1 pairings now.

The probability of you dying is therefore

k*(n-2)!/((n/2-1)!2^(n/2-1))/(n!/((n/2)!2^(n/2)))

This simplifies to:

k/(n-1)

This is the chance of you meeting a killer.

The chance of you surviving is one minus this.

1 - k/(n-1)

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

In the beginning, n = 21 and k=10, which gives you a 11/21 ~ 0.52 chance of surviving the first round.

The way you register does not affect your survival chances on the first round (k excludes you, so numerically your choice changes nothing).

Also, if you are a killer, it won't really help you, since you only get the opportunity to kill when you are dying.

In either case, your only hope is to never touch a killer.

If you are a killer and that happens, then each round you were either an odd man out or you killed some pacifists each round.

Are you better off with more pacifists or less pacifists?

Well, if we believe that at each round, if there are n people, the probability of you surviving is

given above, then it is better to have more pacifists around, since those equations increase with n (positive derivative).

Therefore, you don't want to kill pacifists, because they are protecting you by taking bullets for you.

You therefore want to be a pacifist to maximize the number of people who can take bullets for you in the hopes that the killers all kill eachother and other pacifists before ever meeting you.

Answer: Pacifist

"

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

"

should be

1/n + (k/n)*(1-(k-1)/(n-2)) + (n-k-1)/n*(1-k/(n-2))

need to account for odd man out being killer.

also denominator should be n-2, which is what i originally had before, but changed due to nonsensical answers for k=0 and/or k=20, without figuring out exactly what was wrong.

this simplifies to

(n-k)/n = 1 - k/n

amazingly

So survival if n is even is:

1 - k/(n-1)

survival if n is odd is:

1 - k/n

Conclusion from before remains the same.

Chance of surviving first round is still 11/21

haha, intuition could have given those probabilities from the beginning, but i tend to be paranoid with probability, and not try to go by intuition, unless problems are very simple.

Edited September 6, 2012 by mmiguel

[ujjagrawal]

Register as KILLER

Then you will have atleast 1/11 chance of surviving and prosper killing the other Pacifists.

Otherwise if you register yourself as Pacifist then surely all killers will kill themselves and your chances of surviving will depends solely on your luck.

[emeraldfyr3]

I would just quit my job.

[phil1882]

personally i think

either way works.

if you're a pacifist, that makes 11 pacifists, and 10 killers, making it possible, all-be-it unlikely that all the killers will kill

themselves off, while still leaving some pacifists. if you're a killer, that makes 11 killers and 10 pacifists. meaning 1 killer is guaranteed to survive.

[Saxguy01]

The only way to survive is to be a killer. As the prompt says, killers immediately shoot anyone they meet. The only way two killers would end up simultaneously killing each other is if they simultaneously shoot each other (the old Wild West Gunslinger scene), an unlikely situation in any context. Barring that, 1 killer will survive (all the others having been killed by the other killers).

Edited September 6, 2012 by Saxguy01

[jim]

Saxguy....Realistically you are correct--but in the original version of the problem it was specifically stated that both killers die when they meet each other.

[mmiguel]

I think the main difference here is that you are the 11th person for whatever group you decide to be in.

I notice that when you register as a pacifist, you are not required to act like a pacifist (the promise they make registered killers make), but I think that this problem likely has more depth in its true solution than just this - not sure if this can even offer you much of an advantage any way.

I'll assume after you register, the game proceeds like the last problem, except there are now 11 people in your group and 10 in the other.

The only real way to survive is if all the killers kill each other (other than you) without any of them meeting you.

How to model the randomness of these meetings?

Assume each valid configuration of pairings is equally likely in each round.

What if there are an odd number of people?

Then I guess one person doesn't meet with anyone.

First assume n is even.

Number of possible pairings is given by multinomial formula (divided by (n/2)! to make ordering of pairings not matter):

n!/((n/2)!2!*2!*2!...)

where there are n/2 many 2!s on the bottom, and (n/2)! i.e.

n!/(2^(n/2)*(n/2)!)

If there are k killers (excluding you) of those n, then the chance of you meeting with one of them is....

well, how many possible ways can you meet with a killer?

need to choose 1 of the k killers

k possibilities for that

The other pairings need to happen now. The rest of the folks now number n-2 and there should be n/2-1 pairings now.

The probability of you dying is therefore

k*(n-2)!/((n/2-1)!2^(n/2-1))/(n!/((n/2)!2^(n/2)))

This simplifies to:

k/(n-1)

This is the chance of you meeting a killer.

The chance of you surviving is one minus this.

1 - k/(n-1)

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

In the beginning, n = 21 and k=10, which gives you a 11/21 ~ 0.52 chance of surviving the first round.

The way you register does not affect your survival chances on the first round (k excludes you, so numerically your choice changes nothing).

Also, if you are a killer, it won't really help you, since you only get the opportunity to kill when you are dying.

In either case, your only hope is to never touch a killer.

If you are a killer and that happens, then each round you were either an odd man out or you killed some pacifists each round.

Are you better off with more pacifists or less pacifists?

Well, if we believe that at each round, if there are n people, the probability of you surviving is

given above, then it is better to have more pacifists around, since those equations increase with n (positive derivative).

Therefore, you don't want to kill pacifists, because they are protecting you by taking bullets for you.

You therefore want to be a pacifist to maximize the number of people who can take bullets for you in the hopes that the killers all kill eachother and other pacifists before ever meeting you.

Answer: Pacifist

man... nobody agrees with me lol

[Rob_Gandy]

completely irrelelvant.

(Assuming that when I leave the town the only possible meetings left involve no deaths and all meetings occur one at a time.)

No matter which I choose to be I have about a 9% chance of surviving. That is without counting any meeting that didn't involve me or a killer dying. Because none of the other meetings affect my chance of surviving at the end.

Basically it comes down to me vs. killers. Whether I'm a killer or a pacifist I cannot meet a killer or else I die.

So I need there to be 5 meetings of killers for me to survive. For each set of possible meetings, that count, my chance of survival is (n-1)/(n+1) where n is the number of killers left that aren't me. Which gives us...

9/11 * 7/9 * 5/7 * 3/5 * 1/3 = 1/11 or .0909... or 9.0909...%

And that is my take on it.

[mmiguel]

completely irrelelvant.

(Assuming that when I leave the town the only possible meetings left involve no deaths and all meetings occur one at a time.)

No matter which I choose to be I have about a 9% chance of surviving. That is without counting any meeting that didn't involve me or a killer dying. Because none of the other meetings affect my chance of surviving at the end.

Basically it comes down to me vs. killers. Whether I'm a killer or a pacifist I cannot meet a killer or else I die.

So I need there to be 5 meetings of killers for me to survive. For each set of possible meetings, that count, my chance of survival is (n-1)/(n+1) where n is the number of killers left that aren't me. Which gives us...

9/11 * 7/9 * 5/7 * 3/5 * 1/3 = 1/11 or .0909... or 9.0909...%

And that is my take on it.

Let's say there were 2 killers left, and 100,000 pacifists (I know, can't be more than 10 -- have patience).

Do you really think your chances of dying here are

(2-1)/(2+1) = 1/3?

Of all the other people out there they could kill, why would the killers be so likely to kill you?

Answer:

Because your chance of dying is not (n-1)/(n+1), but depends on number of non-killers out there too.

[bonanova]

Let's say there were 2 killers left, and 100,000 pacifists (I know, can't be more than 10 -- have patience).

Do you really think your chances of dying here are

(2-1)/(2+1) = 1/3?

Of all the other people out there they could kill, why would the killers be so likely to kill you?

Answer:

Because your chance of dying is not (n-1)/(n+1), but depends on number of non-killers out there too.

How many initial pacifists would there have to have been for there to be only 100,000 pacifists remaining when the killers numbered but two? What are your chances of being among those 100,000?

Actually, what if the puzzle had said Killville has K (an even number) killers and P pacifists when you arrive. You may join the killers, and act like one, or you may join the pacifists and remain unarmed. Which party would get your vote?

BTW, RG is correct to observe that your survival can be defined as follows: among the six events, KK, KK, KK, KK, KK, K-you, the K-you event must happen last. That is, be impossible.

How do the other events (K-other pacifists) affect you or thin outthe killers?

[Rob_Gandy]

Let's say there were 2 killers left, and 100,000 pacifists (I know, can't be more than 10 -- have patience).

Do you really think your chances of dying here are

(2-1)/(2+1) = 1/3?

Of all the other people out there they could kill, why would the killers be so likely to kill you?

Answer:

Because your chance of dying is not (n-1)/(n+1), but depends on number of non-killers out there too.

And yes I do still think that my chances of survival are still 1/3 in that situation.

My chance of dying in any given encounter does depend on the total number of people, but, if we are thinking end game, it doesn't matter to my final survival what happens to those 100,000 pacifists. My survival depends on the two killers meeting each other before one of them meets me. So the only meetings that affect my survival are (K1,K2), (K1,Me) and (K2,Me). So based on those meetings I have a 1/3 chance or survival.

I worked under the assumption that there comes a point where either there is a single killer left or no killers and some number of pacifists and thus no more meetings are important. And that meetings occur one at a time.

Also, I only considered meetings that affected my survival as important and thats how I came up with (n-1)/(n+1).

Am I on the right track or way off?

Edit:In red.

Edited September 7, 2012 by Rob_Gandy

[mmiguel]

How many initial pacifists would there have to have been for there to be only 100,000 pacifists remaining when the killers numbered but two? What are your chances of being among those 100,000?

In short, what if the puzzle had said Killville has K (an even number) killers and P pacifists when you arrive. You may join the killers, and act like one, or you may join the pacifists and remain unarmed. Which party would get your vote?

BTW, RG is correct to observe that your survival can be defined as follows: among the six events, KK, KK, KK, KK, KK, K-you, the K-you event must happen last.

Other events (K-other pacifists) can transpire at any time. They don't harm you, but they don't decrease the killer population either.

chances of survival are probably not very high either way.

but, i showed mathematically in a prior post (unless someone finds a flaw in my reasoning, which is of course very possible), that the chance of surviving a single encounter (assuming everyone is paired together in such an encounter, with the exception of maybe one odd man out), increases as the total number of pacifists increase while the number of killers remain the same.

it is thus in your best interest to make any possible decision you can to result in as many pacifists being alive in each round as possible.

it's like the evolutionary strategy of a school of fish - band together so that although the chances of a shark getting a meal are large, within the school itself, the likelihood of any particular fish getting eaten in a single shark encounter decreases.

being a killer erodes your "protection" faster.

you may likely die either way, but you have a slightly better chance of surviving if you don't kill others, letting them live in order to take a bullet for you later in the future.

Pacifist

[bonanova]

And yes I do still think that my chances of survival are still 1/3 in that situation.

My chance of dying in any given encounter does depend on the total number of people, but, if we are thinking end game, it doesn't matter to my final survival what happens to those 100,000 pacifists. My survival depends on the two killers meeting each other before one of them meets me. So the only meetings that affect my survival are (K1,K2), (K1,Me) and (K2,Me). So based on those meetings I have a 1/3 chance or survival.

I worked under the assumption that there comes a point where either there is a single killer left or no killers and some number of pacifists and thus no more meetings are important.

Also, I only considered meetings that affected my survival as important and thats how I came up with (n-1)/(n+1).

Am I on the right track or way off?

Yes. See my spoiler above.

In the general case I alluded to above, with K (even) killers and P pacifists, P/ (K+1) pacifists survive on average. If K is odd, no pacifists survive.

When K=P=10 initially, by joining the pacifists you make P=11, and on average 1 pacifist can attend the killers' funerals. You have 1/11 chance of being that survivor.

If you join the killers, you make K=11 (odd) so it is certain that exactly1 killer is standing at the end. He wipes out any pacifists still breathing when killers 9 and 10 shoot each other. Again, you have 1/11 chance of being the surviving person.

[mmiguel]

And yes I do still think that my chances of survival are still 1/3 in that situation.

My chance of dying in any given encounter does depend on the total number of people, but, if we are thinking end game, it doesn't matter to my final survival what happens to those 100,000 pacifists. My survival depends on the two killers meeting each other before one of them meets me. So the only meetings that affect my survival are (K1,K2), (K1,Me) and (K2,Me). So based on those meetings I have a 1/3 chance or survival.

I worked under the assumption that there comes a point where either there is a single killer left or no killers and some number of pacifists and thus no more meetings are important.

Also, I only considered meetings that affected my survival as important and thats how I came up with (n-1)/(n+1).

Am I on the right track or way off?

well in your last post, i had thought you said that (n-1)/(n+1) were the chances of surviving any round, but maybe i mis-interpreted.

well, i need to think about your response...

i agree that with 2 killers and 100000 pacifists, the last important turn has 3 possibilities.

but have we established that those 3 possibilities are equally likely?

what if there are 100 killers and you are the only pacifist?

your formula says you have 99/101 chance of surviving (pretty good chance), which doesn't seem believable to me.

what if there are 3 killers and you are the only pacifist?

in this case, you basically have to die, no matter what.

in my formula, the chance of survival would be

1 - k/(n-1) = 1-3/3 = 0

in yours, it's 1/2

Edited September 7, 2012 by mmiguel

[Rob_Gandy]

chances of survival are probably not very high either way.

but, i showed mathematically in a prior post (unless someone finds a flaw in my reasoning, which is of course very possible), that the chance of surviving a single encounter (assuming everyone is paired together in such an encounter, with the exception of maybe one odd man out), increases as the total number of pacifists increase while the number of killers remain the same.

it is thus in your best interest to make any possible decision you can to result in as many pacifists being alive in each round as possible.

it's like the evolutionary strategy of a school of fish - band together so that although the chances of a shark getting a meal are large, within the school itself, the likelihood of any particular fish getting eaten in a single shark encounter decreases.

being a killer erodes your "protection" faster.

you may likely die either way, but you have a slightly better chance of surviving if you don't kill others, letting them live in order to take a bullet for you later in the future.

Pacifist

You: assuming everyone is paired together in such an encounter, with the exception of maybe one odd man out

Me: I worked under the assumption...And that meetings occur one at a time.

[mmiguel]

Yes. See my spoiler above.

In the general case I alluded to above, with K (even) killers and P pacifists, P/ (K+1) pacifists survive on average.

When K=P=10 initially, by joining the pacifists you make P=11, and on average 1 pacifist will stand and can attend the killers' funerals. You have 1/11 chance of being that survivor. If you join the killers, you make K=11 (odd) so it is certain that exactly1 killer is standing at the end. He wipes out any pacifists still breathing when killers 9 and 10 shoot each other. Again, you have 1/11 chance of being the surviving person.

can you share the derivation of P/(K+1)?

[mmiguel]

You: assuming everyone is paired together in such an encounter, with the exception of maybe one odd man out

Me: I worked under the assumption...And that meetings occur one at a time.

ah! haha

i suppose i should spend more time reading the prompt then, i guess i was solving the wrong problem

[mmiguel]

ah! haha

i suppose i should spend more time reading the prompt then, i guess i was solving the wrong problem

well... i guess my interpretation is not inconsistent with original problem statement, if 1-on-1 is interpreted as a one-to-one mapping i.e. a pair.

"Assume all encounters are 1-on-1 and random."

i can definitely see how one would see this and assume that in any "round" only 2 people are selected from the population, and said to have "met".

oh well, twas a good exercise of thought.

[Rob_Gandy]

well... i guess my interpretation is not inconsistent with original problem statement, if 1-on-1 is interpreted as a one-to-one mapping i.e. a pair.

"Assume all encounters are 1-on-1 and random."

i can definitely see how one would see this and assume that in any "round" only 2 people are selected from the population, and said to have "met".

oh well, twas a good exercise of thought.

Looking back at your answer posts

(n-k)/n for for chance of survival in a given round. k being number of killers and n being number of outcomes affecting survival.

I always enjoy seeing the way people work out problems. That's one of the great things about being a teacher, seeing how people understand.

[bonanova]

can you share the derivation of P/(K+1)?

I computed the encounter probabilities {kk kp pk pp} starting with K killers and P pacifists and noticed their form. Then I worked out K (even) killer, 1 pacifist case which gave me 1/(K+1). Knowing this is also the odd-K survival probability for killers, I devised the OP.

Tiring of the probability trees I simulated the general process, applying the encounter probabilities with their effects: kk-> reduce K by 2; kp or pk-> reduce P by 1; pp-> do nothing. I verified 1/(K+1) for the 1 pacifist case. Finally I verified (by simulation) that P proportionality holds. For wide ranges of K and P the result was always P/(K+1).

I simulated successive random encounters; not "rounds of encounters." Killers and pacifists were not individually tracked. At each stage, values of K and P yielded the probabilities of encounter types, and a RNG selected among them based on those probabilities. K then decreased by 2 for kk encounters; P decreased by 1 for kp or pk encounters. The values of P when K hit zero were averaged, over 100,000 trials, to get the expected number of survivors. Killers never survived.

I believe it can be derived; but, no, I didn't.

[joef1000]

Whatever you are, you should hide in your house as long as you can. Eventually, the 10 killers that already live there eventually wipe each other out and if you are a killer, you are the last one left and can kill all the pacifists, and if you were a pacifist, you are safe because there are no killers left. The twist here is that anyone else coming into the town can register as a killer. This means you should always stay within earshot of the entrance, but not where you can be seen there. That way, if you ever here gunfire you can hide immediately and wait for another killer to come to town and wipe the other killer out. Another twist is that everyone might employ this strategy and hide in their houses. Then it will sound safe to come out, everyone might and the killers will kill everyone! A third twist is that the problem stated a killer must kill anyone they see, but if a killer killed another killer from behind, they do not die. Also, if it is part of your job you will have to go to work and not be able to hide forever. This means the best strategy could be to be a pacifist, and always travel with other pacifists to and from work, and hide at home whenever possible.

I think the best strategy is just to quit your job and find a safer one. Maybe sue your company for sending their workers top such a dangerous place!