wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Partition naturals into APs
        
(Message started by: Aryabhatta on Aug 5^th, 2005, 8:52am)

Title: Partition naturals into APs
Post by Aryabhatta on Aug 5^th, 2005, 8:52am

Can we partition the set of natural numbers into a finite number (at least 2) of arithmetic progressions, such that no two progressions have the same common difference?

This is probably a well known result, but pretty interesting nevertheless.

Title: Re: Partition naturals into APs
Post by Icarus on Aug 5^th, 2005, 3:05pm

If you demand that your arithmetic progressions all have n^th term of form nd for some fixed d, then yes, it is a very well known result! If you allow the terms to have form nd + c for some fixed d, c, then the situation is harder.

Title: Re: Partition naturals into APs
Post by Aryabhatta on Aug 5^th, 2005, 5:42pm

It could be nd+c.
For instance one partition is 2n, 4n+1, 4n+3.

Title: Re: Partition naturals into APs
Post by Aryabhatta on Aug 12^th, 2005, 7:46pm

Hint: [hide] sometimes it makes things simple to make things complex [/hide] :

Title: Re: Partition naturals into APs
Post by Eigenray on Aug 15^th, 2005, 1:08pm

Perhaps people are remaining silent because the problem is already on this site, and they do not wish to spoil it.

Anyway, both the result and its proof are far too lovely to only be listed once!

Title: Re: Partition naturals into APs
Post by Aryabhatta on Aug 15^th, 2005, 4:17pm

on 08/15/05 at 13:08:00, Eigenray wrote:

Perhaps people are remaining silent because the problem is already on this site, and they do not wish to spoil it.

Aw shoot! Here is the link: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1047927969;start=0#0

Quote:

Anyway, both the result and its proof are far too lovely to only be listed once!

Completely agree.
The approach is beautiful and is basically the building block for Analytic number theory!