Maximizing Sets: A Problem with Sets

  • Thread starter dapet
  • Start date
  • Tags
    Sets
In summary: So, which is it? Do both elements come from A or is it one from A and one from B?In summary, the conversation discusses the creation of two sets A and B, each containing k natural numbers, and n two-element sets X_1, X_2, ..., X_n, where each set contains one element from A and one element from B. The task is to choose a set C of size k, where the elements are numbered from 1 to k, such that the number of X_i sets that have at least one element in common with C is maximal. The goal is to determine the maximum constant c, where 0<=c<=1, such that the number of X_i sets with at
  • #1
dapet
9
0
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

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 news on Phys.org
  • #2
This doesn't make a whole lot of sense. For one:
we will choose the set C = {c_1,c_2,...,c_k} where |c_i|=i
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:
for each 0<i=<n X_i = {a,b} where a is from A and b is from B
But then gave, as an example:
X_4 = {1,2}
which takes both its elements from A.
 
  • #3


To determine the maximal constant c, we need to consider the worst case scenario where the sets X_i have the most common elements with C. In this case, let's assume that all n sets have one common element with C except for one set, say X_n, which has no common element with C. This means that we can only have n-1 common elements with C.

Now, let's consider the size of C. Since we want to maximize the number of common elements, we want to choose the largest possible set C. From the example, we can see that when k = 2, the largest possible set C is {1,2}. However, when k = 3, the largest possible set C is {1,2,3} as we need to have at least one element from A and one element from B for each set X_i.

Therefore, the size of C is equal to k, and the number of common elements with C is at most n-1. This means that the maximal constant c is given by:

c = (n-1)/k

However, we need to consider the integral part of this expression, since the number of common elements must be an integer. This gives us:

[ (n-1)/k ] = [n/k]

Therefore, the maximal constant c is given by:

c = [n/k]

Hence, the maximal constant c is equal to the integral part of n/k. In the worst case scenario, we can have [n/k] common elements with C, which means that we can have at most [n/k] sets X_i with at least one common element with C.

In the example given, k = 2 and n = 4, and we can see that [n/k] = [4/2] = [2] = 2. This means that c = 2 is the maximal constant for this case.

In general, for any arbitrary n and k, the maximal constant c is given by:

c = [n/k]

Therefore, we can conclude that the maximal constant c = [n/k] is sufficient to ensure that MAX >= [cn] for arbitrary n, k, and sets X_1, X_2, ..., X_n.
 

1. What is the purpose of maximizing sets?

The purpose of maximizing sets is to find the largest possible set of elements that fit certain criteria or constraints. This can be useful in various fields such as computer science, mathematics, and statistics.

2. How do you determine which elements to include in a maximized set?

The specific method for determining which elements to include in a maximized set can vary depending on the problem at hand. However, some common strategies include using mathematical algorithms, heuristic methods, or trial-and-error approaches.

3. Can maximizing sets be applied to real-world problems?

Yes, maximizing sets can be applied to real-world problems in various fields. For example, it can be used to optimize resource allocation, maximize profit, or find the most efficient schedule for completing tasks.

4. Are there any limitations to maximizing sets?

Like any problem-solving method, there are limitations to maximizing sets. It may not always be possible to find the absolute maximum set, and the process can become computationally complex for larger sets or when dealing with multiple constraints.

5. How can maximizing sets be beneficial in scientific research?

Maximizing sets can be beneficial in scientific research as it allows for the identification of the largest possible set of relevant data. This can help researchers make more accurate conclusions and predictions, and can also aid in the development of algorithms and models.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
711
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
706
  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
687
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
Replies
0
Views
262
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
Replies
3
Views
618
Replies
2
Views
1K
Back
Top