IMO 1988 LL USA81

Origin: USA

Problem

There are n \geq3 job openings at a factory, ranked 1 to n in order of increasing pay. There are n job applicants, ranked 1 to n in order of increasing ability. Applicant i is qualified for job j if and only if i \geqj. The applicants arrive one at a time in random order. Each in turn is hired to the highest-ranking job for which he or she is qualified and that is lower in rank than any job already filled. (Under these rules, job 1 is always filled and hiring terminates thereafter.) Show that applicants n and n−1 have the same probability of being hired.