Problem:
In how many ways can the sequence be rearranged so that no three consecutive terms are increasing and no three consecutive terms are decreasing?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Let be the set of sequences in which the first three terms are increasing; let be the set of sequences in which the second, third, and fourth terms are increasing; and let be the set of sequences in which the last three terms are increasing. Then . Also, . Finally,
. By the Inclusion-Exclusion Principle, the number of sequences that have at least consecutive increasing terms is .
By symmetry, there are sequences with at least three consecutive decreasing terms. For a sequence to have both three consecutive increasing and three consecutive decreasing terms (and thus be counted in both sets of ), one of two possibilities occurs.
The first three terms must increase and the last three terms must decrease, with the largest number, , as the third term. There are possible choices for the first two numbers, which determines the sequence in its entirety, so there are such sequences.
The first three terms must decrease and the last three terms must increase, with the smallest number, , as the third term. By analogous reasoning to the previous case, there are such sequences.
Therefore the number of sequences that have either three consecutive increasing terms or three consecutive decreasing terms is . There are sequences in all, so there are sequences that have neither three increasing consecutive terms nor three consecutive decreasing terms.
Consider the various orders in which , and can appear:
Each of the other orders for , and is a reversal of one of the above, so the total number of ways is .
To satisfy the conditions of the problem, the sequence must satisfy either or . If in an ordering of the first sort, each number, say , is replaced by , then all inequalities are reversed, which produces an ordering of the second type, and vice versa, so the two types of ordering occur the same number of times.
Consider the first type of ordering. There are two local maxima and three local minima. The numbers and cannot be local maxima, so the local maxima are two of , and . Moreover, the number must be one of the local maxima, because cannot be a local minimum. Thus the two maxima are either and , or and . By considering left-right symmetry, it may be assumed that the smaller one is to the left, and the larger one to the right; this gives a factor in the final count. So the sequence can be or . In the first case there is only one possible location for , namely last, and the first and third positions are the numbers and in either order, which gives possibilities. In the second case, the asterisks are the numbers and in any order, which gives possibilities. In all there are such sequences.
The problems on this page are the property of the MAA's American Mathematics Competitions