2006 Indonesia MO Problems/Problem 6

Problem

Every phone number in an area consists of eight digits and starts with digit . Mr Edy, who has just moved to the area, apply for a new phone number. What is the chance that Mr. Edy gets a phone number which consists of at most five different digits?

Solution

We can do complementary counting to determine the number of phone numbers that have more than 5 different digits. We will divide into separate cases on the last seven digits.

Case 1: Two 8s, Five other numbers appearing once The two eights has seven spots available, so there are ways to place the eights. Since there are nine other digits and five available spots left for each placement of the two 8s, there are phone numbers in this case.

Case 2: One 8, Six other numbers appearing once The eight has seven spots available. Since there are nine other digits and six available spots, there are phone numbers in this case.

Case 3: One 8, Four other numbers appearing once, One other number appearing twice Consider the four solo numbers as a group and the one repeat number as a group. There are ways to place the three groups (where the remaining slot goes to the one 8). There are nine digits for the one repeat, which leaves eight distinct digits for the group of solo numbers. Thus, there are phone numbers in this case.

Case 4: Zero 8s, Seven other numbers appearing once Since there are nine other digits and seven available spots, there are phone numbers in this case.

Case 5: Zero 8s, Five other numbers appearing once, One other number appearing twice There are nine digits to choose for the digit appearing two times, and there are ways to place the recurring digit. For each placement of each repeating digit, there are eight other digits with five open slots, so there are phone numbers in this case.

Case 6: Zero 8s, Three other numbers appearing once, Two other numbers appearing twice First consider the number of ways to order the two numbers appearing twice in a four number string. One can note that in the string , there are ways to order the letters. Additionally, there are 9 possible digits for and 8 possible digits for . However, we are overcounting since and can be swapped, so there are ways to order the two numbers appearing twice in a four number string.

Now consider the number of ways to order . There are ways to order the letters. The letter represents the group of numbers that appear twice, which are already ordered in the above paragraph. That leaves three slots left with 7 available digits, so there are a total of phone numbers in this case.

Case 7: Zero 8s, Four other numbers appearing once, One other number appearing three times There are nine digits to choose for the digit appearing three times, and there are ways to place the recurring digit. For each placement of each repeating digit, there are eight other digits with four open slots, so there are phone numbers in this case.

Adding up all the cases results in a total of phone numbers with more than five distinct digits. The total number of phone numbers is , so there are phone numbers with at most five distinct digits. Thus, the probability that Mr. Edy gets a phone number with at most five distinct digits is .

Python Code

Although Python programs are not allowed in the Indonesia MO, a computer program can be used to manually count every single phone number that has at most 5 distinct digits.

 count = 0
 number = [0,0,0,0,0,0,0]
 for i in range(0,10000000):
 
     # Reset
     numberlist = [0,0,0,0,0,0,0,0,1,0]
 
     # Count Digit
     for digit in number:
         numberlist[digit] += 1
 
     # Count Zeroes (we want 5 or less)
     zerocounter = 0
     for result in numberlist:
         if result == 0:
             zerocounter += 1
     if zerocounter >= 5: #since at most 5 digits are used, at least 5 digits are unused
         count += 1
   
 
     # Next Number
     number[len(number)-1] += 1
 
     # Regroup if Necessary
     for j in range(0,len(number)):
         if number[len(number)-1-j] == 10:
             number[len(number)-1-j] = 0
             if len(number)-1-j > 0:
                 number[len(number)-2-j] += 1
 
 print(count)

The computer program verifies that there are phone numbers that satisfies the conditions, which confirms that the probability is .

See Also

2006 Indonesia MO (Problems)
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8	Followed by Problem 7
All Indonesia MO Problems and Solutions