# A nice problem for fun - Iranian math competition

• Dec 4th 2009, 04:13 PM
Bruno J.
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.
• Dec 4th 2009, 04:22 PM
lvleph
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.
• Dec 4th 2009, 04:53 PM
Jose27
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$.
• Dec 4th 2009, 06:09 PM
Bruno J.
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.
• Dec 4th 2009, 09:56 PM
Drexel28
Quote:

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.
• Dec 5th 2009, 05:27 AM
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.
• Dec 5th 2009, 05:30 AM
Drexel28
Quote:

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.
• Dec 6th 2009, 08:33 PM
Bruno J.
My solution makes use of Bertrand's postulate. Perhaps there is another way. Good job!
• Dec 7th 2009, 10:06 PM
Drexel28
Quote:

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.