Heights in Descending order
Source: Tournament of Towns Fall 2015 Senior A-level
February 23, 2017
combinatorics
Problem Statement
children no two of the same height stand in a line. The following two-step procedure is applied: first, the line is split into the least possible number of groups so that in each group all children are arranged from the left to the right in ascending order of their heights (a group may consist of a single child). Second, the order of children in each group is reversed, so now in each group the children stand in descending order of their heights. Prove that in result of applying this procedure times the children in the line would stand from the left to the right in descending order of their heights.
(12 points)