Results 1 to 5 of 5

Math Help - pigeonhole principle

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2008
    Posts
    5
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Suppose: <br />
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 <br />

    If some of the numbers <br />
a_1 ;\mathop {a_2 a_1 }\limits^{\_\_\_\_\_\_\_} ;...;\mathop {a_7 a_6 a_5 a_4 a_3 a_2 a_1 }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_  \_\_\_\_\_\_\_\_\_\_} <br />
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 <br />
\mathop {a_k ...a_1 }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}  \equiv \mathop {a_j ...a_1 }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_} \left( {\bmod 7} \right)<br />
for some natural numbers j and k such that <br />
7 \geqslant k > j \geqslant 1<br />

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

    Thus: <br />
\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^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_} <br />
but (10, 7)=1 thus: <br />
\mathop {a_k ...a_{j + 1} }\limits^{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}  = \dot 7<br />
which proves the assertion
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2008
    Posts
    5
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2008
    Posts
    5
    that's pretty brilliant, my friend! i cannot believe you're only 18!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 1st 2009, 12:23 AM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 04:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 04:59 PM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 04:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 07:09 PM

Search Tags


/mathhelpforum @mathhelpforum