Combinatorics | Diabolical or Smart

The 24th problem of Project Euler wanted the one-millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

This was yet another problem which I solved with paper and pencil.

We determine one digit at a time. Say the most significant digit is x, then the remaining 9 digits can fill up the remaining places of the 10 digit number. This can be done in 9! = 362880 ways.

362880 X 2 < 1000000 < 362880 X 3

This implies that all the numbers with 0 and 1 as the most significant digits make up 362880 X 2 numbers, which is less than a million, and when we start with 2 as the most significant digit, the one millionth number comes before the series is over. Thus our first digit is 2.

Now with that fixed, we need to find the 1000000 – 2 X 362880 = 274240th number arranged lexicographically using digits 0, 1, 3, 4, 5, 6, 7, 8 and 9. This time we need to consider 8! = 40320.

40320 X 6 < 274240 < 40320 X 7

Thus we need the 7th digit which is 7. So our number starts with 27.

The same step is to be repeated over and over again. In a condensed notation, the digits found are:

9! X 2 < 1000000 < 9! X 3 => digit is 2; 1000000 – 725760 = 274240

8! X 6 < 27420 < 8! X 7 => digit is 7; 27420 – 241920 = 32320

7! X 6 < 32320 < 7! X 7 => digit is 8; 32320 – 30240 = 2080

6! X 2 < 2080 < 6! X 3 => digit is 3; 2080 – 1440 = 640

5! X 5 < 640 < 5! X 6 => digit is 9; 640 – 600 = 40

4! X 1 < 40 < 4! X 2 => digit is 1; 40 – 24 = 16

3! X 2 < 16 < 3! X 3 => digit is 5; 16 – 12 = 4

At this point the digits left are 0, 4 and 6. The 4th number ordered lexicographically will be 460.The number we set out to find is thus 2783915460.

Popularity: 38% [?]

I have gone in a very round about way, and my explanation might not be clear. Apparently, this is a very standard combinatorics problem and can be answered at sight. Well, I did not know that, and did a few things which made me realize the combinatorial answer.

The latest problem that I solved was is Problem 15. Given a grid of 20 x 20 squares, the question asked was to find the number of routes from the top left hand corner of the grid to the bottom rightmost corner without ever backtracking.

This was an easy one too. I started out by writing at every meeting point of lines, the number of extra lines that spring out of the point. For example, at the starting point 2 lines start. Select for example the horizontal one. At the first point that it comes across, it forks into 2 lines, which is 1 extra. So I wrote 1 at this point. The same is done at all points except those on the rightmost vertical and the bottommost horizontal which contains the total number of lines passing through it.

Below is a diagram showing the same thing.