Competition problem — Combinatorics

Library / /73 of 94

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:

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?

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.

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

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