So I am thinking this has something to do with being an ideal in . And that every ideal of is of the form where . I believe we may want . That is my thoughts right off hand.
Let denote the partition of in even and odd integers (resp), and let be any other partition that satisfies the condition then (say) but then clearly because odd+even=odd and so since cannot be contained in , and by the same argument and since they form a partition and .
i wouldn't call Bertrand's postulate a big-gun theorem because the proof (Erdos) of this theorem is fairly short and very elementary. actually, students who participate in math competetions
(even IMO, never mind Putnam!) are expected to know and use it. anyway, i just wanted to add this to Drexel28's comment that the problem is easily solved using Bertrand's postulate.