Olympiad Maths Prep

Track / Stage 6 / 240 of 400 #1240 of 2000

Problem 1240

National olympiad, first round
Combinatorics Difficulty 6.4 Find the answer

Consider the set
S={(a,b,c,d,e):0<a<b<c<d<e<100} \mathcal{S}=\{(a, b, c, d, e): 0<a<b<c<d<e<100\}
where a,b,c,d,ea, b, c, d, e are integers. If DD is the average value of the fourth element of such a tuple in the set, taken over all the elements of S\mathcal{S}, find the largest integer less than or equal to DD.

Official solution

1. We need to find the average value of the fourth element d d in the set S={(a,b,c,d,e):0<a<b<c<d<e<100} \mathcal{S} = \{(a, b, c, d, e) : 0 < a < b < c < d < e < 100\} , where a,b,c,d,e a, b, c, d, e are integers.
2. First, we determine the total number of such tuples. This is given by the binomial coefficient (995) \binom{99}{5} , since we are choosing 5 distinct integers from the set {1,2,,99}\{1, 2, \ldots, 99\}.
3. Next, we need to calculate the sum of all possible values of d d over all tuples in S \mathcal{S} . We will use the fact that d d can take any value from 4 to 98, and for each value of d d , we need to count how many tuples have d d as the fourth element.
4. For a fixed d d , the number of ways to choose a,b,c a, b, c from {1,2,,d1}\{1, 2, \ldots, d-1\} is (d13) \binom{d-1}{3} , and the number of ways to choose e e from {d+1,d+2,,99}\{d+1, d+2, \ldots, 99\} is 99d 99 - d .
5. Therefore, the total number of tuples with d d as the fourth element is (d13)(99d) \binom{d-1}{3} \cdot (99 - d) .
6. The sum of all values of d d weighted by the number of tuples is:
d=498d(d13)(99d) \sum_{d=4}^{98} d \cdot \binom{d-1}{3} \cdot (99 - d)
7. To find the average value D D , we divide this sum by the total number of tuples (995) \binom{99}{5} :
D=d=498d(d13)(99d)(995) D = \frac{\sum_{d=4}^{98} d \cdot \binom{d-1}{3} \cdot (99 - d)}{\binom{99}{5}}
8. We simplify the numerator using the identity for binomial coefficients:
d=498d(d13)(99d)=4i=195i(99i4) \sum_{d=4}^{98} d \cdot \binom{d-1}{3} \cdot (99 - d) = 4 \sum_{i=1}^{95} i \cdot \binom{99-i}{4}
9. Using the hockey-stick identity for binomial coefficients, we have:
i=195i(99i4)=(1006) \sum_{i=1}^{95} i \cdot \binom{99-i}{4} = \binom{100}{6}
10. Therefore, the numerator becomes:
4(1006) 4 \cdot \binom{100}{6}
11. The denominator is (995) \binom{99}{5} , so:
D=4(1006)(995) D = \frac{4 \cdot \binom{100}{6}}{\binom{99}{5}}
12. Using the property of binomial coefficients:
(1006)=100!6!94!and(995)=99!5!94! \binom{100}{6} = \frac{100!}{6! \cdot 94!} \quad \text{and} \quad \binom{99}{5} = \frac{99!}{5! \cdot 94!}
13. Simplifying the ratio:
(1006)(995)=1009965=1009930=990030=330 \frac{\binom{100}{6}}{\binom{99}{5}} = \frac{100 \cdot 99}{6 \cdot 5} = \frac{100 \cdot 99}{30} = \frac{9900}{30} = 330
14. Thus:
D=43301=1320 D = \frac{4 \cdot 330}{1} = 1320
15. Finally, the largest integer less than or equal to D D is:
66 \boxed{66}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.