Maths Olympiad Prep

Library / /202 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

Let nn be a positive integer. Let (a,b,c)(a, b, c) be a random ordered triple of nonnegative integers such that a+b+c=na + b + c = n, chosen uniformly at random from among all such triples. Let MnM_n be the expected value (average value) of the largest of aa, bb, and cc. As nn approaches infinity, what value does Mnn\frac{M_n}{n} approach?

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

Solution

1. Define the problem and variables:
We are given a positive integer n n and need to find the expected value Mn M_n of the largest of three nonnegative integers a,b, a, b, and c c such that a+b+c=n a + b + c = n . We are interested in the limit of Mnn \frac{M_n}{n} as n n approaches infinity.

2. Count the number of ordered triples:
The number of ordered triples (a,b,c)(a, b, c) such that a+b+c=n a + b + c = n is given by the stars and bars theorem:
(n+22) \binom{n+2}{2}

3. **Define Wk(n) W_k(n) :**
Let Wk(n) W_k(n) denote the number of ordered triples (a,b,c)(a, b, c) such that a+b+c=n a + b + c = n and max(a,b,c)=k\max(a, b, c) = k.

4. **Symmetry and counting Wk(n) W_k(n) :**
By symmetry and the properties of the triangular array, we can determine Wk(n) W_k(n) for different ranges of k k :
- For kn3 k \geq \lceil \frac{n}{3} \rceil , the values of Wk(n) W_k(n) depend on the residue of nmod3 n \mod 3 :
Wn3+k(n)={3(3k+2)if n1mod33(3k+1)if n2mod39kif 3n W_{\lceil \frac{n}{3} \rceil + k}(n) = \begin{cases} 3(3k + 2) & \text{if } n \equiv 1 \mod 3 \\ 3(3k + 1) & \text{if } n \equiv 2 \mod 3 \\ 9k & \text{if } 3 \mid n \end{cases}

5. Expected value calculation:
To compute Mn M_n , we need to average the values of kWk(n) k \cdot W_k(n) over all k k from n3 \lceil \frac{n}{3} \rceil to n n :
Mn=i=n3n(iWi(n))(n+22) M_n = \frac{\sum_{i=\lceil \frac{n}{3} \rceil}^{n} (i \cdot W_i(n))}{\binom{n+2}{2}}

6. Simplify the sum:
Using the properties of binomial coefficients and the Hockey Stick Identity, we can simplify the sum:
i=1+n2n(iWi(n))=3n2(n2+22)+3(n2+33) \sum_{i=1 + \lfloor \frac{n}{2} \rfloor}^{n} (i \cdot W_i(n)) = 3 \lfloor \frac{n}{2} \rfloor \binom{\lfloor \frac{n}{2} \rfloor + 2}{2} + 3 \binom{\lfloor \frac{n}{2} \rfloor + 3}{3}

7. Asymptotic behavior:
As n n approaches infinity, the floors and ceilings become negligible. We focus on the leading terms of the numerator and denominator:
i=n3n(iWi(n))n(n+22) \frac{\sum_{i=\lceil \frac{n}{3} \rceil}^{n} (i \cdot W_i(n))}{n \binom{n+2}{2}}

8. Leading coefficients:
The leading third-degree coefficients of the numerator and the denominator determine the limit. After simplification, we find:
limnMnn=1118 \lim_{n \to \infty} \frac{M_n}{n} = \frac{11}{18}

The final answer is 1118 \boxed{\frac{11}{18}}

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.