A few years ago, somebody told me a lovely problem. I suspect there may be more to it (which I would be interested in learning), and would very much like to find a reference, it makes me uncomfortable to use it in class without being able to point to its source. 


The problem is as follows. I'll post the solution I know, which is the reason I like it, as an answer, to give a bit of a chance to people who read it and want to think about it without being spoiled.


Assume the natural numbers are partitioned into finitely many arithmetic progressions. Then two of these progressions must have the same common difference. 



Finitely many arithmetic progressions
You're probably thinking of the proof, via generating functions, due to D J Newman. I don't have a reference to the first appearance in print, but it's in his book, A Problem Seminar, problem 90, on page 18, with solution on page 100. 


I suppose that when you state the problem you must require finitely many but *at least two* arithmetic progressions. 


