I posed this problem for myself based on a simpler problem I saw on reddit, here is the more detailed version of my problem:
The game master traps N people in a pit and equips them with a sort of kill button. When the button is pressed for the first time it will kill a random person, possibly even killing the button presser. The button cannot be pressed a second time (it simply wont do anything). The game master has each person take a turn pressing their button (if they are still alive). What percentage of the initial group of N people will remain?
I am more specifically after $\lim_{n\to \infty} \frac{F(n)}{n}$ Where F(n) is the number of people who remain from an initial population of n people.
I made a basic computer simulation of this scenario for an initial population of n people. As I plugged in bigger n values it became obvious that the percentage remaining was approaching 1/e.
I've been trying to show on paper that $\lim_{n\to \infty} \frac{F(n)}{n} = \frac{1}{e}$ and can't seem to get it, help would be appreciated.
Some useful information:
- A person can only press their button once.
- The people press their buttons one at a time.
- The button will always kill someone. (It will not try to kill an already dead person)
- The button can kill the button presser.
- Every living person has an equal chance of being chosen by the button.
Information that I have gathered on the problem:
The best case scenario happens when the kill buttons always choose to kill someone who has yet to use their button. Resulting in a remaining population of n/2.
The worst case scenario is when the kill button kills the user every time, resulting in a remaining population of 0.
The functional equation $$f(n,p) = \left(\frac{n}{p}\right)f(n-2,p-1)+\left(1-\frac{n}{p}\right)f(n-1,p-1)$$ With base cases: $$f(0,p)=p$$ $$f(1,p)=p-1$$ Represents the expected number of survivors for a given initial population of p where only the first n are assigned kill buttons. For which $f(n,n)$ is the same as $F(n)$ that I defined earlier.
Easier reddit question: n people in a room randomly vote for $1$ person to be killed. When the voting period is over anybody with $1$ vote or more gets killed. What percentage of the initial n people survive?
Important info:
- Multiple people can vote for the same person.
- Everyone gets $1$ vote.
- All of the deaths happen at the same time.
Answer: The probability that someone votes for you is $\frac 1n$, so the probability that someone does not vote for you is $1-\frac 1n$. Then the probability that nobody votes for you is $\left(1-\frac{1}{n}\right)^n$. The limit as n goes to infinity of that expression is also $\frac 1e$.
Why do these problems seem to have the same answer? My problem seems to be fundamentally different from the reddit one as:
- In my scenario one person kills one person, multiple people can't be responsible for a single death.
- In my scenario it is possible for someone to die before or after they kill someone themselves, where that isn't true in the case of the reddit problem.