Stones, Prime Powers, Induction Proof

Date: 01/23/2001 at 12:45:28
From: Tinka
Subject: Proof

A heap of 201 stones is divided in several steps into heaps of three 
stones each. One step is to choose one heap, remove one stone from it, 
and divide the rest of it into two heaps. Is this possible if each 
step has to be carried out completely? One heap contains of at least 
one stone.

The answer has to be proved.

I came to the conclusion that this is not possible, because before the 
last step there have to be 7 stones. If you carry out one step you can 
divide the rest of the heap into a heap with 3 stones and another 
one. This would mean it would be possible to divide 201-7 by 4, but 
this is not possible. 

My problem is that I don`t know how to prove that it is not possible 
either if the rest or the heap is divided into heaps that do not 
consist of 3 stones. I hope that you can help me with my problem. 
Thanks a lot.

Date: 01/23/2001 at 16:49:18
From: Doctor Rob
Subject: Re: Proof

Thanks for writing to Ask Dr. Math, Tinka.

This problem can be solved by working backward. If you start with
several heaps of size 3, and combine two of them plus 1 stone, you
get a heap of size 7. Notice that 3 and 7 both leave remainder 3 when 
divided by 4. Whenever you combine two heaps and add one stone, you 
create a new heap whose size also leaves a remainder of 3 when divided 
by 4. 201 leaves a remainder of 1 when divided by 4.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 01/27/2001 at 16:09:12
From: Tinka
Subject: Proof

Prove that every full positive number (1,2,3,4...) has not fewer 
divisors ending with 1 or 9 than divisors ending with 3 or 7.

I thought about solving the problem by dividing the number into 
primes, e.g. 42 = 2 x 3 x 7. Concerning this problem only the numbers 
ending with 1,3,7,9 are important, because numbers with other endings 
can be multiplied by any number but they never become a number ending 
with 1,3,7, or 9.

In the case of 42 the divisors ending with 1;3;7;9 would be.
1
3
7
21

I have no idea how to continue. I hope you can help me. Thank you very 
very much.

Date: 01/31/2001 at 14:17:36
From: Doctor Rob
Subject: Re: Proof

Prove this first for prime numbers.  Then prove it for prime powers.
Then show that if it holds for n and m, and GCD(n,m) = 1, then it
holds for n*m.  Put these together with the Unique Factorization
Theorem (or Fundamental Theorem of Arithmetic), and you get the
result you seek.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/01/2001 at 11:51:05
From: Tinka
Subject: Proof

I know how to prove it for prime numbers, but then you said I have to 
prove it for prime powers. I think I know how to do that but I do not 
understand why I have to prove it for prime powers. Could you please 
explain the rest of your answer a bit more?

Thank you very very much.

Date: 02/01/2001 at 14:08:39
From: Doctor Rob
Subject: Re: Proof

Thanks for writing back, Tinka.

You can prove by induction the result you want. It is true for
n = 1, n = 2, and so on. Assume the theorem is true for all numbers
k < n, and try to prove it for n. Let p be a prime number dividing n,
let p^e the highest power of p dividing n, and let m = n/p^e. Then
p^e and m have GCD 1.  If the theorem is known to be true for prime
powers, and is true for m < n by the induction hypothesis, you want to
assert that that implies that the theorem is true for n. That is why
you want to know that it is true for powers of primes like p^e, and
that if it is true for two numbers with no common factor other than 1,
it is true for their product. If you knew these two facts, you would
be done with the induction.

Powers of a prime will be fairly easy. The other statement, that if it 
holds for r and m, and GCD(r,m) = 1, then it holds for r*m, is a 
little harder.

If d is a divisor of r*m and r and m have GCD(r,m) = 1, then d = e*f,
where e is a divisor of r and f is a divisor of m. You can find e and
f by using e = GCD(d,r) and f = GCD(d,m). That means that the list of
divisors of r*m can be gotten by multiplying all the divisors of r
times all the divisors of m. For example, all the divisors of
1323 = 3^3 * 7^2 can be found by multiplying all the divisors of
3^3 = 27 times all the divisors of 7^2 = 49. Thus you can multiply the 
numbers in the set {1,3,9,27} times the numbers in the set {1,7,49}.
When you do this, you get

   1*1   3*1   9*1   27*1
   1*7   3*7   9*7   27*7
   1*49  3*49  9*49  27*49

which is a list of all the divisors of 1323.  This doesn't work if r
and m are not relatively prime.

Now use the following facts:

1. When you multiply a number ending in 1 or 9 by a number ending in 1
   or 9, you get another number ending in 1 or 9.

2. When you multiply a number ending in 1 or 9 by a number ending in 3
   or 7, you get another number ending in 3 or 7.

3. When you multiply a number ending in 3 or 7 by a number ending in 3
   or 7, you get another number ending in 1 or 9.

4. Multiplying numbers with any other combination of ending digits can
   never give you a number ending in 1, 3, 7, or 9.

Let S be the divisors of r, and s19 be their number ending in 1 or 9,
and s37 be their number ending in 3 or 7.  We are assuming that the
theorem holds for r, so s19 >= s37.  Let T be the divisors of m, and
t19 be their number ending in 1 or 9, and t37 be their number ending
in 3 or 7. We are also assuming that the theorem holds for m, so
t19 >= 37. Then in the set of products S*T, there are exactly
s19*t19 + s37*t37 numbers ending in 1 or 9 (see facts 1, 3, and 4
above), and exactly s19*t37 + s37*t19 numbers ending in 3 or 7 (see
facts 2 and 4 above).  Your job is to show that

   s19*t19 + s37*t37 >= s19*t37 + s37*t19.

That will prove that if the theorem holds for r and for m, and
GCD(r,m) = 1, then it holds for r*m.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/