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.

`$\mathbb Z_N$`

where $N$ is any common multiple of all differences). Here the generating function approach will meet some troubles. – fedja May 20 '10 at 5:18