# Math Help - pigeonhole principle

1. ## pigeonhole principle

Show that, given a 7-digit number, you can cross out some
digits at the beginning and at the end such that the remaining
number is divisible by 7. For example, you can cross out the
rst 3 and the last 2 digits of 1294961 to get 49.

2. i know this problem uses the pigeonhole principle but i can't get to a point where i can use it. i would like to be able to remove a digit and somehow prove that each resulting number mod 7 is different. this is what i can't get to happen. at that point we could use the pigeonhole principle and say that one of the resulting numbers has to equal 0 mod 7.

3. Suppose: $
x = \mathop {a_7 a_6 a_5 a_4 a_3 a_2 a_1 }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_} = 10^6 \cdot a_7 + ... + 10^0 \cdot a_1
$

If some of the numbers $
a_1 ;\mathop {a_2 a_1 }\limits^{\_\_\_\_\_\_\_} ;...;\mathop {a_7 a_6 a_5 a_4 a_3 a_2 a_1 }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_\_}
$
is already multiple of 7 we are done. Then assume that none of them is multiple of 7.

Remember now that if $a\ne \dot 7$ then $a\equiv{1,2, 3, ..., 6}(\bmod.7)$ that is we have 6 possible remainders, but we have 7 numbers, thus 2 of them are congruent mod 7.

That is $
\mathop {a_k ...a_1 }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_} \equiv \mathop {a_j ...a_1 }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_} \left( {\bmod 7} \right)
$
for some natural numbers j and k such that $
7 \geqslant k > j \geqslant 1
$

Thus, substracting: $
\mathop {a_k ...a_{j + 1} \underbrace {0...0}_{j{\text{ zeros}}}}\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_} \equiv 0\left( {\bmod 7} \right)
$

Thus: $
\mathop {\dot 7 = a_k ...a_{j + 1} \underbrace {0...0}_{j{\text{ zeros}}}}\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_} = 10^j \cdot \mathop {a_k ...a_{j + 1} }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}
$
but (10, 7)=1 thus: $
\mathop {a_k ...a_{j + 1} }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_} = \dot 7
$
which proves the assertion

4. Thanks!

5. that's pretty brilliant, my friend! i cannot believe you're only 18!!