Problem Post 3-3: randGen.nextInt()

Problem Posts

[Difficulty 2] [PDF]

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

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.

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.

Problem Post 3-2: Prime Valued Polynomial

Problem Posts

[Difficulty 3] [PDF]

QUESTION
(PMO 2012-2) Let $f$ be a polynomial function with integer coefficients and $p$ be a prime number. Suppose there are at least four distinct integers satisfying $f\left(x\right)=p$. Show that $f$ does not have integer zeroes.

Laconic Solution Sketch Get the most obvious auxiliary polynomial.

Discussion

For many people this will probably be the easiest problem in the paper. First, we need a very basic theorem:

THEOREM
Given a polynomial $f\left(x\right)$, iff $f\left(a\right)=0$, then $\left(x-a\right)$ divides $f\left(x\right)$.

Now we want to leverage the Root Theorem along with what we know about $f\left(x\right)$. There are at least two approaches to consider:

Route 1: Jump to Contradiction

One approach would be to apply the theorem directly. Suppose $f\left(x\right)$ has an integer zero $n$, then $\left(x-n\right)$ is a factor of $f\left(x\right)$. That means that \[ f\left(x\right)=q\left(x\right)\left(x-n\right) \] where $q\left(x\right)$, the quotient, is a polynomial with integer coefficients. Now let's plug in $x=a_{1}$. We would have $p=f\left(a_{1}\right)=q\left(a_{1}\right)\left(a_{1}-n\right)$. Our left hand side is a prime number, and $q\left(a_{1}\right)$ and $\left(a_{1}-n\right)$ are integers. This means that $\left(a_{1}-n\right)$ is a divisor of a prime number, so $\left(a_{1}-n\right)$ is among $\left\{ \pm1,\pm p\right\} $.
This fact, taken in itself, isn't very interesting. But when we compound that with the fact that the same has to occur for $\left(a_{2}-n\right)$, $\left(a_{3}-n\right)$, and $\left(a_{4}-n\right)$, something interesting happens: these four numbers have to all be different, and each can be one of four numbers! So that means that the four $a_{i}$ have to be $n+1$, $n-1$, $n+p$, $n-p$.
If there was an $a_{5}$ we'd have a contradiction, because recall that all the $a_{i}$ have to be different. Unfortunately, we're only sure that four $a_{i}$ exist, so we can't really conclude anything. For me this looks like a dead end.

Route 2: Auxiliary Polynomial

We have to be a bit more subtle in using the Root Theorem. Ideally we'd want a polynomial to be zero somewhere. Unfortunately we aren't given that information with $f\left(x\right)$. However, we can set an auxiliary polynomial $g\left(x\right)$ to be exactly $f\left(x\right)-p$. That way, there are at least four distinct integers satisfying $g\left(x\right)=f\left(x\right)-p=0$.
Since it's getting tiring saying ``at least four distinct integers'', let's call the four distinct integers $a_{1}$, $a_{2}$, $a_{3}$, $a_{4}$. There could be more, but whatever we have to prove cannot depend on those extra ones. So we have $g\left(a_{1}\right)=0$, $g\left(a_{2}\right)=0$, and so on.
We can use the Root Theorem now: Since $g\left(a_{1}\right)=0$, we must have $\left(x-a_{1}\right)$ as a factor of $g\left(x\right)$. The same goes for $\left(x-a_{2}\right)$, $\left(x-a_{3}\right)$, and so on. This means that \[ g\left(x\right)=h\left(x\right)\left(x-a_{1}\right)\left(x-a_{2}\right)\left(x-a_{3}\right)\left(x-a_{4}\right) \] where $h\left(x\right)$ is the quotient polynomial (which also has integer coefficients!). Don't forget that we have to put $h\left(x\right)$ there, since $g\left(x\right)$ could have other polynomial factors apart from the four. Also note that at this point, we needed the fact that $a_{1}$, $a_{2}$, and so on are all different from each other.
This is all nice, but how does it bring us to what we want to show? Remember we want to show that $f\left(x\right)$ has no integer zeroes. That means no integer should satisfy $f\left(x\right)=0$, or equivalently $g\left(x\right)=-p$. But when we look at the equation above, we've shown that for any integer $n$, $g\left(n\right)$ is the product of five integers, four of which have to be different! There's no way we can write $-p$ like that, so we're done.

SOLUTION
Let the four distinct integers be $a_{1},a_{2},\ldots,a_{4}$ , and let $g\left(x\right):= f\left(x\right)-p$ , so that for $i=1,2,\ldots,4$ , we have $g\left(a_{i}\right)=0$. Then $\left(x-a_{i}\right)$ divides $g\left(x\right)$, and since the $a_{i}$ are distinct we have$g\left(x\right)=h\left(x\right)\left(x-a_{1}\right)\left(x-a_{2}\right)\left(x-a_{3}\right)\left(x-a_{4}\right)$ where $h\left(x\right)$ is a polynomial with integer coefficients. Now suppose for the sake of contradiction $f\left(x\right)$ has an integer root $n$ . Then \begin{eqnarray*} -p & = & f\left(n\right)-p\\ & = & g\left(n\right)\\ & = & h\left(n\right)\left(n-a_{1}\right)\left(n-a_{2}\right)\left(n-a_{3}\right)\left(n-a_{4}\right) \end{eqnarray*} Now we must have $h\left(n\right),\left(n-a_{i}\right)\in\left\{ \pm1,\pm p\right\} $ , and such that either $p$ or $-p$ (but not both or neither) shows up in the above product, and so that the $\left(n-a_{i}\right)$ are distinct. The five values cannot be so allocated, hence we have a contradiction.

Side Story 3-1: 4 + 1 Reasons Every Math Wizard needs a Spellbook

Image credit: Still from The Lord of the Rings: The Fellowship of the Ring (2001)

Collating and summarizing information on the fly can greatly reduce Ring identification time.

I couldn't resist the title pun, though I have a very strong opinion on the term "math wizard". (If you look at the etymology of the word wizard, "one who is wise" would seem to jive properly. But nowadays wizards are seen as dabblers in magic and unnatural arts, which couldn't be further from mathematics. Moreover, I think there's something remiss in labelling promising students in mathematics as "wizards" in their craft when competitive mathematics isn't exactly the mathematics people make careers [academic and otherwise] out of. High school / contest math is to real [i.e. modern] math as Gandalf's fireworks are to Gandalf's defeating the Balrog; in other words, they are in a completely different scale of wizardry. But I digress.)

Anyway, I think any serious mathlete should have a notebook to write the formulae and strategies (s)he picks up along the way, a Secret Book of Spells if you must.

The Codex 3-1: How Many Shapes?

The Codex

This is the first of the articles in The Codex, which is an attempt at a comprehensive manual for intermediate to pre-Olympiad level mathletes. Accordingly, the Codex Articles will typically be produced in PDF format for easy download and printing.

This first one compiles our four-part journey through the surprisingly sophisticated art of shape counting.

Problem Post 3-1: How many Shapes, Part 4: Triangles

		Problem Posts
		Part 4 of 4 in How Many Shapes?

[Level 3]

So last time we finished off the dreary onus of counting rectangles in rectangles. Now for something completely different.

CAN WE DO BETTER?

• What if the original grid were a rectangle, instead of a square? Or an irregular figure?
• What if we were counting rectangles instead of squares?
• What if some of the grid 'wires' are missing?
• What if we're working on a triangular grid, counting triangles? Does our logic still apply?

3 Triangles!

This one was surprising to say the least. I had hoped to find a straightforward formula like in counting rectangles, but it turns out triangle counting is nastier than one might think!