For a subset , let . Show that there is a unique partition of such that and contain no odd prime.
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.