# Thread: Pigeon hole-proof

1. ## 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.

2. Why do I have that headline? I'm sorry, it should have been "infintite sets of integers" or something instead.

3. Try these.
In the following sets definitions each of k, m, & n is a nonnegative integer and at least one is not zero.
$\displaystyle A = \left\{ {2^k \cdot 3^m \cdot 5^n } \right\}\quad \& \quad B = \left\{ {2^k \cdot 3^m \cdot 7^n } \right\}$
$\displaystyle 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?

4. Originally Posted by Severus
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.

5. Originally Posted by angel.white
(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?

6. Originally Posted by Plato
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" >.<

7. Originally Posted by Plato
Try these.
In the following sets definitions each of k, m, & n is a nonnegative integer and at least one is not zero.
$\displaystyle A = \left\{ {2^k \cdot 3^m \cdot 5^n } \right\}\quad \& \quad B = \left\{ {2^k \cdot 3^m \cdot 7^n } \right\}$
$\displaystyle 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.