- #1
- 2,570
- 2
here's the problem:
You are given a seven digit number. Prove that you can cross off some of the numbers at the beginning or the end and you'll be left with a number that is divisible by 7. For example:
1434945
Cross off the first three and last two to get 49.
I have a proof of this and I want to see if it's valid. I'll post it below, but if you want to solve this yourself don't scroll down.
Here's my proof:
Assume that none of the numbers formed by crossing off the last digit and then any number of other digits are divisible by seven. Then I will show that one of the seven numbers left (ie., those which include the last digit) must be. Take any two of these seven strings. They differ by a power of ten times one of the strings not divisible by 7, so their difference is not divisible by 7. Therefore, they are not congruent mod 7. Since all seven of these numbers are different mod 7, one of them must be equal to 0 mod 7. Is this right? I was told I'd have to use the pigeonhole principle, but I don't think i did. And I thought about the fact that it might be impossible that none of the strings not including the last digit are divisible by seven, which would mean my proof is based on a contradiction, and therefore isn't valid. But if that's true, then it implies the result anyway. Is that a valid method of proof? Second question is, how long should this problem take to solve? I got it in probably about half an hour, without paper, just walking around thinking about it. Does speed matter in math, or is it just that you get the final answer?
You are given a seven digit number. Prove that you can cross off some of the numbers at the beginning or the end and you'll be left with a number that is divisible by 7. For example:
1434945
Cross off the first three and last two to get 49.
I have a proof of this and I want to see if it's valid. I'll post it below, but if you want to solve this yourself don't scroll down.
Here's my proof:
Assume that none of the numbers formed by crossing off the last digit and then any number of other digits are divisible by seven. Then I will show that one of the seven numbers left (ie., those which include the last digit) must be. Take any two of these seven strings. They differ by a power of ten times one of the strings not divisible by 7, so their difference is not divisible by 7. Therefore, they are not congruent mod 7. Since all seven of these numbers are different mod 7, one of them must be equal to 0 mod 7. Is this right? I was told I'd have to use the pigeonhole principle, but I don't think i did. And I thought about the fact that it might be impossible that none of the strings not including the last digit are divisible by seven, which would mean my proof is based on a contradiction, and therefore isn't valid. But if that's true, then it implies the result anyway. Is that a valid method of proof? Second question is, how long should this problem take to solve? I got it in probably about half an hour, without paper, just walking around thinking about it. Does speed matter in math, or is it just that you get the final answer?