Track / Stage 5 / 72 of 400 #1152 of 2444

Problem 1152

AIME late

Combinatorics Difficulty 5.1 Prove it Harvard-MIT Math Tournament · United States

You are given 16 pieces of paper numbered $16,15, \ldots, 2,1$ in that order. You want to put them in the order $1,2, \ldots, 15,16$ switching only two adjacent pieces of paper at a time. What is the minimum number of switches necessary?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

Piece $16$ has to move to the back $15$ times, piece $15$ has to move to the back $14$ times, $\ldots$ . Piece $2$ has to move to the back $1$ time, piece $1$ has to move to the back $0$ times. Since only one piece can move back in each switch, we must have at least $15+14+\ldots+1=\mathbf{120}$ switches.

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