Library / Ukrainian Mathematical Olympiad /46 of 49

Ukrainian Mathematical Olympiad

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Ukraine

Let $n \geq 1$ be integer. Sequence $a_1, a_2, \dots, a_{2n}$ is called lucky if

1) $a_1, \dots, a_n$ is a permutation of $\{1, 2, \dots, n\}$ ;

2) $a_k = a_{n+k}$ for all $k = 1, 2, \dots, n$ ;

3) there exist indices $1 \le i_1 < i_2 < \dots < i_n \le 2n$ such that $a_{i_k} = k$ for all $k = 1, 2, \dots, n$ .

For each $n \geq 1$ find the number of lucky sequences.

Solution

Через $m$ , $0 \le m \le n$ , позначимо кількість чисел множини $\{1, 2, \dots, n\}$ , які знаходяться серед індексів $i_1 < i_2 < \dots < i_n$ . Неважко довести, що такими $m$ індексами визначаються $n - m$ чисел із множини $\{n+1, n+2, \dots, 2n\}$ , які увійдуть до даного набору індексів $i_1 < i_2 < \dots < i_n$ . Цим повністю описуються всілякі вдалі послідовності $a_1, a_2, \dots, a_{2n}$ . Для $m = 0$ маємо вдалу послідовність $1, 2, \dots, n$ , $1, 2, \dots, n$ . Але ж ця сама вдала послідовність утворюється ще в $n$ випадках, коли для набору індексів $i_1 < i_2 < \dots < i_n$ маємо, що
$\{i_1, i_2, \dots, i_n\} \cap \{1, 2, \dots, n\} = \{1, 2, \dots, m\}, \quad 1 \le m \le n.$
Усіляких підмножин $n$ -елементної множини $\{1, 2, \dots, n\}$ , відмінних від підмножин $\{1, 2, ..., m\}$ , $1 \le m \le n$ , існує $2^n-n$ . Усім таким підмножинам відповідають різні вдалі послідовності (порожня підмножина відповідає випадку $m=0$ і також враховується серед $2^n-n$ підмножин).
Відповідь: $2^n-n$ .

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

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