Lopsy answered 11. rand al'thor then asked to consider e.g. 9 and 13. I will
give a recursive formula for the probability of winning for a game of $N$ players.
According to Lopsy's Lemma, for $N$ even there is no chance of winning so I
consider only odd $N$.
First, let me define notation for two types of sequences of coins. I use
$B(n_1)$ for a "block" sequence of same sided coins, of length $n_1$. E.g.
$B(5)$ can be $TTTTT$ or $HHHHH$. I use $A(n_2)$ for an "alternating" sequence of
coins, of length $n_2$. E.g. $A(5)$ can be $THTHT$ or $HTHTH$. We also define
the following when combining sequences:
$A$ types concatenate with $A$ types, and $B$ types concatenate with $B$
types. Namely $A(n_1)A(n_2) = A(n_1 + n_2)$ for any integers $n_1, n_2$, and
similarly for $B$ types. Without loss of generality I will only consider fully
concatenated forms from here on.
An $A$ type sequence always starts with the opposite
of the preceding coin, e.g. $B(2)A(2)$ corresponds to $TTHT$ or $HHTH$.
A $B$ type sequence always starts with the same side
as the preceding coin, e.g. $A(2)B(2)$ corresponds to $THHH$ or $HTTT$.
Note that any periodic sequence can be described by combining $A$ and $B$ type
sequences and specifying the first coin. E.g., $TH H THTHTH HH$ is described by
specifying $T$ as the first coin, then $A(2)B(1)A(6)B(2)$.* I call
such forms "canonical", i.e.
The canonical form of a periodic sequence specifies the first coin in the
sequence, and a list of alternating $A$ and $B$ type sequences of specified
lengths.**
Note that canonicalization provides a bijection from the set of all length-$N$
periodic coin sequences to the set of all length-$N$ canonical forms having an
even number of coins contained in $A$-type subsequences.
Let us consider just the first round of an N player game. Without loss of
generality, assume my coin is $T$. Starting from me, looking to the left, and
skipping every other player, I write the sequence of $N$ coins in canonical
form. (This is the counting scheme from Lopsy's lemma.) Let $N_A$ denote the
total number of coins contained within $A$-type subsequences. Note that $N_A$ is
the number of people eliminated in this round and $N_A$ must be even (see
Lopsy's answer). Therefore the probability of $N_A$ people being eliminated is
$$
\frac{\binom{N}{N_A}}{2^{N - 1}}.
$$
Since I assumed I have $T$, we have only $2^{N-1}$ possible sequences of
coins in the denominator.$\dagger$
Denote the probability that in a single N-player round, $N_A$ people are
eliminated, while I am not eliminated, as
$$
P_1(N, N_A) = \left(1 - \frac{N_A}{N}\right) \frac{\binom{N}{N_A}}{2^{N - 1}}.
$$
We must now consider all possibilities recursively. Denote the probability of
winning the entire N-person game as $P(N)$. Then $P(1) = 1$, and for $N > 1$,
$$
P(N) = \sum_{N_A} P_1(N, N_A) P(N - N_A),
$$
where the sum runs over all even, positive integers $N_A$, such that $N_A \leq N - 1$.
*:
Note that the first coin is "preceded" by the last coin since this is a periodic
sequence. The last coin differs from the first, and is part of a $B$ type
sequence, so the first coin is the start of an $A$ type sequence. To be more
rigorous, the construction should go like $TA(1)B(1)A(6)B(2)$, then
$A(1)A(1)B(1)A(6)B(2)$, then $A(2)B(1)A(6)B(2)$.
**:
Note that the first and last sequence types can be the same.
E.g., $T$, $A(2)B(3)A(2)$ is in its canonical form.
$\dagger$:
If we let my coin be $H$ or $T$, then both the numerator and denominator will pick up a
factor of two. Another way to obtain the denominator is by summing over all
possible eliminations, i.e. $\sum_{i=0}^{(N - 1) / 2} \binom{N}{2i} = 2^{N-1}$.
Edit 12/28: Clarify why the example "canonical form" starts with $A(2)$, and that
the canonical form is for periodic sequences.
Edit 12/29: Fix factor of 2 in probability of eliminating $N_A$ players, as pointed out by Lopsy.
