# Coin toss tails divisibility

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.

Suppose that I flip a coin $t$ times. How can I find a generalized formula for the probability that the number of tails I will get will be equivalent to $0$ mod $3$ ?

I have tried my hand at this problem- I believe that the result is related to $t$ mod $6$. I am not able to get a formula that works, other than that.

-
Do you know some stuff about complex numbers? And if you have found a formula that you can show works, why is that not satisfactory? –  André Nicolas Oct 4 '12 at 3:51
@AndréNicolas I don't have a working formula- only a hunch that it is related to tmod6.I know enough about complex numbers, yes. –  Aria Fitzpatrick Oct 4 '12 at 11:43

Say the coin comes up tails with probability $p$, heads with probability $q=1-p$. Let $$f(x)=(px+q)^t=\sum_{r=0}^t{t\choose r}p^rq^{t-r}x^r$$ Then the coefficient of $x^r$ is the probability of exactly $r$ tails in $t$ tosses.

Now let $a$ and $b$ be the nonreal cube roots of 1. It's not hard to show that $$1^r+a^r+b^r=3{\rm\ if\ }3\mid r,1^r+a^r+b^r=0{\rm\ else}$$ So $$f(1)+f(a)+f(b)=1+(pa+q)^t+(pb+q)^t=3\sum_{3\mid r}{t\choose r}p^rq^{t-r}$$ tells you the answer to your question is $(1/3)(1+(pa+q)^t+(pb+q)^t)$.

-

Let $1$, $\omega$, and $\omega^2$ be the cube roots of unity. So $\omega=e^{2\pi i/3}$. I don't like the letter $t$ in the context you are using it, so will use $n$.

By the Binomial Theorem, we have $$(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k.$$ Now let $$F(x)=(1+x)^n +(1+\omega x)^n+(1+\omega^2 x)^n.$$ If we expand, the coefficient of $x^k$ is $$\binom{n}{k}(1+\omega^k+\omega^{2k}).$$ If $k$ is divisible by $3$, then $1+\omega^k+\omega^{2k}=1+1+ 1=3$. If $k$ is not divisible by $3$, then $1+\omega^k+\omega^{2k}=0$. So $$\frac{F(x)}{3}=1+\binom{n}{3}x^3+\binom{n}{6}x^6+\binom{n}{9}x^9+\cdots,$$ (finite sum). Put $x=1$. We get $$\frac{F(1)}{3}=\frac{(1+1)^n+(1+\omega)^n+(1+\omega^2)^{2n}}{3}=\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\binom{n}{9}+\cdots.$$ For the probability, divide by $2^n$. So our probability, simplified a bit, is given by $$\frac{1}{3}+\frac{(1+\omega)^n +(1+\omega^2)^n}{3\cdot 2^n}.$$

For computation, we will want to fool around with $(1+\omega)^n+(1+\omega^2)^{n}$. Note that $1+\omega$ and $1+\omega^2$ are conjugates. Express $\omega$ in polar form $re^{i\theta}$. It will involve a $60^{\circ}$ angle. Then $(1+\omega)^n+(1+\omega^2)^n =r^n (e^{i n\theta}+e^{-i n\theta})$. That will just be $2r^n \cos(n\theta)$. Can simplify further, getting a "mod" expression, since the cosines cycle.

Another way: Here is a brief sketch of another approach. Let $P_0(n)$ be the probability that the number of tails is congruent to $0$ modulo $3$, and let $P_1(n)$ the probability that the number of tails is congruent to $1$ modulo $3$. For symmetry we should also have a $P_2(n)$, but it can be dispensed with, since it is $1-P_0(n)-P_1(n)$.

We can get recurrences for $P_0(n)$ and $P_1(n)$ in terms of each other. The first is $$P_0(n)=\frac{1}{2}P_0(n)+\frac{1}{2}P_2(n-1)=\frac{1}{2}P_0(n-1)+\frac{1}{2}(1-P_0(n-1)-P_1(n-1)).$$ This is because in our $n$ tosses, the number of tails is congruent to $0$ mod $3$ if (i) it was congruent to $0$ and we got a head or (ii) it was congruent to $2$ and we got a tail. Similarly, but more simply, $$P_1(n)=\frac{1}{2}P_1(n-1)+\frac{1}{2}P_0(n-1).$$ We can solve this system of two recurrences by matrix methods. It is more common in undergraduate courses to get from our two first-order recurrences a single second-order linear recurrence for $P_0(n)$. You may have seen methods to deal with these (find roots of characteristic polynomial, $\dots$).

-
You say $$(1+x)^n=\sum_{k=0}^n \binom{n}{k}t^k.$$ Do you not mean $$(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k$$? If not what is $t$? –  Aria Fitzpatrick Oct 4 '12 at 16:15
Also, I am not sure I understand how you are getting the probability from the previous step. Could you show the intermediate step? I think that you made some typos on that previous step... –  Aria Fitzpatrick Oct 4 '12 at 17:00
You say $$\frac{F(1)}{3}=(1+1)^n+(1+\omega^n)+(1+\omega^2)^{2n}=\binom{n}{0}+\binom{n}{3‌​}+\binom{n}{6}+\binom{n}{9}+\cdots.$$ Should it not be $$\frac{F(1)}{3}=(1+1)^n+(1+\omega)^n+(1+\omega^2)^{2n}=\binom{n}{0}+\binom{n}{3‌​}+\binom{n}{6}+\binom{n}{9}+\cdots.$$ –  Aria Fitzpatrick Oct 4 '12 at 17:11
yes, that is true as well, but should it not be $(1+\omega)^n$ rather than $(1+\omega^n)$? –  Aria Fitzpatrick Oct 4 '12 at 18:17
Yes, was obviously in need of coffee. –  André Nicolas Oct 4 '12 at 18:18