wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Arithmetic progressions and partitions
        
(Message started by: Pietro K.C. on Mar 17^th, 2003, 11:06am)

Title: Arithmetic progressions and partitions
Post by Pietro K.C. on Mar 17^th, 2003, 11:06am

Can the positive integers {1, 2, 3, ...} be partitioned into a finite number of sets S₁, ... , S_k, each of which is an arithmetic progression - that is,

S₁ = {a₁, a₁ + d₁, ...}
...
S_k = {a_k, a_k + d_k, ...}

- and such that all the d_i's are nonzero and distinct? Note that if we allowed equal d_i's, the answer would be a trivial yes; just take S₁ = "odd integers" and S₂ = "even integers".

Title: Re: Arithmetic progressions and partitions
Post by towr on Mar 17^th, 2003, 1:25pm

If I understand right we've got
http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?md5=dbf94182515c5544c74d4db0a307c4b9

if k needn't be larger than 1, there's the trivial solution with d₁=1

if the number of partitions didn't have to be finite you could use
a₁=1 and d₁=2
a₂=2 and d₂=4
a₃=4 and d₃=8
a₄=8 and d₄=16
a₅=16 and d₅=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..

Title: Re: Arithmetic progressions and partitions
Post by towr on Mar 25^th, 2003, 1:02pm

how about another trivial case,
S1 = {1} (a1 = 1, d1 = 0)
S2 = {2,3,4 ..} (a2 = 2, d2 = 1)

Title: Re: Arithmetic progressions and partitions
Post by Pietro K.C. on Mar 25^th, 2003, 2:06pm

OK, sorry, I forgot to mention the d_i 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.

Title: Re: Arithmetic progressions and partitions
Post by Icarus on Mar 25^th, 2003, 6:40pm

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 d_i, d_k can be relatively prime (otherwise, the congruences x=a_i mod d_i and x=a_k mod d_k have mutual solutions, some of which will occur in both S_i and S_k).

Title: Re: Arithmetic progressions and partitions
Post by Eigenray on Apr 24^th, 2003, 10:10pm

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.

Title: Re: Arithmetic progressions and partitions
Post by Hippo on Nov 25^th, 2007, 2:17am

on 04/24/03 at 22:10:19, Eigenray wrote:

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