Problem:
Six cards numbered through are to be lined up in a row. Find the number of arrangements of these six cards where one of the cards can be removed leaving the remaining five cards in either ascending or descending order.
Solution:
We begin by counting the number of permutations of the six cards such that removing a single card leaves the remaining five in ascending order.
There is exactly one such permutation where all six cards are already in order: .
Next, consider permutations where two adjacent cards in are swapped. Each of these creates exactly one inversion, and removing the out-of-place card restores ascending order. There are 5 such permutations (one for each adjacent pair swap), such as .
Now, consider permutations obtained by removing a card from and reinserting it in a position at least two places away from its original position. In these cases: cards and can each be placed in 4 positions that are at least two spots from their original positions, and cards , , , and can each be placed in 3 such positions.
Thus, the number of these permutations is .
In total, the number of permutations where removing one card results in an increasing sequence is .
By symmetry, there are also 26 permutations where removing one card leaves the remaining cards in descending order.
Therefore, the total number of such permutations is .
The problems on this page are the property of the MAA's American Mathematics Competitions