Results 1 to 3 of 3

Math Help - Pigeonhole and SS numbers

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    56

    Smile Pigeonhole and SS numbers

    Two social security numbers "match zeros" if a digit of one number is zero iff the corresponding digit of the other is zero.

    Ex. 120-90-1109
    430-20-5402

    these numbers match zeros.

    Prove: Given 513 SS numbers, there must be at least two that match zeros.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    A 9-bit string is a string of length 9 made of 0’s & 1’s.
    There are 2^9 =512 different 9-bit strings.
    If we have a collection of 513 9-bit strings then at least two are equal.
    Now think of a SS#, change all the nonzero digits to 1’s.
    EX: 120-90-1109 becomes 110101101 & 430-20-5402 becomes 110101101.
    That is one 9-bit string. Can you finish?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    Posts
    56
    That's a good way to look at it!

    Then by the pigeonhole principle, an axiom that we must believe to hold true, we can conclude that : if we have 513 strings , and only 512 possible strings, then two or more of the strings must be identical (in terms of 0's).
    More precisely, - two of the strings "match zeros"

    Awesome!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: August 27th 2011, 08:26 AM
  2. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  3. help me with pigeonhole principle #3
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 06:38 PM
  4. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum