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 $1/2$. Determine all pairs $(n,p)$ for which this is possible.
Problem
Source: Simon Marais MC 2019 A3
Tags: probability and stats
Bashy99
16.10.2019 12:40
For $0\le r\le n,$ let $a_r$ denote the number of sequences with $r$ heads that Kim wrote in the left column. Then $0\le a_r\le\binom{n}{r}.$ Kim wants
$$\sum_{r=0}^na_rp^r(1-p)^{n-r}=\frac{1}{2}\implies\sum_{r=0}^n(2a_r)p^r(1-p)^{n-r}=1.$$But we also know that
$$\sum_{r=0}^n\binom{n}{r}p^r(1-p)^{n-r}=1.$$Hence
$$\sum_{r=0}^n\left(2a_r-\binom{n}{r}\right)p^r(1-p)^{n-r}=0.$$Suppose $p=\frac{a}{b}$ where $a,\,b$ are coprime positive integers with $a<b.$ Then, the above becomes
$$\sum_{r=0}^n\left(2a_r-\binom{n}{r}\right)\left(\frac{a^r(b-a)^{n-r}}{b^n}\right)=0$$$$\implies\sum_{r=0}^n\left(2a_r-\binom{n}{r}\right)a^r(b-a)^{n-r}=0.$$Hence $a$ must divide $2a_0-1$ since $\gcd(a,b-a)=1.$ But $0\le a_0\le 1.$ So $a$ must be $1.$ Similarly $(b-a)$ must divide $2a_n-1.$ Again $0\le a_n\le 1.$ Hence $(b-a)$ is also equal to $1$ which gives $a=1,\,b=2.$ so $p$ must be $\frac{1}{2}.$
Observe that if $p=\frac{1}{2},$ any $n\in\mathbb{N}$ will work. Kim will write any $2^{n-1}$ of the $2^n$ sequences in the left column and that will serve his purpose.