If half the population were murderers, and they could only kill once, how many would survive?

Here is my thought.

Let's call murderers (m) the persons that are able to kill and citizens (c) the persons that cannot kill (these might be either innocent persons or murderers that have already killed someone).

I will use M and C for initially murderers and initially innocent citizens.

Assuming we start with N murderers and N citizens (let's take N to be even), our story will last from N/2 ticks to N-1 ticks.

The number of citizens remaining in the end depends on how many murderers have been killed. Each murderer killed, increases this number by 1, because our story will last 1 tick less. So we can easily check that in the end we will have: $$M+\frac{C}2=N$$

• If a murderer is killed, then the number of m decreases by 2 and the number of c increases by 1 (the murdeder becomes a citizen)
• If a citizen is killed, then the number of m decreases by 1 and the number of c stays the same (an innocent is killed but the murderer takes his place)

Let's define f(m,c) the number of persons left alive in the end.

$\begin{cases} f(m,c)=\frac{m-1}{m+c-1}f(m-2,c+1) + \frac{c}{m+c-1}f(m-1,c)\\ f(0,x)=x\\ \end{cases}$

Using this function we should be able to calculate f(N,N)=x

Then we have: $\begin{cases} M+C=x\\ M+\frac{C}2=N \end{cases}$

Solving for M,C we get: $\begin{cases} C=2(x-N)\\ M=2N-x \end{cases}$,

So there will survive M+C people and the proportion of murderers will be $\frac{M}{M+C}$.

Note: Using a recursive algorithm it should be trivial, but I'm still not sure how to compute with pencil and paper the f(N,N).

Expansion of a comment:

As a simulation in R

survive <- function(n){
  living <- c(rep("Future murderer", n), rep("Nonmurderer", n))
  while( sum(living == "Future murderer") > 0 ){ 
    if( sum(living == "Future murderer") == 1 ){
      newmurderer <- which(living == "Future murderer")
      }else{
      newmurderer <- sample(which(living == "Future murderer"), 1)
      }
    newvictim <- sample((1:length(living))[-newmurderer], 1)
    living[newmurderer ] <- "Murderer"
    living <- living[-newvictim]
    }
  return(c(sum(living == "Murderer"), sum(living == "Nonmurderer")))
  }

and trying with $N=100$ and with $10000$ simulations

set.seed(2021)
N <- 100
cases <- 10^4
sims <- replicate(cases, survive(N)) 
mean(sims[1,]) # average number of muderers surviving
# 60.754
mean(sims[2,]) # average number of nonmurderers surviving
# 60.4485

This simulated total mean number of survivors of $121.2025$ fits well with Thanos Darkadakis's recursion which for $N=100$ would give $x\approx 121.23$. (It seems $\frac x N \to 1.21306\ldots$ as $N$ increases; since $x>1.2N$ for $N\ge 7$ the ratio does not change much.)

But his expressions for the expected number of murderers and nonmurderers surviving $M$ and $C$ do not look correct. For $N=100$ his formulae would give $M \approx 78.77$ and $C\approx 42.46$ when they should be each be just over $60$.

As an alternative argument, on average slightly more murderers than nonmurderers should survive purely because murderers do not commit suicide so have a slight bias to killing nonmurderers, though this is mitigated by an increasing proportion of murderers surviving and so being available to be murdered. If we say that the expected number of actual murders is $2N-x$, and the first kills an expected $\frac{N-1}{2N-1}$ murderers and $\frac{N}{2N-1}$ non-murderers and so on for later murders, it might be possible to argue in a handwaving way that for $N=100$ you might have $M-C \approx 0.4$, not so far from the simulated $0.3055$ (there may be some minor unjustified simplifications in this, but as an order of magnitude it seems reasonable).

So as $N$ increases, it seems likely that the expected proportion of survivors who are murderers $\frac M{M+C} \to \frac12$ from above, and so both $\frac{M}N$ and $\frac{C}N$ tend towards $0.60653\ldots$.

The initial population is $2x$, half each. The population at time $t$ is $2x-t$. We want to find $t$ when the population of murderers is zero.
The differential equation obeyed by murderers is $$\frac{dM}{dt}=-1-\frac M{2x-t}, M(0)=x$$ from which the proportion that survives is $e^{-1/2}$.
The number of nonmurderers that survive seems to be $x-t/2$, so half the population at any time is nonmurderers.