Sly Subsets of S

Let $T=\{T_1,T_2,\ldots,T_a\}, |T_i|=k_i,i=\overline{1,a}$ .

Note that there are $n!$ permutations of the elements of $S$ .

We will say that a permutation $\pi$ of the elements of $S$ begins with $T_i$ if the first $k_i$ members of $\pi$ are the elements of $T_i$ in some order. The number of permutations beginning with $T_i$ must be $k_i!(12-k_i)!$ .

Because of $T_i\nsubseteq T_j,\forall i\ne j$ , no permutation can begin with two different sets in $T$ ; therefore permutations beginning with different sets in $T$ are distinct.

Therefore: $\displaystyle\sum_{i=1}^a k_i!(12-k_i)!\le 12!$ or $\displaystyle\sum_{i=1}^a \dfrac{1}{\displaystyle\binom{12}{k_i}}\le 1$ .

We have $\displaystyle\binom{12}{k_i}\le \binom{12}{6}$ , so $\displaystyle a\le\binom{12}{6}=924$

Consider $T_1,T_2,\ldots,T_{924}\subset S$ such that $|T_i|=6,\forall i$ . It's easy to look that this subsets such that $T_i\nsubseteq T_j,\forall i\ne j$ .

Since $^{12}C_k$ is maximum for $k=6$ , hence dividing $12$ elements into the sets such that each element contains exactly $6$ elements, is the best way to maximize $a$

One thing that I am not able to prove mathematically is :- Why won't any $a > 924$ would violate the subset condition. Someone Kindly help me out ^_^

Given, S={1,2,3,…12} and T1,T2,…Ta are its subsets S such that Ti⊄Tj for all i≠j. so we must either chose subsets from S such that no subset is a subset of the other if we choose all subsets with size 1 we cant chose subsets with size 2. if we choose all subsets with size 1 we cant chose subsets with size 3. and so on Number of subsets of size r from a set of size n is nCr we need to find to find the maximum value of nCr if n=12 max value of 12Cr is when r=12/2=6 number of subsets = 12C6=924

The total number of subsets that can be formed out of the superset $S$ which meets the below the criteria
$\rightarrow$ $T_i \not \subset T_j \, \forall i \neq j$

can be denoted as

${N \choose R}$

where $R$ indicates cardinality of each subset and $R$ can take values from ${1 to N}$ . $N$ denotes the cardinality of the superset $S$ .

In the given problem where $N=12$ the maximum possible value of ${12 \choose R}$ needs to be evaluated. This turns out to be when $R=6$ . Hence the total number of subsets is ${12 \choose 6} = 924$

We want to have the greatest number of subsets of S that are not subsets of other subsets of S. To accomplish this, we must have the most number of elements in each set to ensure diversity. The best way to do this is to have subsets with the same number of elements such that all of these combinations are unique. Since there are twelve elements, the greatest number of combinations is 12C6 or 12C7 (same value). These will then define the greatest possible number of subsets. Solving, we get 924.

C(12,6)=924

(sorry for my english mistakes) There is a very famous theorem known as "sperner theorem" that I'll prove in the next lines : Let A and B be two "weird" sets if A is not a subset of B nor B is a subset of A. Let X be a family of subsets of {1,2,...,n} such that these subsets are all weird one with other. Then : \sum_{A is a element of X}^{a} {n \choose |A|}^{-1} \le 1

We want the maximum number of disjoint subsets of S. If the number of elements in $T_i$ is less than the number of elements in $T_j$ , then $T_i$ can potentially be a subset of $T_j$ . Therefore we want all $T_i$ 's to have the cardinality (number of elements). This is maximized when we select subsets with cardinality $6$ . This is because ${12 \choose 6} > {12 \choose n}$ , where $n \neq 6$ . Therefore our answer is ${12 \choose 6} = 924$ .

A typical combination problem. From the pascal triangle,the 12Cr with the biggest value is when r is in the middle of 0-12.Hence, 12C6 is the answer.

We can consider a set of primes $P = \{p_1, p_2, p_3, ..., p_{12}\}$ . We will find as many products (of elements of $P$ ) that are mutually coprime as possible. It should be intuitive that the products consist of the same number of primes, for instance taking all possible products of three primes we will have $p_1 p_2 p_3, p_2 p_3 p_4, p_3 p_4 p_5$ , etc. Now we should not find a product of more than 3 primes since two or more of the products of 3 primes will always be factors, and products of less than 3 primes will also be factors of two or more of the products of 3 primes. Introducing products of different number of primes will at least sacrifice one product from the count. Then, we simply look for all the possible ways to find a certain number $n$ of primes from $P$ to multiply together, that is ${12 \choose n} = \frac{12!}{n!(12-n)!}$ . It has a maximum when $n = 6, {12 \choose n} = 924$ . The original problem should behave similarly, when we consider the factor of $1$ to prime numbers as the subset of $\varnothing$ to sets.