Problem of the Day


Bill has a set of encyclopedias with 26 volumes, one per letter of the alphabet. He has a special shelf built for them with 26 slots in a row, each labeled alphabetically. After moving to a new house, Bill is faced with the task of putting the books back in their proper slots. He decides to do it in such a way that, during the process, there is never a gap between any of the books that are on the shelf. That is, each book he puts back after the first one is adjacent to a book that is already on the shelf. If he can start with any of the 26 books, how many ways can Bill accomplish his task?

A. 26!
B. 2^{25}
C. 24!
D. 26^2
E. 14!12!

Reveal Answer

Answer

[latexpage]

B.  $2^{25}$

See the Solution

Solution

[latexpage]
The easiest way to approach this problem is to work backwards. That is, count the number of ways to take the books OFF the shelf without leaving a gap, rather than the number of ways of putting them back on. In that case you always have to remove one of the books at the end. There will always be two books to choose from until you get to the last book, so you’ll have 2 choices 25 times and 1 choice 1 time, so there are $2^{25}$ ways to take the books off.

This is clearly equivalent to the original problem because every legitimate sequence that he could use to put the books on the shelf could be reversed, so the number of ways to put the books on and number of ways to take the books off would have a one-to-one correspondence.


Comments are closed.