Problem #WSP-100020

Problem

There are $n$ balls labelled 1 to $n$. If there are $m$ boxes labelled 1 to $m$ containing the $n$ balls, a legal position is one in which the box containing the ball $i$ has number at most the number on the box containing the ball $i+1$, for every $i$.

There are two types of legal moves: 1. Add a new empty box labelled $m+1$ and pick a box from box 1 to $m+1$, say the box $j$. Move the balls in each box with (box) number at least $j$ up by one box. 2. Pick a box $j$, shift the balls in the boxes with (box) number strictly greater than $j$ down by one box. Then remove the now empty box $m$.

Prove it is possible to go from an initial position with $n$ boxes with the ball $i$ in the box $i$ to any legal position with $m$ boxes within $n+m$ legal moves.