187 – Quiz 9

April 13, 2010

Here is quiz 9.

Problem 1 asks to show that if three numbers are given, each a power of 2 or of 3, or a product of powers of 2 and 3, then either one of these three numbers is a square, or else the product of some of them is a square.

Each of these numbers, and their products, can be written in the form $2^a3^b$ with $a,b\in{\mathbb N}.$ A number of this form is a square if and only if both $a$ and $b$ are even.

To a number $2^a3^b$ we associate its “pattern of parities,” the pair $(a\mod2,b\mod 2).$ Note that if $n$ has pattern $(p,q)$ and $m$ has pattern $(r,s),$ then their product has pattern $((p+r)\mod2,(q+s)\mod2).$

If one of the three numbers has pattern $(0,0),$ we are done. If two of the numbers have the same pattern, their product is a square, and we are done. So we may assume that the numbers have patterns $(0,1),$ $(1,0),$ and $(1,1).$ But then the product of the three of them is a square.

More generally, one can check that if $r+1$ positive integers are given ( $r\ge1$), and their prime factorizations together involve only $r$ primes, then there is a (non-empty) subset of these integers whose product is a square. Try to show this as an extra credit problem.

Problem 2 asks to show that if 9 lattice points are given in ${\mathbb R}^3,$ there are two such that the midpoint of the segment they determine is also a lattice point. Here, a lattice point is a point all of whose coordinates are integers.

As before, associate to each lattice point $(a,b,c)$ its pattern of parity, $(a\mod2,b\mod2,c\mod2).$ Note that the midpoint of the segment joining $(a,b,c)$ and $(d,e,f)$ is $\displaystyle \bigl(\frac{a+d}2,\frac{b+e}2,\frac{c+f}2\bigr).$ It follows that this midpoint is a lattice point iff $(a,b,c)$ and $(d,e,f)$ have the same pattern of parity.

But there are only 8 possible patterns: each of the three coordinates is either 0 or 1. Since 9 points are given, two must have the same pattern, and we are done.

Problem 3 asks for a list of 4 distinct integers without an increasing or decreasing subsequence of length 3.

There are many possible ways of doing this. For example, $2,1,4,3.$