Competition problem — Combinatorics

Library / /31 of 86

Combinatorics Difficulty 6.3 National Olympiad Prove it United States

Problem:
Let $x_{1}, x_{2}, \ldots, x_{k}$ be a sequence of integers. A rearrangement of this sequence (the numbers in the sequence listed in some other order) is called a scramble if no number in the new sequence is equal to the number originally in its location. For example, if the original sequence is $1,3,3,5$ then $3,5,1,3$ is a scramble, but $3,3,1,5$ is not.
A rearrangement is called a two-two if exactly two of the numbers in the new sequence are each exactly two more than the numbers that originally occupied those locations. For example, $3, 5, 1, 3$ is a two-two of the sequence $1,3,3,5$ (the first two values $3$ and $5$ of the new sequence are exactly two more than their original values $1$ and $3$ ).
Let $n \geq 2$ . Prove that the number of scrambles of
$1,1,2,3, \ldots, n-1, n$
is equal to the number of two-twos of
$1,2,3, \ldots, n, n+1 .$
(Notice that both sequences have $n+1$ numbers, but the first one contains two $1$ s.)

Solution

Solution:
For the scrambles, we need to choose two locations from the $n-1$ numbers $2,3, \ldots, n$ to be occupied by the two $1$ s. Once this has been done, we are left with $n-1$ numbers, exactly two of which (the numbers whose locations were occupied by the $1$ s) can be placed freely while all the rest have exactly one location they cannot occupy.

For the two-twos, we need to choose two locations from the $n-1$ numbers $1,2, \ldots, n-1$ to be occupied by a number two greater than before; the list ends with $n-1$ since the $n$ and $n+1$ spots don't have a number that is two greater than them. Then, we have $n-1$ remaining numbers, exactly two of which ( $1$ and $2$ ) can be placed freely while all the rest have exactly one location (the location two less than their value) they cannot occupy.

Notice that although the particular locations are different in the two descriptions above, the mechanics of making the selections are identical: Choose two from a particular subset of $n-1$ of the $n+1$ locations and fill them with particular items. Next fill the remaining slots with the remaining items such that two of the remaining items can go anywhere and each of the others is excluded from exactly one particular location.

Since the rearrangement process is identical in both cases, the number of scrambles and two-twos must be equal.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.