Brain Teaser with combinatorics

[chimpfunkz]

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 definitely 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?

 

[skeptic2]

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

 

[awkward]

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.

 

[safemotionguy]

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.

 

[awkward]

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.

 

[safemotionguy]

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.

 

[awkward]

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.