here's the problem:(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Interesting problem with possible solution

Loading...

Similar Threads for Interesting problem possible | Date |
---|---|

(another)interesting number theory problem | Jan 15, 2012 |

Interesting number theory-related problem. | Oct 4, 2011 |

Interesting modular arithmetic problem I found | Aug 2, 2011 |

Interesting problem from my analysis class | Nov 1, 2005 |

**Physics Forums - The Fusion of Science and Community**