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!

Brain Teaser with combinatorics

  1. Mar 9, 2012 #1
    I had a brain teaser that I was hoping you could solve:

    "In order to guarantee all emergency call are received, the phone company wants all phone nubers with 9 follower by 2 1's to be routed to 9-1-1 emergency center. This will ensure that any real emergency victims will still get help they require regardless of whether or not they hit extra keys. The digits 9-1-1 do not need to be consecutive but they do need to be in that order (e.g. 198-8141 would get routed to 9-1-1 but 514-9313 would not be since 9 is only followed by one 1.) How many 7 digit phone numbers would not be able to be used, since they would be routed to the 9-1-1 emergency center? assume all 7 digit phone numbers are available, from 000-0000 to 999-9999."

    What do you think the answer is?

    I worked it as a binomial, so I did

    sum sum (i bin n), n=2 to i, i=2 to 6

    but this gave me 99, which is definately incorrect.

    I also tried to do it as a binomial probability, and did it as

    sum ( sum (i bin n) (.1)^n (.9)^(i-n))), n=2 to i, i=2 to 6
    which gave me approximately .2860250, which is 2, 860 250 out of the 10000000 possible combinations
    Am I right?
     
    Last edited: Mar 9, 2012
  2. jcsd
  3. Mar 9, 2012 #2
    Hmmm, I got 35.

    xxxx911 xx911xx x91x1xx 9x1xx1x
    xxx9x11 x9xxx11 x911xxx 9x1x1xx
    xxx91x1 x9xx1x1 9xxxx11 9x11xxx
    xxx911x x9xx11x 9xxx1x1 9x1xxx1
    xx9xx11 x9x1xx1 9xxx11x 91xxx1x
    xx9x1x1 x9x1x1x 9xx1xx1 91xx1xx
    xx9x11x x9x11xx 9xx1x1x 91x1xxx
    xx91xx1 x91xxx1 9xx11xx 911xxxx
    xx91x1x x91xx1x 9x1xxx1
     
  4. Mar 10, 2012 #3
    Chimpunkz,

    You need to count all the strings of 7 digits which contain 911 as a substring. I don't think you have done this. You might try some smaller problems first. For example, what if the string is only 3 digits long? 4 digits?

    This is a tricky problem, because it's hard to avoid counting some of the arrangements more than once.
     
  5. Mar 12, 2012 #4
    This came up as the qualifying quiz for a booth giveaway for an iPad at University of Illinois Urbana Champaign’s Engineering Open House last Friday (day of the post). I solved it while driving home with a slightly different method than just walking across the possibilities as skeptic2 did but his is more visual.
    My logic:
    Of the 7 positions, if the first 2 positions are 91, there are 5 additional positions for the final 1 => 1 x 5
    If the first 1 is in the third position, there are 2 places for the 9 (cases are 9x1 or x91) and there are 4 additional positions for the final 1 => 2 x 4
    If the first 1 is in the fourth position, there are 3 places for the 9 (cases are 9xx1 or x9x1 or xx91) and there are 3 additional positions for the final 1 => 3 x 3
    If the first 1 is in the fifth position, there are 4 places for the 9 (cases are 9xxx1, x9xx1, xx9x1 or xxx91) and there are 2 additional positions for the final 1 => 4 x 2
    If the first 1 is in the sixth position, there are 5 places for the 9 (cases are 9xxxx1, x9xxx1, xx9xx1, xxx9x1, or xxxx91) and there is only 1 additional position for the final 1 => 5 x 1
    Result is (1 x 5) + (2 x 4) + (3 x 3) + (4 x 2) + (5 x 1) = 35.
     
  6. Mar 12, 2012 #5
    Guys,

    Those of you who propose 35 as the answer have not solved the original problem. You have counted arrangements of 9-1-1. You have not counted the number of possible 7-digit numbers that do not contain 9-1-1 as a substring. There are many more of these than 35.
     
  7. Mar 13, 2012 #6
    Once the 35 cases are defined, the number combinations in each case depends on the possibilities in each position of the x. If the x is before the first 9, it cannot be 9 so there are only 9 possibilities in each position. Between the first 9 and the last 1, the x cannot be 1 so there are 9 possibilities in each position. After the 911 sequence is completed, an additional 9 or 1 can occur, so there are 10 possibilities in each position.

    Rearranging skeptic2’s full list of cases based on the number of trailing x’s :
    xxxx911 xxx911x xx911xx x911xxx 911xxxx
    xxx9x11 xx9x11x x9x11xx 9x11xxx
    xxx91x1 xx91x1x x91x1xx 91x1xxx
    xx9xx11 x9xx11x 9xx11xx
    xx9x1x1 x9x1x1x 9x1x1xx
    xx91xx1 x91xx1x 91xx1xx
    x9xxx11 9xxx11x
    x9xx1x1 9xx1x1x
    x9x1xx1 9x1xx1x
    x91xxx1 91xxx1x
    9xxxx11
    9xxx1x1
    9xx1xx1
    9x1xxx1
    91xxxx1

    The result is 15 cases with 0 trailing x’s => 15 x (9^4) x (10^0)
    Plus 10 cases with 1 trailing x => 10 x (9^3) x (10^1)
    Plus 6 cases with 2 trailing x’s => 6 x (9^2) x (10^2)
    Plus 3 cases with 3 trailing x’s => 3 x (9^1) x (10^3)
    Plus 1 case with 4 trailing x’s => 1 x (9^0) x (10^4)

    The total is {15 x (9^4) x (10^0)} + { 10 x (9^3) x (10^1)} + { 6 x (9^2) x (10^2)} + {3 x (9^1) x (10^3)} + {1 x (9^0) x (10^4)}
    = {15 x 6561 x 1} + { 10 x 729 x 10} + { 6 x 81 x 100} + {3 x 9 x 1000} + {1 x 1 x 10000}
    = 98415 + 72900 + 48800 + 27000 + 10000
    = 256915

    So 256,915 (or 2.57% of the 10,000,000 7-digit numbers) would be unavailable because they would trigger a 911 call.
     
  8. Mar 13, 2012 #7
    safemotionguy,

    Congratulations! I think you are correct.

    Another approach is to count all the numbers which are not acceptable, breaking the possibilities into cases based on the position of the leftmost 9, which will give the same answer in the end.
     
    Last edited: Mar 13, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Brain Teaser with combinatorics
  1. Game show brain teaser (Replies: 4)

  2. Brain Teaser (Replies: 0)

Loading...