0

The set of all positive integers is partitioned into several(finitely many) arithmetic progressions. Show that there is at least one among these arithmetic progressions whose initial term is divisible by its difference.

my attempt is as follows :

Since there are finite partitions if we were to color each arithmetic progression by some individual color at some point a repetition of colors will occur . (I will try to prove this ) . Now if we color all of the integers at some point some color matches up with integer=$0$ This color must be of the form ak where a is the distance between each term in the sequence

m3h3mm3d
  • 179
  • 2
    Is the partition into finitely many arithmetic progressions? in that case the product of the differences for the progressions is a positive integer, and thus in one of the progressions. (if there are progressions with 0 difference, ignore those, as there are finitely many you can take a large enough multiple of the product of the rest of the differences to guarantee it's not in a progression with 0 difference) – Mor A. Jul 09 '21 at 12:47
  • I'm not sure if you are seeking a critique of your attempt as a solution or as a broad approach that has not yet been carried out ("I will try to prove this.") In its present form it is not clear how the coloring of "all of the integers" is supposed to relate to the partition of the positive integers (in particular "integer=0" is not positive). – hardmath Jul 09 '21 at 12:49
  • Lets say we have n partitions , where each partition has some beginning element and some constant difference between its sequential elements . Now if we color each sequence using a unique color , at some point the pattern will be such that a set of colors are repeated. If we extend this pattern behind to the left side of the integers , this repeatition at some point coincides with 0 , and for this color we have a partition that q asks , as far as i can think of – m3h3mm3d Jul 09 '21 at 12:54
  • Ofc , i am trying to prove it ,but i think finiteness suggest that some repetition of a pattern occurs , i think forming a non pattern emerging series of colors using finite things is not possible. But using infinite partitions one can somehow avoid the repetition i think , but yes i will try to prove it – m3h3mm3d Jul 09 '21 at 13:19
  • Take the lcm of the finitely many differences. This gives the period for the repetition of your colorings. – Barry Cipra Jul 09 '21 at 13:26
  • So , can we say its true? @BarryCipra – m3h3mm3d Jul 09 '21 at 13:27
  • Can we say what is true? (I.e., what is the antecedent of "it" in your reply to my comment?) All I was really doing was pointing out the key idea that'll make your attempt work. – Barry Cipra Jul 09 '21 at 13:30
  • Oh , let me be clearer . I wanted to ask whether since here is a period using lcm can we say the extension towrads negative numbers is true? That is i was meaning the attempt in the beginning. Ofc you dont have to answer – m3h3mm3d Jul 09 '21 at 13:33
  • No, that's OK, thanks for the clarification. I'd say yes, your basic idea is correct – Barry Cipra Jul 09 '21 at 13:38

2 Answers2

1

Let $a_1, a_2,\ldots,a_k$ the initial terms of our $k$ progressions, and let $d_1 , d_2 ,\ldots , d_k $ be their differences. The number $d_1 d_2 \cdots d_k$ is an element of one of these progressions, say, the $i$th one. Therefore, there is a positive integer $m$ so that

$$d_1 d_2 \cdots d_k = a_i + md_i\Longrightarrow d_1 d_2 \cdots d_k − md_i = a_i $$

So $a_i$ is divisible by $d_i$. This problem had nothing to do with the Pigeon-hole Principle. We included it to warn the reader that not all that glitters is gold. Just because we have to prove that one of many objects has a given property, we cannot necessarily use the Pigeon-hole Principle.

Sorry , this is the solution in the book and apparently they have included it in pigeonhole section , even tho there is no need apparently.

anankElpis
  • 1,255
m3h3mm3d
  • 179
0

Prove with the following partition of $\;\Bbb N\;$ is arithmetic sequences:

$$A_0:=\left\{\;1,3,5,...,2n-1,..\;\right\}$$

$$A_1: \left\{\;2,6,10,14,...,4n-2,...\;\right\}$$

$$A_2: \left\{\;4, 12,20,28,...,8n-4,...\;\right\}$$

$$\ldots\;$$

$$A_k: \left\{\;2^k, 2^k+2^{k+1},...2^{k+1}n-2^k,...\;\right\}$$

$$\ldots$$

Check the above is a partition of the naturals, that each element of the partition is an arithmetic sequence...and that there is no sequence whose first element is divided by its difference.

Disclaimer : after the answer was posted the OP commented the partition must be finite. I'll leave this undeleted in case someone can find some use to it, at least for a while.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • Is this a counter example? Because in that case the question would be wrong but i think question is not wrong , just because the book describing this q is a good book . I admit thats not a great argument but this is how i feel – m3h3mm3d Jul 09 '21 at 12:56
  • As you were asked in the comments: if the number of sets in the partition is finite then there might be another answer. As it is not specifically written the above is a counter example with infinite (countable) sets, each of which is an arithmetic sequence. – DonAntonio Jul 09 '21 at 12:59
  • Ah , yes it’s finite sorry – m3h3mm3d Jul 09 '21 at 13:00
  • Sorry m I didn’t mean to disrespect your solution , its on me – m3h3mm3d Jul 09 '21 at 13:13
  • @MehemmedYusifov Don't worry, I understand. The disclaimer is just for anyone who could think I posted something that goes against what you asked. – DonAntonio Jul 09 '21 at 13:16