interesting problem with possible solution

[StatusX]

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 wanna see if it's valid. I'll post it below, but if you wanna 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?

[Muzza]

I was told I'd have to use the pigeonhole principle, but I don't think i did.


You used it here (without realizing it):


Since all seven of these numbers are different mod 7, one of them must be equal to 0 mod 7.

[StatusX]

i thought the pigeonhole principle was that if you put n+1 objects into n holes, there will be one hole with at least 2 in it. I put n objects in n holes, and by making sure none went in the same hole, I showed that a particular one of them must be full. isnt that different? and moreover, is my proof right?

[mathwonk]

i thought the pigeonhole principle was that if you put n pigeons into n+1 holes, there will be one hole with no pigeons in it. Or was it that if you put no pigeons into n holes there will be n holes with no pigeons?

[StatusX]

are you making fun of me? im only saying i dont think its the pigeonhole principle cause im curious if theres another solution. no pigeons in n holes leaves n holes? thats stupid.

[Muzza]

i thought the pigeonhole principle was that if you put n+1 objects into n holes, there will be one hole with at least 2 in it. I put n objects in n holes, and by making sure none went in the same hole, I showed that a particular one of them must be full. isnt that different?


*shrug* Seems like practically the same thing to me.

[matt grime]

i thought the pigeonhole principle was that if you put n+1 objects into n holes, there will be one hole with at least 2 in it. I put n objects in n holes, and by making sure none went in the same hole, I showed that a particular one of them must be full. isnt that different? and moreover, is my proof right?


and if one of the numbers weren't 0 mod 7 then you'd have to assign 7 distinct objects to 6 slots. that is the pigeon hole principle. note mathwonk is reversing the labels of holes and pigeons.

[StatusX]

o ok, i was just confused cause i thought the pigeonhole principle was for when you had no idea where the pigeons were going, you just wanted to know that two of them were in the same hole. For example, in a sentence with 27 words, at least 2 of the words (probably more) will start with the same letter. What I did would be like somehow proving every word started with a different letter, and saying that in a sentence with 26 words, one of them must start with x. I'm sorry if that's the same and I'm not seeing it, I'm just curious if theres another solution to this problem.