China Mathematical Olympiad

Proof We denote by $a$ the ability rating of the applicant with the highest ability among the first three interviews. Obviously, $a\le 8$. Now we denote by $A_k(a)$ the set of permutations for which the person with the $k$-th ability rating is employed and we denote the corresponding number of permutations by $|A_k(a)|$.

(1) It is easy to see that, when $a=1$, a definite result is to give up the first nine persons and to employ the last interviewee. Now the chance is equal for every person except the one who has the highest ability rating. It is not difficult to see that $$|A_k(1)|=3\times 8!:=r_1,k=2,3,\dots ,10,$$ where “:=” denotes “written as”.

When $2\le a\le 8$, a person who is placed $k$-th in ability rating will have no chance to be employed for $a\le k\le 10$, and the chance is equal for $1\le k<a$.

In fact, a person with the $a$-th ability rating is among the first three interviews and there are three ways to choose one out of the three interviews. Those people with their ability rating from the $1$-st to $(a-1)$-th are among the later seven interviews, and the first one having the highest ability rating among them is employed. There are $C_7^{a-1}(a-2)!$ ways of such arrangement. The other $10-a$ persons may be arranged arbitrarily on the remainder positions, and we have $(10-a)!$ ways of arrangement. Hence, we have $$|A_k(a)|=\{\begin{array}{ll}3C_7^{a-1}(a-2)!(10-a)!:=r_a,& k=1,\cdots ,a-1;\\ 0,& k=a,\cdots ,10.\end{array}$$

The result above shows: $$A_8=A_9=A_{10}=r_1=3\times 8!>0;\stackrel{◯}{1}$$ $$A_k=r_1+\sum _{a=k+1}^8{r}_a,k=2,\dots ,7;\stackrel{◯}{2}$$ $$\text{and}{A}_1=\sum _{a=2}^8{r}_a.\stackrel{◯}{3}$$ From ① and ②, we obtain $$A_2>A_3>\cdots >A_8=A_9=A_{10}>0;$$ and from ② and ③, we obtain $$A_1-A_2=r_2-r_1=3\times 7\times 8!-3\times 8!>0.$$ Consequently, (1) is proved.

(2) From ①, we know $$\frac{A_8+A_9+A_{10}}{10!}=\frac{3\times r_1}{10!}=\frac{3\times 3\times 8!}{10!}=10\%.$$ So the probability for the company to employ one of the bottom three is equal to $10\%$.

From ② and ③, we can show that $$\begin{array}{rl}{A}_1& =\sum _{a=2}^8{r}_a=\sum _{a=2}^{8}3C_7^{a-1}(a-2)!(10-a)!\\ & =3\times 7!\sum _{a=2}^8\frac{(9-a)(10-a)}{a-1}\end{array}$$ $$\begin{array}{rl}& =3\times 7!\sum _{s=1}^7\frac{(8-s)(9-s)}{s}\\ & =3\times 7!\times \left(56+21+10+5+\frac{12}{5}+1+\frac{2}{7}\right)\\ & =3\times 7!\times 95\frac{24}{35}>3\times 7!\times 95\frac{2}{3}\\ & =287\times 7!;\end{array}$$ $$\begin{array}{rl}{A}_2& =r_1+\sum _{a=3}^8{r}_a\\ & =3\times 8!+3\times 7!\times \left(21+10+5+\frac{12}{5}+1+\frac{2}{7}\right)\\ & =3\times 7!\times 47\frac{24}{35}>3\times 7!\times 47\frac{2}{3}=143\times 7!;\end{array}$$ $$\begin{array}{rl}{A}_3& =r_1+\sum _{a=4}^8{r}_a\\ & =3\times 8!+3\times 7!\times \left(10+5+\frac{12}{5}+1+\frac{2}{7}\right)\\ & =3\times 7!\times 26\frac{24}{35}>3\times 7!\times 26\frac{2}{3}=80\times 7!.\end{array}$$ Therefore, $$\begin{array}{rl}\frac{A_1+A_2+A_3}{10!}& >\frac{287+143+80}{720}\\ & =\frac{510}{720}=\frac{17}{24}>70\%.\end{array}$$ That is, the probability for the company to employ one of the top three, is greater than $70\%$.