MathDB

(480) 4

Part of 1995 Tournament Of Towns

Problems(1)

TOT 480 1995 Autumn S A4 n spectators, n tickets

Source:

7/9/2024
Along a track for cross-country skiing, 10001000 seats are placed in a row and numbered in order from 11 to 10001000. By mistake, nn tickets were sold, 100<n<1000100 < n < 1000, each with one of the numbers 1,2,...,1001,2,..., 100 printed on it. Also for each number 1,2,...,1001,2,..., 100 there exists at least one ticket with this number printed on it. Of course, there are tickets that have the same seat numbers. These nn spectators arrive one at a time.
Each goes to the seat shown on his ticket and occupies it if it is still empty. If not, he just says “Oh” and moves to the seat with the next number. This is repeated until he finds an empty seat and occupies it, saying “Oh” once for each occupied seat passed over but not at any other time. Prove that all the spectators will be seated and that the total number of the exclamations “Oh” that have been made before all the spectators are seated does not depend on the order in which the n spectators arrive, although it does depend on the distribution of numbers on the tickets.
(A Shen)
combinatorics