Maths Olympiad Prep

Library / /262 of 520

Combinatorics Difficulty 5.5 AIME, harder Find the answer

35. [20] For each i{1,,10},aii \in\{1, \ldots, 10\}, a_{i} is chosen independently and uniformly at random from [0,i2]\left[0, i^{2}\right]. Let PP be the probability that a1<a2<<a10a_{1}<a_{2}<\cdots<a_{10}. Estimate PP.
An estimate of EE will earn 20min(EP,PE)\left\lfloor 20 \min \left(\frac{E}{P}, \frac{P}{E}\right)\right\rfloor points.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Answer: P0.003679\quad P \approx 0.003679
Solution: The probability that a2>a1a_{2}>a_{1} is 7/87 / 8. The probability that a3>a2a_{3}>a_{2} is 7/97 / 9. The probability that a4>a3a_{4}>a_{3} is 23/3223 / 32. The probability that a5>a4a_{5}>a_{4} is 17/2517 / 25. The probability that a6>a5a_{6}>a_{5} is 47/7247 / 72. The probability that a7>a6a_{7}>a_{6} is 31/4931 / 49. The probability that a8>a7a_{8}>a_{7} is 79/12879 / 128. The probability that a9>a8a_{9}>a_{8} is 49/8149 / 81. The probability that a10>a9a_{10}>a_{9} is 119/200119 / 200.
Assuming all of these events are independent, you can multiply the probabilities together to get a probability of around 0.05 . However, the true answer should be less because, conditioned on the realization of a1<a2<<aka_{1}<a_{2}<\cdots<a_{k}, the value of aka_{k} is on average large for its interval. This makes ak<ak+1a_{k}<a_{k+1} less likely. Although this effect is small, when compounded over 9 inequalities we can estimate that it causes the answer to be about 1/101 / 10 of the fully independent case.
PP was approximated with 10910^{9} simulations (the answer is given with a standard deviation of about 2×106)\left.2 \times 10^{-6}\right).

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.