It is currently Thu Mar 28, 2024 7:22 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 15 posts ] 
Author Message
Offline
 Post subject: Entertaining puzzle
Post #1 Posted: Mon Dec 14, 2015 2:35 am 
Lives in gote
User avatar

Posts: 452
Liked others: 74
Was liked: 100
Rank: 4 Dan European
There are n people in a circle, all with guns. When the clock strikes, they all shoot someone else dead. they choose their victim at random, with equal probability assigned to any potential victim.

After the first round of killings, the clock strikes again. The survivors repeat the exercise. This continues until wither only 1 person is left; or until 0 people are left.

Let P(n) be the probability that 0 people are left.

What is the asymptotic distribution of P(n) as n gets large?

Top
 Profile  
 
Offline
 Post subject:
Post #2 Posted: Mon Dec 14, 2015 2:48 am 
Honinbo
User avatar

Posts: 8859
Location: Santa Barbara, CA
Liked others: 349
Was liked: 2076
GD Posts: 312
drmwc, Thanks for the puzzle. Do you also know about Ponder This ?


This post by EdLee was liked by: drmwc
Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #3 Posted: Mon Dec 14, 2015 5:59 pm 
Lives in gote
User avatar

Posts: 603
Liked others: 43
Was liked: 139
Rank: 6-7k KGS
1/e

I don't know why, but am guessing that because it's the answer to a lot of questions that involve calculus.


This post by Fedya was liked by: ez4u
Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #4 Posted: Mon Dec 14, 2015 6:28 pm 
Lives in gote

Posts: 553
Liked others: 61
Was liked: 250
Rank: AGA 5 dan
Does a numerical simulation count as a valid answer?
Attachment:
psim.png
psim.png [ 29.44 KiB | Viewed 9487 times ]


This post by mitsun was liked by: drmwc
Top
 Profile  
 
Offline
 Post subject:
Post #5 Posted: Tue Dec 15, 2015 2:35 am 
Honinbo
User avatar

Posts: 8859
Location: Santa Barbara, CA
Liked others: 349
Was liked: 2076
GD Posts: 312
Hi drmwc, this sounds like a nice puzzle.
Did you invent it ? If so, you may consider to send it to Ponder This .
So that many others can enjoy it.
drmwc wrote:
When the clock strikes, they all shoot someone ELSE dead.
I didn't get very far at all.
Just the first few baby steps.

Let Q(x->y) be the probability to get from (n==x) to (n==y).

If n == 2, both die, ending with n == 0. Q(2->0) = 1.
If n == 3, it's impossible to get down to 2. Q(3->2) = 0. Q(3->1) = 3/4. Q(3->0) = 1/4.

If you have never seen The Good, the Bad, and the Ugly, spoiler alert:
I hate spoilers; I've already said too much. :)
Drew some pretty graphs for n == 3 case.

Need a bigger piece of paper for the (n == 4) graphs.

Obviously, for each poor fellow in the circle, the probability this person survives this round is:
[ (n-2)/(n-1) ](n-1)

Thanks, drmwc.

mitsun, I hope there's an elegant algebraic solution.
But from your graph, it looks like 0.5 doesn't it.

Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #6 Posted: Tue Dec 15, 2015 3:08 am 
Lives in gote
User avatar

Posts: 452
Liked others: 74
Was liked: 100
Rank: 4 Dan European
Ed

Thanks for pointing out ponder this - it looks interesting. I didn't make this puzzle up - I found it in this book:
http://www.amazon.co.uk/Mathematical-Puzzles-A-Connoisseurs-Collection/dp/1568812019

I wholeheartedly recommend the book.

Here is a mild hint:
The problem is highly non-trivial,and the solution is counter-intuitive.

Top
 Profile  
 
Offline
 Post subject: Re:
Post #7 Posted: Tue Dec 15, 2015 5:53 am 
Oza

Posts: 2180
Location: ʍoquıɐɹ ǝɥʇ ɹǝʌo 'ǝɹǝɥʍǝɯos
Liked others: 237
Was liked: 662
Rank: AGA 5d
GD Posts: 4312
Online playing schedule: Every tenth February 29th from 20:00-20:01 (if time permits)
Ed's statement (hidden below) for one person's chances of survival can be multiplied by n and produces a value which is remarkably close to 1/e as n increases. Fedya must have remarkable intuition.
Obviously, for each poor fellow in the circle, the probability this person survives this round is:
[ (n-2)/(n-1) ](n-1)

_________________
Still officially AGA 5d but I play so irregularly these days that I am probably only 3d or 4d over the board (but hopefully still 5d in terms of knowledge, theory and the ability to contribute).

Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #8 Posted: Tue Dec 15, 2015 1:00 pm 
Lives in gote

Posts: 553
Liked others: 61
Was liked: 250
Rank: AGA 5 dan
I should have made the plot using the natural logarithm of the starting population :) The probability oscillates about 50% and looks like it might not ever converge. Each oscillation period appears to be a factor e longer than the previous period -- the spacing is one unit along the log(e) axis in the plot. Weird.
Attachment:
psim.png
psim.png [ 28.08 KiB | Viewed 9344 times ]


This post by mitsun was liked by: drmwc
Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #9 Posted: Tue Dec 15, 2015 1:24 pm 
Oza

Posts: 2493
Location: DC
Liked others: 157
Was liked: 442
Universal go server handle: skydyr
Online playing schedule: When my wife is out.
The question is really asking whether you'll end up with an odd or even number of people at the end, since 2 == 0 for the purposes of this question. If the selection process is random, you can do all sorts of calculation to determine exactly how many people will be killed on average given a number of starting people, but you should end up with 50/50 odds that one person will survive in a very large group, because while having an odd or even number of people to start may bias it in one direction or the other, you are taking both into account, and the more people there are, the more likely fluky selection of targets will randomize the odd/even count of the group.

Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #10 Posted: Tue Dec 15, 2015 2:58 pm 
Lives in gote

Posts: 553
Liked others: 61
Was liked: 250
Rank: AGA 5 dan
As Ed and DrStraw noted, the probability of any one person's survival into the next round is [(n-2)/(n-1)]^(n-1). For large n, this is also the fraction of people who survive into the next round, which we might call the culling factor. This can be simplified to approximately Fcull ~= [(n-1)/n]^(n-1) for large n. Taking the logarithm, ln(Fcull) ~= (n-1) ln[1-1/n] ~= (n-1)(-1/n) ~= -1, so Fcull ~= 1/e. This explains at least the periodicity of the results.

Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #11 Posted: Wed Dec 16, 2015 2:52 pm 
Lives in gote
User avatar

Posts: 312
Liked others: 52
Was liked: 41
Rank: 7K KGS
KGS: tictac
This does not really answer the OP question: the crazy duellist repeat the process until 1 or 0 are left!


each time, they have a proba of (1/e)^n of all dying, very small

but the proba of 1 survivor is n* (1/e)^(n-1) (1-1/e)

so P(1 left after this round)/P(0 left after this round ) is of order n * (e-1) (possible because both proba are very very small)

We will retry until there is either 1 or 0 left, so

so if n is very large, P (1 survivor) is about 1! all result other than 0 or 1 is meaningless even if they are by far the most probable each time!

The exact law is trickier to extract , though, because it might take a lot of rounds to reduce from N duellist to either 0 or 1.
if we start with N duellists, proba of 0 or 1 left after 1 round is given above,
but the actual number of rounds before it happens, and the number of remaining duellists at that time is hard to compute from N

i ll go with P(n = proba that 0 are left in the end after starting with n duelists) in O(1/n) anyway :scratch:

_________________
In theory, there is no difference between theory and practice. In practice, there is.

Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #12 Posted: Wed Dec 16, 2015 3:18 pm 
Lives in gote
User avatar

Posts: 312
Liked others: 52
Was liked: 41
Rank: 7K KGS
KGS: tictac
attempt at more rigorous computation.

lets assume that we throw a weighted coin wich falls on tail with proba p, on head with proba q=p*r, and on the edge with proba
1-p-q
We will throw the coin until it falls on either head or tail.

what is the proba that it ends up on head ?

lets compute the proba that it end on head after N throws:
P(Head,N)= (1-p-q)N-1q
if we sum over all N:

P(Head/End of game )=q* sum over N((1-p-q)N-1)

now, we could compute the geometric sum but there is no need:

by symmetry,
P(Tail/End of game )=p* sum over N((1-p-q))N-1)
so P(Head/End of game )/ P(Tail/End of game ) =q/p = r

in the end; the result is either Head or tail:
so P(Head/End of game )+ P(Tail/End of game ) = 1
We have

P(Head/End of game ) *(1+r)=1
=> P (Head at end of game) =1/(1+r)

back to first problem, p and q changes with the number duelist left, but IF we assume that the game will finish before N as been reduced enough that the law changes a bit,
(its reasonable, but not proved)

we have P(n)=P (0 is left at the end when starting with n duelists) = 1/ (1+n*(e-1))

so of order P(n)=1/n(e-1)

(unless there is some horrible error, its late)

EDIT: F- for me for not noticing that by beautiful theory contradicts the experiments (mitsun's graph) :grumpy:

_________________
In theory, there is no difference between theory and practice. In practice, there is.


Last edited by perceval on Wed Dec 16, 2015 3:45 pm, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #13 Posted: Wed Dec 16, 2015 3:31 pm 
Lives in gote
User avatar

Posts: 312
Liked others: 52
Was liked: 41
Rank: 7K KGS
KGS: tictac
skydyr wrote:
The question is really asking whether you'll end up with an odd or even number of people at the end, since 2 == 0 for the purposes of this question. If the selection process is random, you can do all sorts of calculation to determine exactly how many people will be killed on average given a number of starting people, but you should end up with 50/50 odds that one person will survive in a very large group, because while having an odd or even number of people to start may bias it in one direction or the other, you are taking both into account, and the more people there are, the more likely fluky selection of targets will randomize the odd/even count of the group.



mm i missed the fact that if we are left with 2 then 0 will be left at the end, which changes my result above ...

in fact I know believe that my assumption above "lets assume that N does not goes down too fast before end of game" is wrong:

whatever the big N you start with, you will very probably ends up with a small number of duellist at the end, a number where the law above applies badly
The exact number you end up with at the last round probably introduce the weird oscillation on mitsun graph, or something.

i am not 100% convinced by skydir argument above, but 1/2 seems to fit mitsuns graph (butthere is still the issue of the weird oscillation)
probabilities are hard

_________________
In theory, there is no difference between theory and practice. In practice, there is.

Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #14 Posted: Wed Dec 16, 2015 3:52 pm 
Lives in gote

Posts: 553
Liked others: 61
Was liked: 250
Rank: AGA 5 dan
Perceval, you seem to be trying to solve a different game, in which the entire population is reduced to zero or one in a single round (with lots of repetitions from the full starting population until that very unlikely outcome actually occurs). In this scenario, the odds favor one survivor over zero survivors by a factor of N. This is quite different from the actual game.

The question of how many rounds it takes to resolve the actual game is easy to answer. Since the population is reduced by a factor of e each round, it ln(N) rounds to end the game. This approximation is derived for large N, but actually comes pretty close even for N=3.

Top
 Profile  
 
Offline
 Post subject: Re: Entertaining puzzle
Post #15 Posted: Thu Dec 17, 2015 6:13 pm 
Beginner

Posts: 15
Liked others: 0
Was liked: 3
drmwc wrote:
What is the asymptotic distribution of P(n) as n gets large?

See arXiv:1507.03805

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 15 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group