IMO Shortlist 2014 problem A3
For a sequence of real numbers, we define its price as
Given real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price . Greedy George, on the other hand, chooses such that is as small as possible; among the remaining numbers, he chooses such that is as small as possible, and so on. Thus, in the step he chooses among the remaining numbers so as to minimise the value of . In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price .
Find the least possible constant such that for every positive integer , for every collection of real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality .