Selfish shellfish

$12=1+11=2+10=3+9=4+8=5+7=6+6$ and vice-versa... Hence, we have $6\times 2=12$ possible combinations of a subset and it's complement...

In order to a set be selfish, when the set has $i$ elements, it must have the number $i$ in it... So, we proceed by checking $12$ cases...

We start with one element set... It must have the number $1$ , hence it can't be rearranged in any other way... Next we work with two element set... It must have the number $2$ in it, and the other element can be chosen from the remaining $11$ numbers in $\dbinom{11}{1}$ ways... Same way, the three element set must have the number $3$ in it, and the other two can be chosen from the remaining 11 in $\dbinom{11}{2}$ ways... And so on till the $11$ element set...

But wait... The question says that the complement must be selfish too... So, when we are working with the $i$ element set, the number $(12 - i)$ must not be in that set i.e. the number $(12-i)$ should be in the complement of that set... Thus that leaves $10$ possible choices for that set... So, when working with the one element set, we simply have the set $(1)$ and the complement is $(2, 3, ..., 11, 12)$ ... For two element set, we have the number $2$ and exactly $\dbinom{10}{1}$ ways to choose the second one... For three element set, we have the number $3$ and exactly $\dbinom{10}{2}$ ways to choose the other two... And so on...

Hence, the total becomes: $\sum_{n=0}^{10} \dbinom{10}{n}=1024$

Well, here's where the brilliant answer limitation comes in handy... As I'm too lazy to spend time after a time, if it were not on brilliant, I would have posted the answer as $1024$ :p... As $1024>999$ , I realized that there's something I'm missing... The mistake was to consider the subset and complement pair each with $6$ elements... If the number $i$ is in the subset, the number $(12-i)$ can't be in that set, and $(12-i)$ should be in the complement set, as we concluded... In this case, the subset has $6$ elements, hence it must have the number $6$ in it... But $(12-6)=6$ and so, the complement must also have the number $6$ in it, which is not possible, hence we should omit this case...

The answer becomes: $\left(\sum_{n=0}^{10} \dbinom{10}{n}\right) - \dbinom{10}{5}=1024-252=\fbox{772}$

Well, I tried to generalize the problem for $(1,2,3,...,n)$ set with $n$ elements...

If $n$ is even, then the number of subsets such that both the subset and it's complement are selfish is: $\left(\sum_{i=1}^{n} \dbinom{n-2}{i-1}\right) - \dbinom{n-2}{\frac{n-2}{2}}$

If $n$ is odd, then it's simply: $\sum_{i=1}^{n} \dbinom{n-2}{i-1}$

Please lemme know if anything is wrong with the generalization... I ain't quite sure... :-)

First, note the size cannot be 0 or 12, since 0 is not in the set.

Let the size of the subset be $n$ . Then, $n$ must be in the subset, and $12-n$ cannot be in the subset. Then, we must take $n-1$ more numbers to put into the subset, of the 10 remaining numbers. There are $\dbinom{10}{n-1}$ ways to do this. As $n$ ranges from 1 to 11, there are $\dbinom{10}{0}+\dbinom{10}{1}+\cdots+\dbinom{10}{10}=2^{10}=1024$ ways to pick a subset. However, notice that $n$ cannot be 6, as then 6 is both in the subset and its complement. Then, the answer is $1024-\dbinom{10}{5}=1024-252=\boxed{772}$

Motivation: I tried to casework initially, and realized how I could make subsets from the size.

Generalization:

If $n$ is even, there are $2^{n-2}-\dbinom{n-2}{\dfrac{n-2}{2}}$ If $n$ is odd, there are $2^{n-2}$

Notice that for the conditions of the question to be satisfied, the subset just needs to have the number of its size and not the number of the size of its complement. An example would be: The subset of size $3$ must have the number $3$ in it but not the number $12-3 = 9$ which is the size of the complement set.

Hence, leaving the $2$ numbers aside (the elements of the sizes of the subset and its complement), there will be $10$ other numbers which can be freely manipulated and put into either of the $2$ sets. Note that when subset has size $1$ , it must and only have $1$ in it. Thus, there is only $1$ way to do so. For subset of size $2$ , there must be the element $2$ and another element not $10$ . Thus, there are $10 \choose 1$ ways to choose the other element. For subset of size $3$ , there will be $10 \choose 2$ ways. And so on.

BUT note that there cannot be a subset of size $6$ as its complement will also be of a size $6$ . --- There is only $1$ element $6$ in the set of { $1,2,...,12$ }.

As such the answer is:

$2 \times$ $($ $10\choose 0$ $+$ $10\choose 1$ $+$ $10\choose 2$ $+$ $10\choose 3$ $+$ $10\choose 4$ $)=\boxed{772}$

We provide a constructive method of counting the number of subsets such that it and its complement are both selfish.

First off, the empty set is not selfish, because it does not contain the element $0$ in it. The complement of the subset $\{1,2,3,...,11,12\}$ is not selfish because it is the empty set.

Now, for $\forall k \in \mathbb{Z}^{+}, 1 \le k \le 11$ , we consider the subset with size $k$ , and the complement of that subset with size $12-k$ .

We must have $k$ in the subset with size $k$ , and $12-k$ in the subset with size $12-k$ . The problem boils down to how many ways we can choose the remaining $k-1$ elements in the former subset, as the rest will be fixed in the complement. How many ways can we do this? Well, we have already eliminated $k$ and $12-k$ from the elements we can choose, so there are $12-2 = 10$ elements left. Thus, there are $\dbinom{10}{k-1}$ ways to construct a subset with size $k$ . For $1 \le k \le 11$ , we have the sum $\dbinom{10}{0} + \dbinom{10}{1} + ... + \dbinom{10}{10}$

We can use the identity that $\dbinom{n}{0} + \dbinom{n}{1} + ... + \dbinom{n}{n} = 2^{n}$ to find that this sum is $1024$ . But wait, this is greater than $999$ , so what went wrong?

As it turns out, we missed that if $k=6$ , then the construction is impossible, as the subset and the complement can't both have a $6$ in it, so to get our final answer we must do $1024 - \dbinom{10}{5} = \boxed{772}$

Let $n$ be the size of a subset $S$ of $\{1,2,3,4,5,6,7,8,9,10,11,12\}$ . Clearly, $1\le n\le12$ . By symmetry, we are able to consider only $1\le n\le6$ and multiply by $2$ afterwards. If $n=6$ , then $6$ must be in $S$ and $12-6=6$ must also be in $S'$ , the compliment of $S$ , a contradiction. Hence, $1\le n\le5$ . If $n\in S$ and $12-n\in S'$ , then there are $10$ other numbers left. $n-1$ will be chosen to go into $S$ and the rest will go in $S'$ , so there are $\binom{10}{n-1}$ ways for each $n$ . This leads to a total of

$2(\binom{10}{0}+\binom{10}{1}+\binom{10}{2}+\binom{10}{3}+\binom{10}{4})=2^{10}-\binom{10}{5}=\boxed{772}$

combinations.

A subset of size 0, or the empty subset, does not contain 0, and so is not selfish. If a subset of size 6 is selfish, then its complement does not contain 6 and so is not selfish. Let S denotes a subset of size k, where 1 <= k <= 11 and k <> 6. If S and its complement are selfish, then k in S and 12-k not in S, and so there are 10C(k-1) such subsets. Summing for all possible k's, the answer is 10C0+10C1+10C2+...+10C5+10C7+10C8+...+10C10 = 10C0+10C1+...+10C10-10C6 = 2^10-10 9 8 7 6/(5 4 3*2) = 772.

A selfish subset will have the number of elements as one of its elements.

1. 1 as number of elements: Only one such subset i.e. $\{1\}$ . Its complement with 11 elements will also be selfish.
2. 2 as number of elements: The set will be $\{ \_,2\}$ . There will be 10 elements to choose from for the empty place since out of the 12 elements, '2' is in the subset and '10' is in the complement. So there are 10 choose 1 = 10 subsets.
3. 3 as number of elements: The set is $\{\_,\_,3\}$ . There are 10 elements and we choose 2. So there are 10 choose 3 = 45 subsets. So in general for element with n elements, there are '10 choose n-1' selfish subsets such that their complements are also selfish. However, this is not true for n = 0, 6 and 12. This is because in case of 0 elements, the selfish subset must contain 0 which is not possible. In case of 12, the complement set must be selfish but is cannot be selfish because it will have 0 elements and it cannot have 0 as an element. For n = 6, the subset and complement will both have 6 elements and for both of them to be selfish, they will both have to have 6 as their element which is not possible.

So the number of selfish subsets whose complement is also selfish = ${10 \choose 0} + {10 \choose 1} + {10 \choose 2}+{10 \choose 3}+{10 \choose 4}+{10 \choose 5}+{10 \choose 7}+{10 \choose 8}+{10 \choose 9}+{10 \choose 10} = \boxed{772}$ .

Let A a subset of S={1,2,...,12}. Let |A| the size of A then let B=S/A so |B| =12- |A| . Like 12 = 6+6 then |A| = |B| =6 so we don't have selfish subesets for this order. For |A| =a, we have $\binom{10}{a-1}$ subset with the propriety required.

For example if |A| =4 we have |B| =8 so A ={4, $a_{1}$ , $a_{2}$ , $a_{3}$ } , $a_{i}$ in S/{4,8} we must remove 4 in order to have |A| =4 and 8 in order to have B a selfish subset. So we can choose $a_{i}$ in $\binom{10}{3}$ ways. We can generalize (demonstrate) this case to any |A| =a with a=1,2,,,12 and a dinsint to 6.

So we have $\sum_{a=1}^{11} \binom{10}{a-1}$ - $\binom{10}{5}$ = $2^{10}$ -252 = $\boxed{772}$

For ex lets take first set containing 5, which then must contain 4 numbers, its complement will have 7 numbers, so its obvious that this set must have 7 in it. So now for the first set, it can have any 4 numbers except 5 and 7, so number of selection of 4 numbers except 5 and 7 from remaining 10 numbers, which is 10C4, do this for every case from 1,2,3,4,5,7,8,9,10 and 11. Remember we cannot consider set of 6, as its complement set wont have 6 so it can never satisfy given condition for any combination.