A computer generates even integers half of the time and another computer generates even integers a third of the time. If $a_i$ and $b_i$ are the integers generated by the computers, respectively, at time $i$, what is the probability that $a_1b_1 +a_2b_2 +\cdots + a_kb_k$ is an even integer.
Problem
Source:
Tags: probability, combinatorics unsolved, combinatorics
05.11.2016 04:03
Let $p_k$ be the probability that $\sum_{i=1}^{k} a_ib_i\text{ is even.}$ The probability that $a_ib_i\text{ is even is }1-\frac{1}{2}\cdot\frac{2}{3}=\frac{2}{3}$ The probability that $a_ib_i\text{ is odd is }\frac{1}{2}\cdot\frac{2}{3}=\frac{1}{3}$ Then $p_{k+1}=p_k\cdot\frac{2}{3}+(1-p_k)\cdot\frac{1}{3}=\frac{1}{3}p_k+\frac{1}{3}$ $p_{k+1}-\frac{1}{2}=\frac{1}{3}\left(p_k-\frac{1}{2}\right)=\dots=\left(\frac{1}{3}\right)^k\left(p_1-\frac{1}{2}\right)=\left(\frac{1}{3}\right)^k\cdot\frac{1}{6}$ $p_{k+1}=\left(\frac{1}{3}\right)^k\cdot\frac{1}{6}+\frac{1}{2}(k\ge 1)$ This also holds at $k=0.$Therefore $\boxed{p_k=\frac{1}{6}\left(\frac{1}{3}\right)^{k-1}+\frac{1}{2}}\blacksquare$
05.11.2016 04:17
The above solution is nice Alternatively see that the desired probability is $$\sum_{0\leq i\leq k,2\mid i}\binom{k}{i}\left(\frac{2}{3}\right)^{k-i}\left(\frac{1}{3}\right)^i=\frac{1}{2}\left(\left(\tfrac{2}{3}-\tfrac{1}{3}\right)^k+\left(\tfrac{2}{3}+\tfrac{1}{3}\right)^k\right)=\boxed{\frac{1}{2}\left(1+3^{-k}\right)}$$