September 18, 2007

A Few More Number Theory Problems

Two more “introductory” problems from “104 Number Theory Problems:”

1.  Let  x,  y,  z  be positive integers such that

1/x      1/y   =  1/z.

Let  h  be the greatest common divisor of  x,  y,  z.   Prove that  hxyz  and  h(y – z)

are perfect squares.

2.  Prove that any number consisting of  2n  identical digits has at least  n  distinct prime factors.

Three actual Putnam problems:

3.  (2000 Putnam, A-2)  Prove that there exist infinitely many integers  n  such that  n,  n+1,  n+2  are each the sum of the squares of two integers.  [Example:  0 = 02 + 02,  1 = 02 + 12,  2 = 12 + 12.]

4.  (1999 Putnam, B-6)  Let  S  be a finite set of integers, each greater than  1.  Suppose that for each integer  n  there is some  s Î S  such that  gcd(sn) = 1  or  gcd(s, n) = s.  Show that there exist  s, t Î S  such that  gcd(s, t)  is prime.

(not number theory, but a good game problem…)

5.  (1995 Putnam, B-5)  A game starts with four heaps of beans, containing 3, 4, 5, and 6 beans.  The two players move alternately.  A move consists of taking EITHER

(a)  one bean from a heap, provided that at least two beans are left behind in that heap,              OR

(b)  a complete heap of 2 or 3 beans.

The player who takes the last heap wins.  To win the game, do you want to move first or second?  Give a winning strategy.

(end)