Test 1

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Hong Kong

$k$ cards numbered $1$ to $k$ are arranged at random in a row. In a move, we may change any block of consecutive cards whose numbers are in ascending or descending order and switch the block around. For example, in the case $k = 4$ , $4132$ may be changed to $1432$ and $3214$ may be changed to $1234$ . Suppose that in at most $n_k$ moves, we can arrange the $k$ cards so that their numbers are in ascending or descending order.

a. Prove that $n_4 = 3$ .

b. Determine or estimate $n_5$ .

Solution

a. Consider the same problem but we require the numbers at the end to be in ascending order (i.e. descending order is not allowed). Let $m_k$ be the least number of moves needed to guarantee that this can be done when there are $k$ numbers. By symmetry, this number is the same if we require the numbers at the end to be in descending order. Clearly, we have $n_k \le m_k$ .

We claim that $m_{k+1} \le m_k + 1$ for $k \le 4$ . Given a permutation of $1, 2, \dots, k+1$ , one of the numbers $1$ and $k+1$ must be located at the first two or the last two positions since there are at most $5$ numbers in total. We can use at most $1$ move to put this number to the first or the last position. For the remaining numbers, we need at most $m_k$ moves to sort them in the correct order, so that all numbers are in monotonic order. This proves the inequality.

It follows that $n_4 \le m_4 \le m_3 + 1 \le m_2 + 2 = 3$ (obviously, $m_2 = 1$ ). Next, we show that $2413$ cannot be changed to $1234$ or $4321$ in $2$ steps. This can be verified by checking all possibilities as follows. (Note that swapping the same block twice is useless.)

$\begin{array}{ccc} \underline{2413} \longrightarrow 4213 \longrightarrow 4123, 4231, 1243 \\ 2413 \longrightarrow 2143 \longrightarrow 1243, 2134 \\ \underline{2413} \longrightarrow 2431 \longrightarrow 4231, 2341, 2134 \end{array}$

Therefore, we must have $n_4 = 3$ .

b. We have $n_5 = 4$ .

Again, we list out all possibilities.

0 moves	1 move	2 moves	3 moves
$\underline{31}524$	$1\underline{3}524$	$15324$	$51324$ , $15234$ , $15342$ , $12354$
	$1\underline{3}524$	$13254$	$31254$ , $12354$ , $13245$
	$\underline{13}524$	$13542$	$31542$ , $15342$ , $13452$ , $53142$ , $13245$
	$\underline{13}524$	$53124$	$35124$ , $51324$ , $53214$ , $53142$ , $53421$
$\underline{31}524$	$\underline{3}5124$	$53124$	$51324$ , $53214$ , $53142$ , $13524$ , $53421$
	$3\underline{1}24$	$35214$	$53214$ , $32514$ , $35241$ , $31254$
	$3\underline{1}24$	$35142$	$53142$ , $31542$ , $35412$
	$3\underline{1}24$	$35421$	$53421$ , $34521$ , $35241$ , $35412$ , $32451$ , $31245$
$\underline{31}524$	$\underline{3}1254$	$13254$	$12354$ , $13524$ , $13245$
	$\underline{3}1254$	$32154$	$23154$ , $32514$ , $32145$ , $12354$
	$3\underline{1}254$	$31245$	$13245$ , $32145$ , $31425$ , $34215$ , $31542$ , $35421$
	$\underline{3}1254$	$35214$	$53214$ , $32514$ , $35124$ , $35241$
$\underline{31}524$	$\underline{3}1542$	$13542$	$15342$ , $13452$ , $13524$ , $53142$ , $13245$
	$3\underline{1}542$	$35142$	$53142$ , $35412$ , $35124$
	$3\underline{1}542$	$31452$	$13452$ , $34152$ , $31425$ , $35412$
	$\underline{3}1542$	$31245$	$13245$ , $32145$ , $31425$ , $31254$ , $34215$ , $35421$

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.