280,680 views
39 votes
39 votes
If all possible rearrangements of the word REVISIONS are sorted alphabetically, the n-th word is VISIONERS. What is the remainder when n is divided by 100?

User Adnan Yaseen
by
3.1k points

1 Answer

17 votes
17 votes

Answer:

75

Explanation:

You want the remainder when n is divided by 100, where VISIONERS is the n-th word in the alphabetically-ordered list of the permutations of REVISIONS.

Lexicographical order

The letters of the word REVISIONS are, in alphabetic order, are EIINORSSV. We notice there are two each of the letters I and S.

When the permutations of the letters of REVISIONS are written in lexicographical order, the list will first have all of the permutations beginning with E, then those beginning with I, and so on until the permutations beginning with S are exhausted.

Counting permutations

To find the rank (number n) of the first permutation beginning with V, we must count the number of permutations ahead of it in the list. This will be the sum of the numbers of permutations beginning with E, I, N, and so on through S.

The straightforward way to do this is to consider the letters individually, and the number of permutations associated with each one. For example, the letters following E will be the 8 letters IINORSSV, which have two repeat pairs. The number of permutations of these 8 letters is 8!/(2!·2!) = 10080.

The next leading letter in the list is I, which can be followed by any of the letters EINORSSV, for a total of 8!/2! = 20160 permutations.

The letter N will be the next leading letter, and it will have a number of permutations equal to the number for the letter E, 10080.

At this point, we have exhausted 4 of the 8 letters that must precede V in the ordered list, and have counted 10080 +20160 +10080 = 40320 permultations. We notice this is, in effect, 10080 permutations per letter, the number of permutations of the letters not including V.

If we were to work through the remaining letters (including the repeated S), we would find the total to be 8·10080 = 80640 permutations before any starting with V.

Effectively, our formula for the number of added permutations preceding words matching up to the k-th letter of our target word is ...

p(9-k)!/q

where p is the number of letters in the (remaining) ordered letter list preceding the k-th letter of VISIONERS, and q is the factor that compensates for repeated letters among those remaining. "q" is the product of the factorials of the number of times a letter is repeated. For 2 letters, each repeated once, q = 2!·2! = 4.

Application of the formula

V is the 9th letter of EIINORSSV; there are 8 letters preceding, including 2 repeated twice. k=1, so there are 8·(9-1)!/(2!·2!) = 80640 permutations preceding ones starting with V.

I is the 2nd letter of EIINORSS; there is 1 letter preceding, including 2 repeated twice. k=2, so there are 1·(9-2)!/(2!·2!) = 1260 permutations preceding ones starting with VI.

S is the 6th letter of EINORSS; there are 5 letters preceding, including 1 repeated twice. k=3, so there are 5·(9-3)!/2! = 1800 permutations preceding ones starting with VIS.

I is the 2nd letter of EINORS; there is 1 letter preceding, with no repeats. k=4, so there are 1·(9-4)! = 120 permutations preceding ones starting with VISI.

O is the 3rd letter of ENORS; there are 2 letters preceding. k=5, so there are 2·(9-5)! = 48 permutations preceding ones starting with VISIO.

N is the 2nd letter of ENRS; there is 1 letter preceding. k=6, so there are 1·(9-6)! = 6 permutations preceding ones starting with VISION.

We note that the remaining letters, ERS, are in alphabetical order, so there are no additional permutations preceding VISIONERS.

Rank

Then the number of permutations preceding VISIONERS is ...

80640 +1260 +1800 +120 +48 +6 = 83874

and the rank of VISIONERS is 83875.

Remainder

The remainder when this is divided by 100 is 75.

__

Additional comment

The usual counting method goes into more detail than the one described here. For problems of reasonable size, it is often easier to count the permutations generated ahead of the one of interest using a "next permutation" function.

In the attachment, we generated them all, and searched for the one of interest.

If all possible rearrangements of the word REVISIONS are sorted alphabetically, the-example-1
User Dhk
by
2.9k points