Show that, given a 7-digit number, you can cross out somerst 3 and the last 2 digits of 1294961 to get 49.
digits at the beginning and at the end such that the remaining
number is divisible by 7. For example, you can cross out the
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.
Suppose: $\displaystyle
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 $\displaystyle
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 $\displaystyle a\ne \dot 7$ then $\displaystyle 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 $\displaystyle
\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 $\displaystyle
7 \geqslant k > j \geqslant 1
$
Thus, substracting: $\displaystyle
\mathop {a_k ...a_{j + 1} \underbrace {0...0}_{j{\text{ zeros}}}}\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_} \equiv 0\left( {\bmod 7} \right)
$
Thus: $\displaystyle
\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: $\displaystyle
\mathop {a_k ...a_{j + 1} }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_} = \dot 7
$ which proves the assertion