 |
 |
Problem Posts |  |
 |
QUESTION
(PMO 2012-1) 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$; show that the probability that $a_{1}b_{1}+\cdots+a_{k}b_{k}$ is even is $\frac{1}{2}+\frac{1}{2\cdot3^{k}}$.
(PMO 2012-1) 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$; show that the probability that $a_{1}b_{1}+\cdots+a_{k}b_{k}$ is even is $\frac{1}{2}+\frac{1}{2\cdot3^{k}}$.
Laconic Solution Sketch Induction.
Discussion
To be frank, there is a minor issue about having computers generate these integers. It is quite difficult for a traditional computer system to generate truly random numbers; most of the time it is good enough to have pseudorandomness, where the output appears random to the casual observer but are really produced by complicated but deterministic processes.Because we want to have something to solve in the first place, let's assume the randomness here is real. Big assumption in the real world, but hey, this isn't the first time we've had to suspend disbelief for the sake of a math problem.
When we want to prove something about probabilities regarding an arbitrary integer, our first line of attack should always be mathematical induction. There's almost always some way to link the $k^{{\rm th}}$ case with the $\left(k+1\right)^{{\rm th}}$; in other words, it's easy to find the inductive step.
So anyway let's try small numbers first. If $k=1$, we want to see if $a_{1}b_{1}$ is even. And that's just \begin{eqnarray*} P\left(a_{1}b_{1}\text{ even}\right) & = & P\left(a_{1}\text{ even or }b_{1}\text{ even}\right)\\ & = & 1-P\left(a_{1},b_{1}\text{ odd}\right)\\ & = & 1-\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\\ & = & \frac{2}{3}\\ & = & \frac{1}{2}+\frac{1}{2\cdot3^{1}} \end{eqnarray*} So it's true for $k=1$. The interesting property we have here is that $\frac{2}{3}$ is also the probability that $a_{2}b_{2}$ is even, or that $a_{3}b_{3}$ is even; it doesn't matter what the previous outcomes are.
NOTE
Yes, it's the same probability, regardless of the previous outcomes. To believe otherwise is only human; it's called the gambler's fallacy. Just because you've lost every bet so far doesn't improve your chances of winning the next one. For example, the probability that a fair coin lands heads 1000 times in a row is exceedingly small, but the probability the $1001^{{\rm st}}$ one lands heads is still the same old number, 0.5.
Yes, it's the same probability, regardless of the previous outcomes. To believe otherwise is only human; it's called the gambler's fallacy. Just because you've lost every bet so far doesn't improve your chances of winning the next one. For example, the probability that a fair coin lands heads 1000 times in a row is exceedingly small, but the probability the $1001^{{\rm st}}$ one lands heads is still the same old number, 0.5.
So now for the inductive step. Suppose the probability that $a_{1}b_{1}+\cdots+a_{n}b_{n}$ is even is $\frac{1}{2}+\frac{1}{2\cdot3^{n}}$. Let's query the machines for $a_{n+1}$ and $b_{n+1}$. We will have $a_{n+1}b_{n+1}$ even with probability $\frac{2}{3}$, and odd with probability $\frac{1}{3}$.
How does this help us? Well, \begin{eqnarray*} P\left(a_{1}b_{1}+\cdots+a_{n+1}b_{n+1}\text{ even}\right) & = & P\left(a_{1}b_{1}+\cdots+a_{n}b_{n}\text{ and }a_{n+1}b_{n+1}\text{ odd}\right)+\\ & & P\left(a_{1}b_{1}+\cdots+a_{n}b_{n}\text{ and }a_{n+1}b_{n+1}\text{ even}\right)\\ & = & P\left(a_{1}b_{1}+\cdots+a_{n}b_{n}\text{ odd}\right)P\left(a_{n+1}b_{n+1}\text{ odd}\right)+\\ & & P\left(a_{1}b_{1}+\cdots+a_{n}b_{n}\text{ even}\right)P\left(a_{n+1}b_{n+1}\text{ even}\right)\\ & = & \left(1-\frac{1}{2}-\frac{1}{2\cdot3^{n}}\right)\left(\frac{1}{3}\right)+\left(\frac{1}{2}+\frac{1}{2\cdot3^{n}}\right)\left(\frac{2}{3}\right)\\ & = & \frac{1}{2}-\frac{1}{2\cdot3^{n+1}}+\frac{1}{3^{n+1}}\\ & = & \frac{1}{2}+\frac{1}{2\cdot3^{n+1}} \end{eqnarray*} which completes our inductive step.
