Given $7$ distinct positive integers, prove that there is an infinite arithmetic progression of positive integers $a, a+d, a+2d,...,$ with $a \le d$, that contains exactly $3$ or $4$ of the $7$ given integers.

Letting those $7$ integers be $x_1, x_2, ..., x_7$ in ascending order, I thought that you could take any two of the smaller $x_i$ (more precisely $x_i$ for $i=1$ to $6$ max) and find their difference. Then you could just keep adding the difference till you encounter another $x_i$— or, divide the difference to make it small enough to keep on adding to $x_i$ and eventually get another $x_i$ from the set. However, I realise this is a pretty terrible line of thought because I don't think I've proven anything much, I haven't taken care of $a \le d$ and in my reasoning, there could then be more than 3 or 4 from the given set. Any help would really be appreciated!

  • $\begingroup$ Looks like some kind of generalized PigeonHole Principle to me, though no idea how that can be applied. $\endgroup$ – MalayTheDynamo Jun 21 '18 at 15:53
  • $\begingroup$ @DietrichBurde — thanks for the notice. I fixed that now. $\endgroup$ – jjhh Jun 21 '18 at 15:58

If there are three or four even integers, you're done.

If there are more than four even integers, look at those even integers modulo 4, modulo 8, etc., until they fall into two classes, one of which has three or four members.

If there are fewer than three even integers, then there are more than four odd integers, and play the same game with them.

  • $\begingroup$ for the last case (more than four odd integers), would I be looking at the odd integers modulo 3 then? $\endgroup$ – jjhh Jun 22 '18 at 15:28
  • 1
    $\begingroup$ No, you still go mod 4, 8, 16, and so on. $\endgroup$ – Gerry Myerson Jun 22 '18 at 23:44
  • $\begingroup$ So are we OK now, jjhh? $\endgroup$ – Gerry Myerson Jun 25 '18 at 13:16
  • $\begingroup$ wait could you explain why though...? It's not quite clear to me yet $\endgroup$ – jjhh Jun 25 '18 at 13:31
  • $\begingroup$ You have 7 integers. You split the whole set of integers into two arithmetical progressions (the evens, and the odds). If one of those progressions has 3 or 4 of your 7 integers, you're done. If not, then one of those progressions has at least 5 of your integers. You split that progression into two progressions (by looking at it modulo 4). If one of the two new progressions has 3 or more of your integers, you're done. If not, then one of the new progressions has at least 5 of your integers. You split it into two progressions modulo 8. And so on, and so on, and so on. OK now? $\endgroup$ – Gerry Myerson Jun 26 '18 at 7:16

Let us change the problem two ways initially. Let us allow $0$ as well as positive integers both for the integers we are supplied and $a$ and have only $5$ integers.

If the set of five integers has a common factor we can divide it out of all of them, $a$ and $d$. If they are all odd we can subtract $1$ from all of them and $a$, then they have a common factor of $2$ which we can divide out. Eventually we get to a point where the numbers do not all have the same parity. At that point either $a=0,d=2$ or $a=1,d=2$ will be the arithmetic progression we need. We restore the values of the numbers by adding and multiplying. As the numbers did not include $0$ at the beginning we will now have $a \gt 0$.

Now we consider the case where we are given $6$ numbers. Again we can work downwards until we have numbers differing in parity. If there are three or four of the same parity we again have a solution with $d=2$ and add and multiply up to get to the original numbers. If there is just one that is a different parity from the rest, we ignore it from now on and solve the problem with the other five. The one we ignored will no longer be integral after the next division by $2$ so it will not be part of the progression.

Again for seven, we can get to a mix of parities. If there are three or four of the same parity we are done. Otherwise there are one or two and we continue with one of the previous cases ignoring them.

As an example, I will do one $$\begin {array} {r r r r r r r} 9&11&17&65&157&289&585\\ 8&10&16&64&156&288&584\\ 4&5&8&32&78&144&292\\ 2&X&4&16&39&72&146\\ 1&X&2&8&X&36&73 \end {array}$$ and now we have three evens, so $a=0,d=2$ will give us three numbers in the progression. We subtracted $1$ then divided by $2$ three times, so for the original set we want $a=1,d=16$ and $17,65,289$ are in the series while none of the others are.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.