187 – Quiz 9

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: