Author |
Topic: Arithmetic progressions and partitions (Read 1803 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Arithmetic progressions and partitions
« on: Mar 17th, 2003, 11:06am » |
 Quote  Modify
|
Can the positive integers {1, 2, 3, ...} be partitioned into a finite number of sets S1, ... , Sk, each of which is an arithmetic progression - that is,
S1 = {a1, a1 + d1, ...}
...
Sk = {ak, ak + dk, ...}
- and such that all the di's are nonzero and distinct? Note that if we allowed equal di's, the answer would be a trivial yes; just take S1 = "odd integers" and S2 = "even integers".
|
| « Last Edit: Mar 25th, 2003, 2:07pm by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Arithmetic progressions and partitions
« Reply #1 on: Mar 17th, 2003, 1:25pm » |
Quote Modify
|
If I understand right we've got
if k needn't be larger than 1, there's the trivial solution with d1=1
if the number of partitions didn't have to be finite you could use
a1=1 and d1=2
a2=2 and d2=4
a3=4 and d3=8
a4=8 and d4=16
a5=16 and d5=32
etc
But at the moment I don't see how it could work for a finite number of partitions (where k > 1). It seems to me some of the sets will allways overlap..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Arithmetic progressions and partitions
« Reply #2 on: Mar 25th, 2003, 1:02pm » |
Quote Modify
|
how about another trivial case,
S1 = {1} (a1 = 1, d1 = 0)
S2 = {2,3,4 ..} (a2 = 2, d2 = 1)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Arithmetic progressions and partitions
« Reply #3 on: Mar 25th, 2003, 2:06pm » |
Quote Modify
|
OK, sorry, I forgot to mention the di are nonzero. I'm going to change my post. But I really mean this problem; aside from the trivial cases, it is very interesting, and has a beautiful solution.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Arithmetic progressions and partitions
« Reply #4 on: Mar 25th, 2003, 6:40pm » |
Quote Modify
|
So far every time I look at this I get to the same point, and then run out of time before I can make any definite improvement. I'm posting this much simply so I don't have look it up again:
Because of the Chinese Remainder Theorem, no pair di, dk can be relatively prime (otherwise, the congruences x=ai mod di and x=ak mod dk have mutual solutions, some of which will occur in both Si and Sk).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Arithmetic progressions and partitions
« Reply #5 on: Apr 24th, 2003, 10:10pm » |
Quote Modify
|
No, they cannot.
Say S_i = { ai, ai + di, ai + 2di, ... }.
If the di's are all distinct and positive, we may assume
1 < d1 < d2 < . . . < dk.
If N is the disjoint union of S_1,...S_k, we have:
sum_{n \in N} x^n = sum_{i=1}^{k} sum_{n \in S_i} x^n
(*) x/(1-x) = sum_{i=1}^{k} x^ai/(1-x^di)
But as x->e^(2pi*i/dk), the function
x^ai/(1-x^di)
remains bounded unless dk | di, which happens only when i=k.
Thus the left side of (*) remains bounded, while the right side has a pole; therefore they cannot be equal.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Arithmetic progressions and partitions
« Reply #6 on: Nov 25th, 2007, 2:17am » |
Quote Modify
|
on Apr 24th, 2003, 10:10pm, Eigenray wrote:No, they cannot.
Say S_i = { ai, ai + di, ai + 2di, ... }.
If the di's are all distinct and positive, we may assume
1 < d1 < d2 < . . . < dk.
If N is the disjoint union of S_1,...S_k, we have:
sum_{n \in N} x^n = sum_{i=1}^{k} sum_{n \in S_i} x^n
(*) x/(1-x) = sum_{i=1}^{k} x^ai/(1-x^di)
But as x->e^(2pi*i/dk), the function
x^ai/(1-x^di)
remains bounded unless dk | di, which happens only when i=k.
Thus the left side of (*) remains bounded, while the right side has a pole; therefore they cannot be equal. |
|
Soory for opening this ancient topic, but I cannot resist: It may be confusing when you use natural number i in the context e^{i phi}. 
BTW: nice reasoning
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print