3
$\begingroup$

Question :

Find the number of subsets (say) $A$ of $X = $ { $1,11,21,31,41,..., 551 $ } such that no two elements in the subset sum to $552$.

My attempt :

I divided the original set $X$ into two parts (or subsets, say $P,Q$) each containing $28$ elements. ( i.e containing first half of the element and other part containing other half of the set.)

Now,Each of the sets $P,Q$ would have $\displaystyle 2^{28}$ total subsets. Thus in all, $2^{29}$.

Now, for each element in $P$ there would be an element corresponding to the element in $Q$.

Thus it is a bijective function $f:P \rightarrow Q$.

Now we are left with $27$ elements in $P$ that do not correspond to a element in $Q.$

So there would be $\displaystyle 2 \times {28 \choose 1} \times \sum_{k=0}^{27} {27 \choose k}$ subsets.

And then considering that set $A$ can have one element at least we need to add $56$ to the total number of subsets to get the set $A.$

Total number of subets $A$ of $X$ will be $$\displaystyle \ 2^{29} + 2 \times {28 \choose 1} \times \sum_{k=0}^{27} {27 \choose k} + 56 = 8,053,063,736.$$

Please verify it.

$\endgroup$
2
  • $\begingroup$ If I am not wrong then, is $\displaystyle \sum_{k=0}^{27} {27 \choose k} = 2^{27}.$ $\endgroup$
    – Nikola Alfredi
    Mar 4, 2020 at 19:22
  • 1
    $\begingroup$ Commenting on your attempt, your count appears to only consider outcomes where all elements come from $P$ or all elements come from $Q$, or one element comes from $P$ and any number from $Q$ or vice versa. You have missed cases where, say, ten elements from $P$ occur as well as $15$ from $Q$ but the numbers were such that no pair added to $552$. I don't follow where the $+56$ comes from, and you have overcounted scenarios involving the empty set numerous times. $\endgroup$
    – JMoravitz
    Mar 4, 2020 at 19:34

2 Answers 2

Reset to default
4
$\begingroup$

You are correct that $\sum\limits_{k=0}^{27}\binom{27}{k}=2^{27}$. Now... as for your original question, I like your idea to partition your set into the "big" numbers and the "little" numbers, noting that for each little number there is one big number such that they add to $552$, for instance $1+551$ or $11+541$ or $21+531$ etc...

Perhaps easier to visualize for the final answer however is to partition it into the $28$ sets $\{1,551\},\{11,541\},\{21,531\},\dots$

Now... in constructing a valid subset, for each of the $28$ subsets in the partition choose whether you wish to include the smaller number, the larger number, or neither. For each of these subsets in the partition we have three choices and for each unique sequence of choices we get a unique final resulting subset fitting our requirements.

We have then applying multiplication principle a.k.a. the rule of product, that there are a final total of:

$$3^{28} = 22,\!876,\!792,\!454,\!961$$

Note: this does include the empty set and the single-element sets in the overall count. Depending on preference, these might be removed from the count if so desired.

$\endgroup$
7
  • $\begingroup$ How do we have three choices for each of the $28$ partitions ? $\endgroup$
    – Nikola Alfredi
    Mar 4, 2020 at 19:34
  • $\begingroup$ @NikolaAlfredi pick the smaller number, pick the larger number, or pick neither. $\endgroup$
    – JMoravitz
    Mar 4, 2020 at 19:35
  • $\begingroup$ Please give an example for picking "neither" wouldn't it be empty ? I didn't get it. $\endgroup$
    – Nikola Alfredi
    Mar 4, 2020 at 19:37
  • 2
    $\begingroup$ Letting $2$ represent picking the larger, $1$ the smaller, and $0$ neither, the sequence of choices $21210010000\dots 0$ corresponds to having picked $551$ from the first part, $11$ from the second, $531$ from the third, $31$ from the fourth, neither from the fifth, neither from the sixth, and $61$ from the seventh and neither from any of the remaining, resulting in the final combined result of $\{551\}\cup\{11\}\cup\{531\}\cup\{31\}\cup\emptyset\cup\emptyset\cup\{61\}\cup \emptyset \cup \dots = \{11,31,61,531,551\}$ $\endgroup$
    – JMoravitz
    Mar 4, 2020 at 19:40
  • $\begingroup$ Picking neither from any of the parts in the partition does indeed result in the empty set $\{\}$ which satisfies the condition that it is a subset of your original set such that no two of the (nonexistant) elements in it add up to $552$. $\endgroup$
    – JMoravitz
    Mar 4, 2020 at 19:41
3
$\begingroup$

In each of the $28$ pairs $(i, 552-i)$, $i = 1, 11, 21, \ldots, 271$, you can have either $0$ or $1$ member (which can be either member of the pair). So there are $3^{28}$ possibilities.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .