Stones, Prime Powers, Induction ProofDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/