The Mayor's dilemma

A simple sorting problem is considered that has been informally discussed in The Netherlands for some time (see Steutel (2008)). The context is as follows. The Mayor of Amsterdam wishes to meet the tallest inhabitant of his city, and to this end he asks the inhabitants to form a long line, where the people are numbered from one to a million, say. Some of the people will have to be paid for their trouble, so the Mayor will have to carry some money. He would hate to have too little, but he would rather not have much more than is necessary. The question then is: how much money should the Mayor carry? This leads to rather surprising answers, and to some not entirely trivial mathematics.