Results 1 to 9 of 9

Math Help - A nice problem for fun - Iranian math competition

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Mar 2009
    Posts
    378
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    From
    México
    Posts
    721
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by NonCommAlg View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    My solution makes use of Bertrand's postulate. Perhaps there is another way. Good job!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Triangle competition problem
    Posted in the Geometry Forum
    Replies: 2
    Last Post: December 5th 2010, 08:56 AM
  2. A problem from a grade 9 math competition
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 4th 2009, 05:38 PM
  3. math competition
    Posted in the Math Forum
    Replies: 8
    Last Post: August 14th 2008, 08:45 AM
  4. nice interactive math site
    Posted in the Math Forum
    Replies: 1
    Last Post: January 20th 2008, 06:15 AM

Search Tags


/mathhelpforum @mathhelpforum