2
$\begingroup$

From Bóna's A Walk through Combinatorics:

Prove or disprove that if we partition the positive integers into finitely many arithmetic progressions then there will be at least one arithmetic progression whose difference and initial term are equal.

A variant of this problems asks to prove that there will be at least one arithmetic progression whose difference divides the initial term, which has an elementary proof. I suspect the same arithmetic progression will have the initial term equal to the difference. However, I cannot prove it.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What is the origin of this question? Usually if you ask to "prove" something you should have some strong evidence that the proof exists. $\endgroup$
    – Fedor Petrov
    Commented Feb 25, 2019 at 14:30
  • 1
    $\begingroup$ Sorry I should’ve asked for counter example also. I have edited the question now. The source is the variant mentioned below the main question which is an exercise from “A Walk Through Combinatorics”. $\endgroup$
    – VRS
    Commented Feb 25, 2019 at 15:27
  • $\begingroup$ Counter example where there are an infinite number of infinite arithmetic progressions and NO progression has the difference equal to the initial term. for k from 1 to inf { S(k) = 2^k * n + 2 ^ (k-1) for n from 0 to inf } S(1) is odd integers; S(2) is 2, 6, 10 - twice an odd integer; and continues for powers of 2. In all cases the initial term is the difference / 2. $\endgroup$
    – Judah Greenblatt
    Commented Feb 25, 2019 at 21:43

1 Answer 1

Reset to default
7
$\begingroup$

Any progression (if they are all infinite, of course, but otherwise the statement is clearly wrong) should have its initial term $a$ not greater than the difference $d$. Indeed, if $a>d$, and $a-d$ is covered by another progression $P$ with difference $d_1$, then $a-d+dd_1$ is covered twice --- a contradiction. Therefore if $a$ is divisible by $d$, we must have $a=d$. And such $a$ exists as you noted in OP (a short proof: take a progression which contains the product of all differences).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .