Q: "Determine the number of ways to choose four integers from 1 to 100 such that there is an arithmetic progression between the integers."
My solution:
Let a, b, c, d denote the four integers, then 1 $\le$ a $\lt$ b $\lt$ c $\lt$ d $\le$ 100. Since there is an arithmetic progression between the integers we say that (a,
b, c, d)=(x, x+k, x+2k, x+3k). From d = x+3k $\le$ 100 we get:
3k $\le$ 99
k $\le$ 33
And because k must be one or greater than one for there to exist an arithmetic progression, we have 1 $\le$ k $\le$ 33. With the only possible values for k set to be the integers 1 to 33, we get the possible values of x for a pre-determined value k by taking 100 – 3k. For example:
If k = 32 then 100-3k = 100-96 = 4, and so we have the possible values 1 $\le$ x $\le$ 4 for x when k is 32. Namely, the valid sequences are (1,33,65,97),(2,34,66,98),(3,35,67,99) and (4,36,68,100).
Now for a value k, we note that the number of vaules possible for x is also the number of valid sequences for that k, i.e. the expression 100-3k gives the number of ways to choose four integers with an arithmetic progression. Hence, we use the expression for all values k and add the number of valid sequences together to get our final result:
$$\sum_{k=1}^{33} 100-3k = 1617$$
However, the solution is supposed to be 3334. Any suggestions?
Best Answer
Your answer and reasoning is correct in my opinion. I can only imagine that the authors alsocounted decreasing arithmetic sequences - but my (and your) interpretation of "choose four integers such that there is a progresssion" is that I pick a subset of size $4$ and check if the elements of this set can be arranged to form a progression. That is, while there are two distinct arithmetic progessions such as $(2,12,22,32)$ and $(32,22,12,2)$, they come from the same picking of four numbers.
So at best the problem statement was ambiguous.