# Thread: A nice problem for fun - Iranian math competition

1. ## A nice problem for fun - Iranian math competition

For a subset $S \subset \mathbb{N}$, let $S+S=\{s_1+s_2 : s_1,s_2 \in S\}$. Show that there is a unique partition $A,B$ of $\mathbb{N}$ such that $A+A$ and $B+B$ contain no odd prime.

2. So I am thinking this has something to do with $S$ being an ideal in $\mathbb{N}$. And that every ideal of $\mathbb{N}$ is of the form $a \mathbb{N}$ where $a \in \mathbb{N}^+$. I believe we may want $A + B = \mathbb{N}$. That is my thoughts right off hand.

3. Let $A,B$ denote the partition of $\mathbb{N}$ in even and odd integers (resp), and let $C,D$ be any other partition that satisfies the condition then $C\cap A\neq \emptyset$ (say) but then clearly $C\subset A$ because odd+even=odd and so since $D$ cannot be contained in $A$, and by the same argument $D\subset B$ and since they form a partition $C=A$ and $D=B$.

4. Why "clearly" $C \subset A$? Odd numbers are allowed, just not odd primes. Nowhere do you use the prime-related condition. You just replaced it by a stronger condition, which, as you noticed, makes the problem quite trivial.

5. Originally Posted by Bruno J.
For a subset $S \subset \mathbb{N}$, let $S+S=\{s_1+s_2 : s_1,s_2 \in S\}$. Show that there is a unique partition $A,B$ of $\mathbb{N}$ such that $A+A$ and $B+B$ contain no odd prime.
I can see doing this two ways.

Method 1:

Spoiler:
The obvious answer is the partition of $\mathbb{N}$ into odds and evens. We can then use Dirichlet's theorem on arithmetic progressions (Dirichlet's theorem on arithmetic progressions - Wikipedia, the free encyclopedia) to prove this partition is unique

Method 2:

Spoiler:
I am less comfortable with this one, but it seems that we can do this inductively utilizing the weak form of Bertrand's Postulate (http://en.wikipedia.org/wiki/Bertrand's_postulate)

These are kind of big-gun theorem's though. I'll get back to you if I can think of a simpler more elegant method.

6. 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.

7. Originally Posted by NonCommAlg
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.
True, but one (or at least I) feel as though most of these problems are able to be solved without the use of something like Bertrand's Postulate. Oh well, if that's how it's to be solved...then sweet! I'll post up a solution later.

8. My solution makes use of Bertrand's postulate. Perhaps there is another way. Good job!

9. Originally Posted by Bruno J.
My solution makes use of Bertrand's postulate. Perhaps there is another way. Good job!
As was stated, you can Dirichlet's theorem, but that is IMO opinion honestly an inaccesible theorem to most middle schoolers.