Mathematics x Programming Competition #8 - General Solution
Last week, @kenchung posted a fun new math/programming problem. He changed the payouts to the three fastest entries receiving prizes, and at least two people submitted answers by the time I saw the blog, so I rushed out a solution by hand in 10 minutes which happened to be inaccurate, but I've since corrected my mistake and have a formula for the general case.
Problem
Ken has a four-digit calculator which displays numbers using the seven-segment-display. For example the number 159 is displayed as
Suppose we want to use non-transparent cards to represent all the possible 4-digit numbers from 0000 to 9999. Each card will show one 4-digit number, where the numbers are written using seven-segment-display. However when some cards are rotated 180°, a new number can be formed. For example when the card 0159 is rotated 180°, it becomes 6510.
Considering the possibility of rotating a card 180°, what is the minimum number of non-transparent cards required to represent all the possible 4-digit numbers from 0000 to 9999?
Problem Solution
First I'll go through the 4 digit case solution and then generalize it into a formula.
What numbers are reversible?
- 0 -> 0
- 1 -> 1
- 2 -> 2
- 5 -> 5
- 6 -> 9
- 8 -> 8
- 9 -> 6
So 3,4, and 7 flipped upside down result in an invalid number. Thus, any 4 digit number that has a 3, 4, or 7 is not reversible. This means that of the 10,000 possible 4 digit numbers, 10000 - 7^4 = 7599 can be written only one way. The remaining 2,401 are candidates to be written right side up and upside down.
Of the 2,401 remaining candidate numbers, there are some numbers that when flipped, result in the same number. 5 of the 7 reversible numbers flipped upside down are themselves, so all palindromes made of these 5 numbers (0,1,2,5,8) are themselves: for instance, 2552 flipped upside down is 2552. There are 5x5 = 25 of these numbers.
But any number with a 6 or 9 in it gets a little tricky. For instance 2662 is not itself, it's 2992, but 2692 -> 2692! And 6666 -> 9999, but 6699 -> 6699. How many of these numbers are there?
2x5 [69,01258] + 5x2 [01258,69] + 2x2 [69,69] = 24.
Thus, the minimum number of cards we need to use is:
7599 (unreversible numbers) + (2401-25-24)/2 + 25 + 24 = 8,824!
General Solution for Even Numbers
If you noticed above, there were 25+24 = 49 numbers that were itself when flipped upside down. This is just 7^2. So creating a formula for even numbers is simple:
Assume we have an even number that is 2N digits long
10^2N - 7^2N + (7^2N - 7^N)/2 + 7^N, when simplified:
minimum cards with even digits = 10^2N - (7^2N - 7^N)/2
Let's plug in a few values for N to check the result:
when N = 1, we have 2 digit numbers. Our formula gives 10^2 - (7^2 - 7)/2 = 100 - 21 = 79.
when N = 2, we have 4 digit numbers. Our formula gives 10^4 - (7^4 - 7^2)/2 = 10000 - 2352/2 = 10000 - 1176 = 8824.
General Solution for Odd Numbers
Odd numbers are a little trickier -- the middle number is only part of a palindrome if it is a 0,1,2,5,8!
So suppose we have 2n+1 digits. Approach it the same way:
- There are 10^(2n+1) - 7^(2n+1) non reversible numbers
- There are 7^n*5 palindromes (the center number can only be 5 choices)
Thus, we have 10^(2n+1) - 7^(2n+1) + 5x7^n + (7^(2n+1) - 5x7^n)/2, which reduces to:
minimum cards with odd digits = 10^(2n+1) - (7^(2n+1) - 5x 7^n)/2
when n = 0: 10 - (7-5)/2 = 9. Confirmed as 6/9 are duplicates and the other 8 numbers are necessary.
when n = 1: 10^3 - (7^3 - 35)/2 = 1000 - (308)/2 = 1000 - 154 = 846
This method was a little slower than the programming approaches
However, if the question was for a 16 digit number, having the general formula is quicker than a brute force method.
My name is Ryan Daut and I am a professional gambler. My interests include dogs, poker, fantasy sports, football, basketball, MMA, health and fitness, rock climbing, mathematics, astrophysics, cryptocurrency, and computer gaming.