1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigenhole principle

  1. Aug 20, 2011 #1
    Let T={0,1,2} so that T^11 represents the set of all strings of eleven digits of T.
    a)for every T=T_1T_2...T_11 show that there is a pair T_iT_i+1 of consecutive digits that is repeated using the pigenhole principle.
    b)Find a string from T of 10 digits where no repetition exists.
    c)Find with justification a postive integer N such that every string of N digits of T contains a repeated triple T_iT_i+1T_i+2.

    Answers:
    a)Since there are 9 possible pairs and 11 digits one pair will be contained at least once in the string.Is this correct?
    b)0011220102.
    c)I don't know.How should I proceed?

    [
     
  2. jcsd
  3. Aug 20, 2011 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Yeah, that's right.
    Try again!
    Think about why you can write a 10-digit number with no pairs repeating but not an 11-digit number. How would you generalize this to the case of triples?
     
  4. Aug 21, 2011 #3
    b)2001022112
    c)There are 27 different triples
    a string of n digist must have n-2 triples in it,we are substracting the last 2 digits.
    So 28+2=30 will work.(or I could just look in terms of 27+another triple(3)=30)
     
  5. Aug 21, 2011 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Good job!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Pigenhole principle
  1. Maximum principle (Replies: 4)

  2. Variational principle (Replies: 0)

  3. D'Alembert's principle (Replies: 0)

  4. Pigeonhole Principle (Replies: 1)

  5. Duality principle (Replies: 2)

Loading...