RU-ALLRUSSIAN 1984 Problem 15

Each weight in a set of n has integral weight and the total weight of the set is 2n. A balance is initially empty. We then place the weights onto a pan of the balance one at a time. Each time we place the heaviest weight not yet placed. If the pans balance, then we place the weight

onto the left pan. Otherwise, we place the weight onto the lighter pan. Show that when all the weights have been placed, the scales will balance. [For example, if the weights are 2, 2, 1, 1. Then we must place 2 in the left pan, followed by 2 in the right pan, followed by 1 in the left pan, followed by 1 in the right pan.]