For some positive integer $n$, a coin will be flipped $n$ times to obtain a sequence of $n$ heads and tails. For each flip of the coin, there is probability $p$ of obtaining a head and probability $1-p$ of obtaining a tail, where $0<p<1$ is a rational number.

Kim writes all $2^{n}$ possible sequences of $n$ heads and tails in two columns, with some sequences in the left column and the remaining sequences in the right column. Kim would like the sequence produced by the coin flips to appear in the left column with probability $\frac{1}{2}$.

Determine all pairs $(n, p)$ for which this is possible.
Any particular sequence that includes $k$ heads and $n-k$ tails occurs with probability $p^{k}(1-p)^{n-k}$. So we are looking for $(n, p)$ for which
$$
\sum_{k=0}^{n} a_{k} p^{k}(1-p)^{n-k}=\frac{1}{2},
$$
where $a_{0}, a_{1}, \ldots, a_{n}$ are integers satisfying $0 \leq a_{k} \leq\binom{ n}{k}$. The equation above implies that
$$
2 \sum_{k=0}^{n} a_{k} p^{k}(1-p)^{n-k}-1=0
$$

Consider the left side of this equation as a polynomial in $p$. Observe that it has integer coefficients and constant term $2 a_{0}-1= \pm 1$. The rational root theorem then implies that any rational root $p$ must be of the form $\frac{1}{m}$ for some non-zero integer $m$. Since we are only interested in $0<p<1$, we may furthermore assume that $m \geq 2$. Substituting $p=\frac{1}{m}$ into the equation above yields
$$
2 \sum_{k=0}^{n} a_{k}\left(\frac{1}{m}\right)^{k}\left(\frac{m-1}{m}\right)^{n-k}-1=0 \quad \Rightarrow \quad 2 \sum_{k=0}^{n} a_{k}(m-1)^{n-k}-m^{n}=0 .
$$

Now consider this equation modulo $m-1$ to deduce that $2 a_{0}-1^{n} \equiv 0(\bmod m-1)$, from which it follows that $\pm 1 \equiv 0(\bmod m-1)$. However, this can only hold if $m=2$, so we conclude that $p=\frac{1}{2}$.

The conditions of the problem are satisfied for $\left(n, \frac{1}{2}\right)$ for all positive integers $n$. For example, Kim can write all sequences that start with a head in the left column and all sequences that start with a tail in the right column.