Maths Olympiad Prep

Library / HMMT /35 of 79

HMMT, 2014

Combinatorics Difficulty 5.2 AIME, harder Find the answer United States

Problem:

An up-right path from (a,b)∈R2(a, b) \in \mathbb{R}^{2} to (c,d)∈R2(c, d) \in \mathbb{R}^{2} is a finite sequence (x1,y1),…,(xk,yk)\left(x_{1}, y_{1}\right), \ldots,\left(x_{k}, y_{k}\right) of points in R2\mathbb{R}^{2} such that (a,b)=(x1,y1),(c,d)=(xk,yk)(a, b)=\left(x_{1}, y_{1}\right),(c, d)=\left(x_{k}, y_{k}\right), and for each 1≤i<k1 \leq i<k we have that either (xi+1,yi+1)=(xi+1,yi)\left(x_{i+1}, y_{i+1}\right)=\left(x_{i}+1, y_{i}\right) or (xi+1,yi+1)=(xi,yi+1)\left(x_{i+1}, y_{i+1}\right)=\left(x_{i}, y_{i}+1\right).
Let SS be the set of all up-right paths from (−400,−400)(-400,-400) to (400,400)(400,400). What fraction of the paths in SS do not contain any point (x,y)(x, y) such that ∣x∣,∣y∣≤10|x|,|y| \leq 10 ? Express your answer as a decimal number between 0 and 1.
If CC is the actual answer to this question and AA is your answer, then your score on this problem is ⌈max⁡{25(1−10∣C−A∣),0}⌉\lceil\max \{25(1-10|C-A|), 0\}\rceil.

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

Solution

Solution:

Answer: 0.2937156494680644…0.2937156494680644 \ldots Note that any up-right path must pass through exactly one point of the form (n,−n)(n,-n) (i.e. a point on the upper-left to lower-right diagonal), and the number of such paths is (800400−n)2\binom{800}{400-n}^{2} because there are (800400−n)\binom{800}{400-n} up-right paths from (−400,−400)(-400,-400) to (n,−n)(n,-n) and another (800400−n)\binom{800}{400-n} from (n,−n)(n,-n) to (400,400)(400,400). An up-right path contains a point (x,y)(x, y) with ∣x∣,∣y∣≤10|x|,|y| \leq 10 if and only if −10≤n≤10-10 \leq n \leq 10, so the probability that this happens is

∑n=−1010(800400−n)2∑n=−400400(800400−n)2=∑n=−1010(800400−n)2(1600800) \frac{\sum_{n=-10}^{10}\binom{800}{400-n}^{2}}{\sum_{n=-400}^{400}\binom{800}{400-n}^{2}}=\frac{\sum_{n=-10}^{10}\binom{800}{400-n}^{2}}{\binom{1600}{800}}

To estimate this, recall that if we normalize (800n)\binom{800}{n} to be a probability density function, then it will be approximately normal with mean 400 and variance 800⋅14=200800 \cdot \frac{1}{4}=200. If this is squared, then it is proportional to a normal distribution with half the variance and the same mean, because the probability density function of a normal distribution is proportional to e−(x−μ)22σ2e^{-\frac{(x-\mu)^{2}}{2 \sigma^{2}}}, where μ\mu is the mean and σ2\sigma^{2} is the variance.
Therefore, the (800n)2\binom{800}{n}^{2} probability density function is roughly proportional to a normal distribution with mean 400 and variance 100, or standard deviation 10. So ∑n=−1010(800400−n)2\sum_{n=-10}^{10}\binom{800}{400-n}^{2} represents roughly one standard deviation. Recall that approximately 68 percent of a normal distribution lies within one standard deviation of the mean (look up the 68-95-99.7 rule to read more), so a good guess would be around .32. This guess can be improved by noting that we're actually summing 21 values instead of 20, so you'd have approximately .68⋅2120≈.71.68 \cdot \frac{21}{20} \approx .71 of the normal distribution, giving an answer of .29.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.