Posers and Puzzles

Posers and Puzzles

  1. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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. Earth Prime
    Joined
    16 Mar '05
    Moves
    21936
    10 Nov '05 00:29
    cor blimey. I was feeling sick enough before clicking this thread.
  3. Standard memberOtis
    Lucky Patzer
    Ohio University
    Joined
    23 Oct '03
    Moves
    9879
    10 Nov '05 00:57
    the set could be infinitely large,
  4. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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. Joined
    08 Oct '05
    Moves
    723
    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?
Back to Top