Maths Olympiad Prep

Library / /11 of 11

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it China

Nine balls, numbered 11, 22, \ldots, 99, are put randomly at 99 equally spaced points on a circle, each point with a ball. Let SS be the sum of the absolute values of the differences of the numbers of all two neighboring balls. Find the probability of SS to be the minimum value. (Remark: If one arrangement of the balls is congruent to another after a rotation or a reflection, the two arrangements are regarded as the same).

Solution

Next, we calculate the number of arrangements, which make SS the minimum. Along the circle there are two routes from 11 to 99, the major arc and the minor arc. For each of them, let x1,x2,,xkx_1, x_2, \dots, x_k be the numbers of the successive balls on the arc, then
1x1+x1x2++xk9(1x1)+(x1x2)++(xk9)=19=8. \begin{aligned} & |1-x_1| + |x_1-x_2| + \dots + |x_k-9| \\ \ge & |(1-x_1) + (x_1-x_2) + \dots + (x_k-9)| \\ = & |1-9| = 8. \end{aligned}
The equality occurs if and only if 1<x1<x2<<xk<91 < x_1 < x_2 < \dots < x_k < 9, i.e. the numbers of the balls on each route is increasing from 11 to 99.

Therefore, Smin=28=16S_{\min} = 2 \cdot 8 = 16.

From the above analysis, when the numbers of the balls {1,x1,x2,,xk,9}\{1, x_1, x_2, \dots, x_k, 9\} on each arc are fixed, the arrangement which gets the minimum value is uniquely determined. Divide the set of 77 balls {2,3,,8}\{2, 3, \dots, 8\} into two subsets, then the subset which contains less elements has C90+C91+C92+C93=26C_9^0 + C_9^1 + C_9^2 + C_9^3 = 2^6 cases. Each case corresponds to a unique arrangement, which achieves the minimum value of SS.

Thus, the number of the arrangements when SS takes the minimum value is 262^6 and the corresponding probability is p=268!2=1315p = \frac{2^6}{\frac{8!}{2}} = \frac{1}{315}.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.