1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem with sets

  1. May 2, 2004 #1
    Let's imagine two sets A = {1,2,...,k} and B = {-1,-2,...,-k} for some natural k, then let's create n two-element sets X_1,X_2,...,X_n such that for each 0<i=<n X_i = {a,b} where a is from A and b is from B but |a|<>|b|. We know how do sets X_i look like and according to this we will choose the set C = {c_1,c_2,...,c_k} where |c_i|=i such that the number (denoted MAX) of sets X_1,X_2,...,X_n that have at least one common element with C is maximal. Determine the maximal constant 0<=c<=1 such that MAX>=[cn] for arbitrary n,k and sets X_1,X_2,...,X_n.
    NOTE: [x] denotes the integral part of number x

    k = 2, A = {1,2}, B = {-1,-2}
    n = 4, X_1 = {-1,-2}, X_2 = {-1,2}, X_3 = {1,-2}, X_4 = {1,2}
    we can choose C = {1,2} (in this case we have more possibilities) the number X_i that have at least one common element with C is 3, X_1 and C have no common element.

    From this example we can easily see, that c<=3/4, I think that c=3/4 is sufficient condition, but I can't prove it.
    Could anybody help me with it? Thanks.
  2. jcsd
  3. May 17, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    This doesn't make a whole lot of sense. For one:
    To me, this says that C = {1, 2, 3, 4, ..., k}. It seems that the set C will always look like this. From there, it is still not clear as to exactly what we're looking for. It is further confused by your example because you said:
    But then gave, as an example:
    which takes both its elements from A.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: A problem with sets
  1. Problem on Set (Replies: 9)

  2. Set mapping problem (Replies: 2)