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?

There are 9! = 362,880 such numbers with 10 digits beginning with the digit 9, so the 200,136th will be one of these.

For any given second digit (after the first is set at 9), there will be 8!=40,320 possible numbers. So we have to bypass the 8's, 7's, 6's and 5's (accounting for 4 * 40,320 numbers) and arrive at the 38,856th (the remainder) 10-digit number beginning 94.

There are 7!=5040 10-digit numbers beginning 94 for each possible third digit, so we have to bypass 7 possibilities: 8, 7, 6, 5, 3, 2 and 1, leaving 0.  The first three digits are 940.

There are 6! = 720 10-digit numbers beginning 940 for each possible fourth digit, and we need the 3576th such (the remainder from the previous division). So we need to bypass 4 possibilities: 8, 7, 6 and 5. Therefore the next digit is 3. So far we have 9403.

We need the 696th 10-digit number starting 9403.

There are 5!=120 10-digit numbers beginning 9403 for each possible fifth digit, and we need the 696th such. So we bypass 5 possibilities: 8, 7, 6, 5 and 2, bringing us to 1. So the number starts 94031.

There are 4!=24 10-digit numbers beginning 94031 for each possible sixth digit, and we need the 96th such number. But 24 divides evenly into 96, so we take tha last number in the 4th group--the 4th group being the one wehere the sixth digit is not 8, not 7, not 6, but 5. The number begins 940315, and is the last such number in the descending sequence.  The unused digits are 2, 6, 7 and 8, and when arranged in this order, are the lowest such.

So at the end we get 9,403,152,678. (unless I've made a mistake somewhere).

Posted by Charlie on 2006-02-02 12:23:32