CombinatoricsDifficulty 5.5AIME, harderFind the answer
35. [20] For each i∈{1,…,10},ai is chosen independently and uniformly at random from [0,i2]. Let P be the probability that a1<a2<⋯<a10. Estimate P. An estimate of E will earn ⌊20min(PE,EP)⌋ points.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Answer: P≈0.003679 Solution: The probability that a2>a1 is 7/8. The probability that a3>a2 is 7/9. The probability that a4>a3 is 23/32. The probability that a5>a4 is 17/25. The probability that a6>a5 is 47/72. The probability that a7>a6 is 31/49. The probability that a8>a7 is 79/128. The probability that a9>a8 is 49/81. The probability that a10>a9 is 119/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<⋯<ak, the value of ak is on average large for its interval. This makes ak<ak+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/10 of the fully independent case. P was approximated with 109 simulations (the answer is given with a standard deviation of about 2×10−6).
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.