Brute force (and enlightened brute force) | Combinatorics

Sometimes you have to do things the long way. For example, you might write out twenty different possibilities, and calculate each of them by hand. This is called working by brute force. The idea is that you don’t need a ton of smarts to do this; you just need a ton of patience. In general, you should rely on brute force whenever you can solve a problem by doing up to about thirty small bits of work.

Often, you will get partway through a brute force solution when you’ll realize that you don’t actually have to list all the things in order to get to a solution. Maybe it’s enough to just write every other thing. Or maybe you can write ten things then notice some pattern in your work that makes the rest much easier. Or maybe partway through your brute force solution you notice some completely different (but easier) way to tackle the problem.

All of these are examples of enlightened brute force: you are combining brute force with some smarts, and that makes everything go better.

Try solving this problem with an enlightened brute force approach:

The $120$ permutations of $A H SME$ are arranged in dictionary order as if each were an ordinary five-letter word. The last letter of the $86$ th word in this list is:

A. $A$
B. $H$
C. $S$
D. $M$
E. $E$

(spoiler)

We can do this problem without having to list out every single combination.

There are 5 distinct letters, so therefore there are $5! = 120$ ways to rearrange the letters. We can divide the $120$ different combinations into 5 groups: words that start with $A$ , words that start with $E$ , and so on.

Combinations 1-24 start with $A$
Combinations 25-48 start with $E$
Combinations 49-72 start with $H$
Combinations 73-96 start with $M$
Combinations 97-120 start with $S$

We are only concerned with combination $86$ , so we focus on the combinations in the 73-96 group. We can divide these remaining 24 combinations into 4 subgroups of 6 each, based upon the second letter.

Combinations 73-78 start with $M A$
Combinations 79-84 start with $ME$
Combinations 85-90 start with $M H$
Combinations 91-96 start with $MS$

Combination $86$ is within the 85-90 group and will start with $M H$ .

Now we can fill in the rest of the letters in alphabetical order and get:

85 - $M H A ES$
86 - $M H A SE$

And now we know the last letter of combination 86, $M H A SE$ , is $E$ .