Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member royalchicken
    09 Nov '05 20:41
    Is it possible to construct an infinite set of n-element sets, each pair of which has a nonempty intersection, such that there do not exist three sets whose mutual intersection is equal to the intersection of any two of them?

    If not, how big do we have to make a set of such sets so that such a triple exists?
  2. 10 Nov '05 00:29
    cor blimey. I was feeling sick enough before clicking this thread.
  3. Standard member Otis
    Lucky Patzer
    10 Nov '05 00:57
    the set could be infinitely large,
  4. Standard member royalchicken
    10 Nov '05 01:04
    Originally posted by Otis
    the set could be infinitely large,
    Sorry, I was not clear, but you may be right anyway. Such a triplet consists of sets A, B, C such that:

    ABC = AB = AC = BC.

    Have you got a proof?
  5. 10 Nov '05 10:13
    I don't think it can be infinite.
    Consider 2^n n element sets. A1, A2, ...., A(2^n). Now consider the sets A1 intersection Ai i= 1,2,3,...2^n

    These are all subsets of A1. But there are only 2^n subsets of A1 (or ant n element set) So if all these interesctions are distint one of them must be the empty set. If they are not distict that is if A1 intersection A2 and A1 intersection A3 are the same then A1 intersection A2 intersection A3 is equal to A1 intersection A2.

    Anyone know if (2^n) -1 is the strictest upper bound possible?