Maths Olympiad Prep

Track / Stage 5 / 106 of 400 #706 of 1964

Problem 706

AIME late
Combinatorics Difficulty 5.3 Find the answer

8. Make a full permutation of the elements in the set {1,2,,8}\{1,2, \cdots, 8\}, such that except for the number at the far left, for each number nn on the right, there is always a number to the left of nn whose absolute difference with nn is 1. The number of permutations that satisfy this condition is \qquad

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

8. 128 .

Suppose for a certain permutation that satisfies the conditions, the first element on the left is k(1k8)k(1 \leqslant k \leqslant 8). Then, among the remaining seven numbers, the 8k8-k numbers greater than kk, k+1,k+2,,8k+1, k+2, \cdots, 8, must be arranged in ascending order; and the k1k-1 numbers less than kk, 1,2,,k11,2, \cdots, k-1, must be arranged in descending order (not necessarily adjacent).
In fact, for any number k+nk+n greater than kk, assume k+n<8k+n<8.
If k+n+1k+n+1 is placed to the left of k+nk+n, then the other number k+n+2k+n+2 that differs by 1 from k+n+1k+n+1 must be placed to the left of k+n+1k+n+1; similarly, the other number k+n+3k+n+3 that differs by 1 from k+n+2k+n+2 must be placed to the left of k+n+2k+n+2; \cdots. Then the second number in the permutation cannot differ by 1 from kk, which is a contradiction.
Therefore, k+n+1k+n+1 must be placed to the right of k+nk+n.
Similarly, the k1k-1 numbers less than kk, 1,2,,k11,2, \cdots, k-1, must be arranged in descending order.

Since when the first element on the left kk is determined, there are still seven positions on the right, and any 8k8-k of these positions can be chosen to fill in the numbers greater than kk (the remaining k1k-1 positions will fill in the numbers less than kk), the number of ways to choose is C78k\mathrm{C}_{7}^{8-k}; and once the positions are chosen, the method of filling in the numbers is uniquely determined.
Therefore, the total number of permutations is
k=18C78k=k=07C7j=27. \sum_{k=1}^{8} \mathrm{C}_{7}^{8-k}=\sum_{k=0}^{7} \mathrm{C}_{7}^{j}=2^{7} .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.