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 with A number of this form is a square if and only if both and are even.

To a number we associate its “pattern of parities,” the pair Note that if has pattern and has pattern then their product has pattern

If one of the three numbers has pattern 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 and But then the product of the three of them is a square.

More generally, one can check that if positive integers are given (), and their prime factorizations together involve only 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 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 its pattern of parity, Note that the midpoint of the segment joining and is It follows that this midpoint is a lattice point iff and 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,

This entry was posted on Tuesday, April 13th, 2010 at 10:59 am and is filed under 187: Discrete mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.