Subsets of a set such that no two have two equal elements

[iceblits]

Homework Statement

Given a set of n elements one after another (1,2,...n) Find the minimum n for which there are about 1000 subsets such that every two subsets will have at least 2 elements not in common

Homework Equations

The Attempt at a Solution

I did this problem for 1 element not in common and I got n C (n/2)=1000 so n is around 12 or 13 which means that for n=13, we can take a subset with cardinality 6 or 7 such that no two of the subsets will have all the same elements...This answer was right.
Saying n=24 or 26 will result in a sufficient number to guarantee every 2 subsets will have alteast 2 elements not in common, but I don't know if it will be the minimum number

 

[mighty2000]

required.


Hello! Interesting problem. Let's approach it step by step. First, we know that the number of subsets of a set with n elements is equal to 2^n. So, if we want to have 1000 subsets, we need to find the value of n that satisfies the equation 2^n = 1000. Solving for n, we get n = log2(1000) ≈ 9.9658. This means that we need at least 10 elements to have 1000 subsets.

Now, for the second part of the problem, we need to make sure that every two subsets have at least 2 elements not in common. This means that for every subset, there are at least 2 elements that are not in any other subset. To guarantee this, we can use the concept of pigeonhole principle. If we divide the n elements into subsets of size 2, there will be n/2 subsets. Since we need at least 1000 subsets, we can set up the following inequality:

n/2 ≥ 1000
n ≥ 2000

This means that we need at least 2000 elements to guarantee that every two subsets have at least 2 elements not in common. However, this is not the minimum number required. For example, if we have n=2000, we can divide the elements into subsets of size 2 and have 1000 subsets, but there might be some elements that are not in any subset.

To find the minimum number required, we can use the concept of pairwise disjoint sets. This means that for every pair of subsets, there is at least one element that is not in any other subset. In other words, we can divide the n elements into subsets of size 3, and have n/3 subsets. We can set up the following inequality:

n/3 ≥ 1000
n ≥ 3000

So, the minimum value of n is 3000, which means we need at least 3000 elements to guarantee that every two subsets have at least 2 elements not in common. This is the minimum number required, and any value lower than this will not satisfy the condition. Therefore, n=3000 is the minimum value required to have about 1000 subsets such that every two subsets will have at least 2 elements not in common.