Maths Olympiad Prep

Library / /528 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

Let x0=x101=0x_{0}=x_{101}=0. The numbers x1,x2,,x100x_{1}, x_{2}, \ldots, x_{100} are chosen at random from the interval [0,1][0,1] uniformly and independently. Compute the probability that 2xixi1+xi+12 x_{i} \geq x_{i-1}+x_{i+1} for all i=1,2,i=1,2, \ldots, 100.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We solve for general nn where n=100n=100 in the problem. Notice that the points (i,Ai)\left(i, A_{i}\right) must form a convex hull, so there is some unique maximal element AiA_{i}. Consider the i1i-1 points A1,,Ai1A_{1}, \ldots, A_{i-1} left of ii, and the ii slopes formed between these points of segments A0A1,,Ai1Ai\overline{A_{0} A_{1}}, \ldots, \overline{A_{i-1} A_{i}}. Notice that we must choose the i1i-1 points to be decreasing. Ignoring cases where they have some shared yy-coordinates since this happens with probability 0, we have a 1(i1)!\frac{1}{(i-1)!} chance of picking them in ascending order. Now, we order the differences {A1A0,A2A1,,AiAi1}\left\{A_{1}-A_{0}, A_{2}-A_{1}, \ldots, A_{i}-A_{i-1}\right\} in descending order, obtaining some new list {d1,d2,,di}\left\{d_{1}, d_{2}, \ldots, d_{i}\right\} and redefining Ak=j=1kdjA_{k}=\sum_{j=1}^{k} d_{j}. Notice that this procedure almost surely maps (i1)!i(i-1)!i! possible sequences of points A1,A2,,Ai1A_{1}, A_{2}, \ldots, A_{i-1} to a valid convex hull, so the chance that the points left of AiA_{i} are valid is 1(i1)!i!\frac{1}{(i-1)!i!}. Similarly, the chance that the points on the right work is given by 1(n+1i)!(ni)!\frac{1}{(n+1-i)!(n-i)!}. So, for a maximum value at AiA_{i} the chance that we get a valid convex hull is 1(i1)!i!(n+1i)!(ni)!\frac{1}{(i-1)!i!(n+1-i)!(n-i)!}. To finish, note that each point is equally likely to be the peak. Our answer is 1ni=1n1(i1)!!!(n+1i)!(ni)!=1nn!2i=1nn!2(i1)!i!(n+1i)!(ni)!=1nn!2i=1n(ni1)(nni)==1nn!2(2nn1)\begin{aligned} & \frac{1}{n} \sum_{i=1}^{n} \frac{1}{(i-1)!!!(n+1-i)!(n-i)!} \\ & =\frac{1}{n \cdot n!^{2}} \sum_{i=1}^{n} \frac{n!^{2}}{(i-1)!i!(n+1-i)!(n-i)!} \\ & =\frac{1}{n \cdot n!^{2}} \sum_{i=1}^{n}\binom{n}{i-1}\binom{n}{n-i}= \\ & =\frac{1}{n \cdot n!^{2}}\binom{2n}{n-1} \end{aligned} Plugging in n=100n=100 gives the desired answer.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.