Solution: 2017 Fall Final - 2

Author: Michiel Smid

Question

Let $n \geq 2$ be an even integer. A permutation $a_1,a_2,\dots,a_n$ of the set $\{1,2,\dots,n\}$ is called awesome if $a_2 = 2 \cdot a_1$.
For example, if $n = 6$, then the permutation $3,6,4,1,5,2$ is awesome, whereas the permutation $3,5,4,1,6,2$ is not awesome.
How many awesome permutations of the set $\{1,2,\dots,n\}$ are there?

(a)

$n \cdot (n-1)!$

(b)

${\frac{n}{2}} \cdot (n-2)!$

(c)

${\frac{n}{2}} \cdot (n-1)!$

(d)

$n \cdot (n-2)!$

Solution

Let’s break it down

There is an integer $a_1$ and then its double $a_2$

The largest value is $n$ and its half is $n/2$

The second largest value is $n-2$ and its half is $\frac{n-2}{2}$

We subtract 2 since odd numbers have no halves

This pattern tells us that starting from n, every other value decrementing results in a double and integer

When we rephrase this statement, we’re saying half of the values from n to 2 are doubles of some values in the set

We can take the integer and its double and place it at the front

This means there are possibly $ \frac{n}{2} $ pairs

The remaining $n-2$ integers can be arranged in $ (n-2)! $ ways

In total, there are $ \frac{n}{2} \cdot (n-2)! $ awesome permutations of the set ${1, 2, …, n}$.