MathDB

Along a track for cross-country skiing,

1000

seats are placed in a row and numbered in order from

1

1000

. By mistake,

n

tickets were sold,

100 < n < 1000

, each with one of the numbers

1,2,..., 100

printed on it. Also for each number

1,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

n

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)

Problem Statement