Results 1 to 7 of 7

Math Help - Pigeon hole-proof

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    7

    Pigeon hole-proof

    I've got quite a tricky problem here:

    Find an example of four infinite subsets of the set of all positive integers so that the intersection of any three of them is an infinite set, while the intersection of all four of them is an empty set.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2008
    Posts
    7
    Why do I have that headline? I'm sorry, it should have been "infintite sets of integers" or something instead.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1
    Try these.
    In the following sets definitions each of k, m, & n is a nonnegative integer and at least one is not zero.
    A = \left\{ {2^k  \cdot 3^m  \cdot 5^n } \right\}\quad \& \quad B = \left\{ {2^k  \cdot 3^m  \cdot 7^n } \right\}
    C = \left\{ {2^k  \cdot 5^m  \cdot 7^n } \right\}\quad \& \quad D = \left\{ {3^k  \cdot 5^m  \cdot 7^n } \right\}

    Why do these work?
    Last edited by Plato; February 11th 2008 at 08:07 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by Severus View Post
    I've got quite a tricky problem here:

    Find an example of four infinite subsets of the set of all positive integers so that the intersection of any three of them is an infinite set, while the intersection of all four of them is an empty set.
    If I understand the problem correctly (which I'm not entirely sure that I do) I think you could use elements which are congruous to 1mod4, 2mod4, 3mod4, and 4mod4.

    These should be infinite both forwards and backwards, and they should never intersect.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1
    Quote Originally Posted by angel.white View Post
    (which I'm not entirely sure that I do) I think you could use elements which are congruous to 1mod4, 2mod4, 3mod4, and 4mod4. These should be infinite both forwards and backwards, and they should never intersect.
    Find an example of four infinite subsets of the set of all positive integers so that the intersection of any three of them is an infinite set, while the intersection of all four of them is an empty set.
    Did you notice that condition?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by Plato View Post
    Find an example of four infinite subsets of the set of all positive integers so that the intersection of any three of them is an infinite set, while the intersection of all four of them is an empty set.
    Did you notice that condition?
    I see, I read it as "empty" rather than "infinite" >.<
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Feb 2008
    Posts
    7
    Quote Originally Posted by Plato View Post
    Try these.
    In the following sets definitions each of k, m, & n is a nonnegative integer and at least one is not zero.
    A = \left\{ {2^k  \cdot 3^m  \cdot 5^n } \right\}\quad \& \quad B = \left\{ {2^k  \cdot 3^m  \cdot 7^n } \right\}
    C = \left\{ {2^k  \cdot 5^m  \cdot 7^n } \right\}\quad \& \quad D = \left\{ {3^k  \cdot 5^m  \cdot 7^n } \right\}

    Why do these work?
    Ah....now I get it. The union of all four of them is empty because the prime factors of an integer only can be in one way.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 17th 2011, 07:44 PM
  2. Pigeon-hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 31st 2011, 05:14 AM
  3. Pigeon Hole Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 18th 2010, 06:53 AM
  4. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 01:41 PM
  5. Pigeon hole-proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 11th 2008, 01:02 AM

Search Tags


/mathhelpforum @mathhelpforum