6
$\begingroup$

I came up with a way of solving this counting problem that's not in my textbook and I am wondering if it is still valid because in one of the intermediate steps I calculate the number of elements in a subset and I often get a non-integer answer like $9.5849\dots$

The questions is

How many subsets of $S = \{1,2,....n\}$ contain at least one of the elements $\{1,2\}$ and at least $2$ of the elements $\{3,4,5\}?$

First I got the number of subsets which have at least one of the elements $\{1,2\}$ by using the subtraction principle and by using powers of two. For each element in the set I ask 'is this in the set?' and there are two options, yes or no. So the total number of subsets is $2^{n}.$ And finally I use subtraction because the number of subsets with at least one element from $\{1,2\}$ is the same as the total minus the number of subsets with nothing from $\{1,2\}:$

$$m = 2^{n} - 2^{n-2}$$

Next, I tried something different. I tried to imagine that I was starting the problem all over again but this time the original set is smaller. Now

$S = \{1,2....k\}$ where $k = log_{2}(m)$

I figured this was sound because if I had 10 element I would have $2^{10} = 1024$ possible subsets and $log_{2}(1024)$ gives me the number of elements in the set which is $10.$

Now I just have answer the simpler question:

How many subsets of $S = \{1,2,....k\},$ where $k = log_{2}(m),$ contain at least $2$ of the elements $\{3,4,5\}?$

And the answer to this is

$4 * 2^{k-3}$

I multiply by 4 because there are $3$ ways of of appending $2$ or more elements from $\{3,4,5\}$ back into to $S$ which has had $\{3,4,5\}$ taken away from it. They are $\{3,4\},\{3,5\},\{4,5\},\{3,4,5\}.$

What I find unusual about this approach is that the $log_{2}(m)$ is not always an integer. And I can't imagine going through each item in a set asking the question 'are you in the subset? if one of the elements is only a fraction of an element like $0.5849\dots$

For example, if $n = 10,$ then

$m = 2^{10} - 2^{8} = 768.$ Then

$k = log_{2}(m) = 9.584962\dots$

It feels wrong to ask how many subsets are in a set with $9.58\dots$ elements.

And yet I get the correct answer:

$4 * 2^{9.5849... - 3} = 384$ exactly!

$\endgroup$
  • $\begingroup$ could be some use of average cardinality in the s=geometric mean sense. $\endgroup$ – user451844 Jul 29 '17 at 14:54
12
$\begingroup$

What you have discovered is that the formula $2^n - 2^{n-2}$ has a continuous extension from the natural numbers $n \in \{1,2,3,...\}$ to all real numbers $x \in \mathbb{R}$; in other words, the formula $2^x - 2^{x-2}$ makes sense no matter what the value of $x$.

This is a significant discovery. It is not at all obvious, from an elementary (precalculus) point of view, that an exponential function like $2^n$ can be extended in a continuous fashion to a function $2^x$ so that the laws of exponents remain valid, laws such as $2^x \cdot 2^y = 2^{x+y}$ and so on. It requires a semester or two of calculus to prove this rigorously, by a method which rigorously constructs the function $2^x$ and proves its properties.

However, you should not over-interpret this discovery. You are right that it makes no sense to ask how many subsets there are in the set with $9.58$ elements, so that is not what your formula says.

$\endgroup$
  • $\begingroup$ Perhaps it makes more sense to think about it like this. If I have 9.58 bits and I remove three bits {3,4,5} and then add two bits {4 = 2^2}. Then I have 8.58 bits. And 2^8.58... is 384 meaning that i can store 384 pieces of information with 8.58.. bits! Got that idea from @ChristianBlatter below who mentioned Shannon below. $\endgroup$ – COOLBEANS Jul 29 '17 at 16:57
  • $\begingroup$ Why do you think this shows that $2^n - 2^{n-2}$ has a continuous extension from the natural numbers $n$ to all real numbers? It is not $n$ that has a non-integer number, but the number of elements, $k$, in the imagined set $S=\{1,2,...,k\}$. $\endgroup$ – HelloGoodbye Jul 29 '17 at 18:26
  • $\begingroup$ The original question switches from $S=\{1,2,...,n\}$ earlier to $S=\{1,2,...,k\}$ later, I was just using the earlier notation. $\endgroup$ – Lee Mosher Jul 29 '17 at 18:30
2
$\begingroup$

The reason this works is that the two conditions (i): at least one from $\{1,2\}$, and (ii): at least two from $\{3,4,5\}$, are independent when $n\geq5$. The probability that (i) is satisfied is $3/2^2$, and the probability that (ii) is satisfied is $4/2^3$. It follows that ${3\over8}$ of all $2^n$ subsets satisfy both conditions. Taking logarithms at the second step was a detour of yours that Shannon might have liked $\ldots$.

$\endgroup$
  • $\begingroup$ A completely different perspective I didn't appreciate. Thanks. Was Shannon fond of detours or taking logs of things, or both? I'm curious. $\endgroup$ – COOLBEANS Jul 29 '17 at 15:20
  • 1
    $\begingroup$ Shannon was the father of information theory. Here $N$ equiprobable outcomes incorporate $\log_2 N$ bits of information. $\endgroup$ – Christian Blatter Jul 29 '17 at 15:26
  • $\begingroup$ This is interesting to me as a programmer. 5 equally likely outcomes are equal to log base 2 (5) = 2.3219.. bits of information. So even though information must be physically stored on an integer number of registers, they can hold a non-integer value of information. That interesting to me for some reason. $\endgroup$ – COOLBEANS Jul 29 '17 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.