Maths Olympiad Prep

Library / /44 of 75

Combinatorics Difficulty 5.3 AIME, harder Prove it Italy

How many arithmetic progressions consisting of four integers a,b,c,da, b, c, d with 1a<b<c<d1001 \leq a < b < c < d \leq 100 are there?

Solution

The answer is 1617. If a,b,c,da, b, c, d is an arithmetic progression of four terms, then the common difference rr is also an integer 1\geq 1 and we have d=a+3rd = a + 3r. On the other hand, the first term and the last term of an arithmetic progression of four terms completely determine the other terms as well. The number of arithmetic progressions sought is therefore in bijective correspondence with the pairs of numbers of the form {a,a+3r}\{a, a+3r\} contained in the set {1,,100}\{1, \ldots, 100\}. Observing that aa and a+3ra+3r give the same remainder upon division by 3, we can distinguish 3 cases, according to whether this remainder is 1, 2, or 0:

- {a,a+3r}X1={1,4,7,,100}\{a, a+3r\} \subset X_{1} = \{1, 4, 7, \ldots, 100\}. The set X1X_{1} consists of 34 elements, so there are (342)=561\binom{34}{2} = 561 pairs of this type.
- {a,a+3r}X2={2,5,8,,98}\{a, a+3r\} \subset X_{2} = \{2, 5, 8, \ldots, 98\}. The set X2X_{2} consists of 33 elements, so there are (332)=528\binom{33}{2} = 528 pairs of this type.
- {a,a+3r}X3={3,6,9,,99}\{a, a+3r\} \subset X_{3} = \{3, 6, 9, \ldots, 99\}. The set X3X_{3} consists of 33 elements, so there are (332)=528\binom{33}{2} = 528 pairs of this type.

In total, 561+528+528=1617561 + 528 + 528 = 1617 arithmetic progressions.

Second solution.
Denoting by r1r \geq 1 the common difference of the arithmetic progression, we have 1a1 \leq a and a+3r100a + 3r \leq 100, so 3r1001=993r \leq 100 - 1 = 99 and r33r \leq 33. If a,a+r,a+2r,a+3ra, a + r, a + 2r, a + 3r is an arithmetic progression with common difference rr, we have a1a \geq 1 and a+3r100a + 3r \leq 100, that is a1003ra \leq 100 - 3r; therefore there are exactly 1003r100 - 3r arithmetic progressions with common difference rr. The total number of arithmetic progressions is therefore
r=133(1003r)=100333r=133r=3300333342=33001683=1617. \sum_{r=1}^{33} (100 - 3r) = 100 \cdot 33 - 3 \sum_{r=1}^{33} r = 3300 - 3 \frac{33 \cdot 34}{2} = 3300 - 1683 = 1617.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.