MathDB

There are

n \geq 3

job openings at a factory, ranked

1

n

in order of increasing pay. There are

n

job applicants, ranked from

1

n

in order of increasing ability. Applicant

i

is qualified for job

j

if and only if

i \geq j.

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 which 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 \minus{} 1 have the same probability of being hired.

Problem Statement