2002 IMO Shortlist Problems/C3

Problem

Let $\displaystyle n$ be a positive integer. A sequence of $\displaystyle n$ positive integers (not necessarily distinct) is called full if it satisfies the following conditions: for each positive integers $\displaystyle k \ge 2$ , if the number $\displaystyle k$ appears in the sequence then so does the number $\displaystyle k-1$ , and moreover the first occurrance of $\displaystyle k-1$ comes before the last occurrance of $\displaystyle k$ . For each $\displaystyle n$ , how many full sequences are there?

Solution

We claim that there is a bijection between the permutations of the numbers $\displaystyle 1, \ldots , n$ and the full sequences of length $\displaystyle n$ .

To obtain a full sequence $\displaystyle a_1, \ldots a_n$ from a permutation $\displaystyle \sigma$ of the first $\displaystyle n$ positive integers, begin by letting $\displaystyle a_{\sigma(1)}$ be 1. Then, if $\displaystyle a_{\sigma(j)}$ is $\displaystyle i$ and $\displaystyle \sigma(j+1) < \sigma(j)$ , let $\displaystyle a_{\sigma(j+1)}$ be $\displaystyle i$ , but if $\displaystyle \sigma(j+1) > \sigma(j)$ , let $\displaystyle a_{\sigma(j+1)}$ be $\displaystyle i+1$ . This ensures that if $\displaystyle k > 2$ appears in the sequence, then the first appearance of $\displaystyle k-1$ occurs before the last appearance of $\displaystyle k$ , as desired.

To obtain a permutation from a full sequence, list the labels of the terms of the sequence that are 1 in decreasing order, followed by the labels of the terms of the sequence that are 2 in decreasing order, etc. This produces a permutation which will map back to our full sequence as described above. Thus the bijection is established; therefore there are $\displaystyle n!$ full sequences of length $\displaystyle n$ , Q.E.D.

Note: There is also a recursive solution, but it is very similar to the bijective solution given here.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Page

Toolbox

Search

2002 IMO Shortlist Problems/C3

Problem

Solution

Resources