Maths Olympiad Prep

Library / /310 of 520

Combinatorics Difficulty 5.4 AIME, harder Prove it

In 2003, the 5th problem of the Chinese Mathematical Olympiad was as follows:
A company needs to hire a secretary, with a total of 10 people applying. The company manager decides to interview them in the order of their application, and the first 3 people will definitely not be hired. Starting from the 4th person, he will be compared with those who have been interviewed before. If his ability exceeds all those who have been interviewed before, he will be hired; otherwise, he will not be hired, and the next person will be interviewed. If none of the first 9 people are hired, then the last person interviewed will be hired.

Assuming the abilities of these 10 people are all different and can be ranked from 1st to 10th in terms of ability. Clearly, which person the company ends up hiring depends on the order in which these 10 people apply. There are 10! such permutations. We denote AkA_{k} as the number of different application orders in which the person with the kk-th ability is hired, and Ak10!\frac{A_{k}}{10!} as the probability of him being hired.

Solution

Prove: Under the policy of the company manager, there is
(1) A1>A2>>A8=A9=A10A_{1}>A_{2}>\cdots>A_{8}=A_{9}=A_{10};
(2) The company has more than a 70%70 \% chance of hiring one of the top three most capable individuals; while there is no more than a 10%10 \% chance of hiring one of the bottom three least capable individuals.

This is a problem related to "probability calculation" with a strong practical background. Upon first reading this question, many people may question its rationality: Why not interview everyone and then select the best one?

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.