123456

If all 720 permutations of the digits 1 through 6 are arranged in numerical order from least to greatest, what is the 409th permutation? Note that 123456 is the first permutation, 123465 is the second, and so on.
Source: mathcontest.olemiss.edu 10/8/2007

SOLUTION
Since 720=6\times 120, there are 6 groups of 120 permutations in each group. Each group is further divided into 5 subgroups of 24 permutations in each subgroup. We list in increasing order the contents of the 6 groups below.

Group 1
123456\rightarrow 126543: 1 through 24. The first permutation through the twenty-fourth permutation with 123456 being the first permutation and 126543 the twenty-fourth permutation.
132456\rightarrow 136542: 25 through 48
142356\rightarrow 146532: 49 through 72
152346\rightarrow 156432: 73 through 96
162345\rightarrow 165432: 97 through 120

Group 2
213456\rightarrow 216543: 121 through 144
231456\rightarrow 236541: 145 through 168
241356\rightarrow 246531: 169 through 192
251346\rightarrow 256431: 193 through 216
261345\rightarrow 265431: 217 through 240

Group 3
312456\rightarrow 316542: 241 through 264
321456\rightarrow 326541: 265 through 288
341256\rightarrow 346521: 289 through 312
351246\rightarrow 356421: 313 through 336
361245\rightarrow 365421: 337 through 360

Group 4
412356\rightarrow 416532: 361 through 384
421356\rightarrow 426531: 385 through 408
431256\rightarrow 436521: 409 through 432
451236\rightarrow 456321: 433 through 456
461235\rightarrow 465321: 457 through 480

For completeness we will list Groups 5 and 6 even though we have found the answer: the 409th permutation is 431256.

Group 5
512346\rightarrow 516432: 481 through 504
521346\rightarrow 526431: 505 through 528
531246\rightarrow 536421: 529 through 552
541236\rightarrow 546321: 553 through 576
561234\rightarrow 564321: 577 through 600

Group 6
612345\rightarrow 615432: 601 through 624
621345\rightarrow 625431
: 623 through 648
631245\rightarrow 635421: 649 through 672
641235\rightarrow 645321: 673 through 696
651234\rightarrow 654321: 697 through 720

Answer: 431256.

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s