Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

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)$.

share|improve this answer

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$).

share|improve this answer
1  
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
1  
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
1  
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
1  
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
1  
Yes, was obviously in need of coffee. –  André Nicolas Oct 4 '12 at 18:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.