Pigeonhole principle - divisibility by $7$. 
Take a natural number $x$ that has $7$ digits. Show that we can delete consecutive digits from it's start or from it's end (or both), such that the number we end with is divisible by $7$ (we can delete 6 digits or less). 

For example if $x=1122334$, We can delete the $2334$ in it's end and get $112$ which is divisible by $7$. 
I am not sure how to approach it, can anyone provide a hint or a solution? The only thing I noticed is that if $x$ contains a $0$ or a $7$ as a digit then we are done. Thanks
 A: Take the sequence of truncations from the right : for example, in the given case we get the set $\{4,34,334,2334,22334,122334,1122334\}$. Now, in this set, if any element is divisible by $7$ we are done, since it is formed by removal of digits from the right.
If not, then there are only six remainders modulo $7$, so two of these have the same remainder modulo $7$. Take the longer one, and remove the digits of the shorter one from it. That number gives a multiple of $7$.
So, for example, in the above example, $2334$ and $1122334$ have the same remainder modulo $7$, so the removal of digits leads to $112$ which is a multiple of $7$.
To give another example, let us take $2544111$, for which the set $\{2544111,544111,44111,4111,111,11,1\}$ contains no multiple of $7$. However, note that $44111$ and $11$ leave the same remainder modulo $7$ so removing the digits gives $441$ which is a multiple of $7$. Also, $544111$ and $1$ leave the same remainder modulo $7$, so $54411$ is a multiple of $7$.

Something to consider : Can this be generalized to say $9,11,13$ with similar proof?
