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.(adsbygoogle = window.adsbygoogle || []).push({});

NOTE: [x] denotes the integral part of number x

Example:

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# A problem with sets

**Physics Forums | Science Articles, Homework Help, Discussion**