Thread: Counting

Let , an odd natural number.
The numbers with digits are written on a paper.
(Numbers can start with 1 or more zeros)
Two numbers are considered equivalent if a number after turning the paper upside down is the same as the other number.
For example: is equivalent with . (Because 0,1,6,8,9 give the numbers 0,1,9,8,6 after turning the paper upside down.)

Determine how many not-equivalent numbers there are.
Any ideas?

I'm going show how to find the number of numbers that *do* have an equivalent; you can subtract it from the total for those that don't.

First of all, it's clear that only numbers made of 0,1,6,8,9 can have an equivalent. Any that have any of the digits 2,3,4,5,7 do not (I assume 2 is not the same upside-down). There are numbers made of only 0,1,6,8,9.

Of these numbers, all have an equivalent *except* those that are equivalent to themselves (for example, if n=5, 06190 is equivalent to itself). Since n is odd, there must be a middle number. For the numbers that are equivalent to themselves the middle number can be either 0,1, or 8 (3 choices). For each middle number, you only need to consider the numbers on the left side of the middle, since there is only one possibility on the right side for any combination on the left side. There are (n-1)/2 numbers on the left of the middle, and they can be any combination of 0's, 1's, 6's, 8's, and 9's. So there are numbers that are equivalent to themselves for each middle number. 3 middle numbers means total numbers that are equivalent to themselves.

Therefore, the total number of numbers that *do* have an equivalent is .