Let us consider all possible positive whole numbers (not containing any leading zeroes) with the proviso that in each of the numbers, none of its digits can be repeated.

Note: any given number may or may not contain all the digits from 0 to 9 (Examples: 7; 20; 1056; 3067941825 etc.)

These numbers are now arranged in descending order of magnitude.

What would be the 200,136th number?

(In reply to re: solution -- computer confirmation by Charlie)

Hello, this is my first post.

Firstly, we'd like to know How many digits this number has.  Since the problem specifies descending order from 9876543210, and the 200136th of them is less than exhausts the set of 3628800 ten digit numbers, the answer has all ten digits.

What is the first digit? Could it be a 9?
Since there are 362880 possible 9xxxxxxxxx, and we seek the 200136th of such, it is indeed a 9.

What's the second digit?
For each possible second digit d of 9dxxxxxxxx, there are 40320 (=8!) permutations of xxxxxxxx. To reach the 200136th position, we must exhaust the first 200136/40320 or 4.something d's. Thusly, we exhaust possible d's 8,7,6,5 and some of 4, but not all. So the second digit is 4.
Number is now 94xxxxxxx.
Since we have ruled out 4*8! possibilities (=161280) because we've ruled out 4 d's, we are left with 200136-161280= 38856th of the REMAINING possibilities.

What is the third digit?
For each possible d of 94dxxxxxxx, there are 5040 (=7!) permutations of xxxxxxx. To reach the 38856th remaining position, we go through about 7.7 (=38856/5040) d's. So, it's not 8, 7, 6, 5, 3, 2, or 1; it's a 0.
We've now exhausted 35280 of those 38856 possibilities, so we're looking for the 3576th possible value of 940xxxxxxx.

What about the fourth digit?
For each possible d of 940dxxxxx, there are 720 permutations. To reach the 3576th, we rule out 4.97 (but not five!) values for d. So d is not a 8, 7, 6, or 5; it is 3.
There are now 720 possible 9403xxxxxx's, and we seek the 696th (= 38856 - (4*720)) of them.

Next!
For each d of 9403dxxxxx, there are 120 permutations (see the pattern yet :). Counting to the 696th of them exhausts 5 possible d's: 8, 7, 6, 5, and 2 - leaving d=1. We now seek permutation # 96 of the remaining 120.

Onward! To Victory!!
For each 94031dxxx, 24 permutations. We're looking for the 96th, which appears to exhaust 5 possible d's. NOTE though, the 96th permutation is the LAST of the Fourth possible d value!! That means the number we seek is the LOWEST possible 940315xxxx which is 9403152678.

Posted by Bill Matthews on 2006-02-04 07:56:17