¿Tiene un conjunto ' tamaño s ser un número natural, y lo contrario cancelaría una solución?

Question

Se me ocurrió una manera de resolver este conteo problema que no está en mi libro de texto y me pregunto si todavía es válida porque en uno de los pasos intermedios para calcular el número de elementos de un subconjunto y con frecuencia tengo un no-entero como respuesta $9.5849\dots$

La pregunta es

¿Cuántos subconjuntos de a $S = \{1,2,....n\}$ contienen al menos uno de los elementos de la $\{1,2\}$ y al menos el $2$ de los elementos $\{3,4,5\}?$

Primero tengo el número de subconjuntos que tienen al menos uno de los elementos $\{1,2\}$ mediante el uso de la resta principio y por el uso de potencias de dos. Para cada elemento en el conjunto pido 'está presente en el set?", y hay dos opciones, sí o no. Por lo que el número total de subconjuntos es $2^{n}.$ Y, finalmente, yo uso la resta, ya que el número de subconjuntos con al menos un elemento de a $\{1,2\}$ es el mismo que el total menos el número de subconjuntos con nada de $\{1,2\}:$

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

A continuación, he intentado algo diferente. Traté de imaginar que yo estaba empezando el problema todo de nuevo pero esta vez con el juego original es más pequeño. Ahora

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

Me di cuenta de esto fue el sonido, porque si yo tenía 10 elemento tendría $2^{10} = 1024$ posibles subconjuntos y $log_{2}(1024)$ me da el número de elementos del conjunto que es $10.$

Ahora solo tengo la respuesta a la simple pregunta:

¿Cuántos subconjuntos de a $S = \{1,2,....k\},$ donde $k = log_{2}(m),$ contener, al menos, $2$ de los elementos $\{3,4,5\}?$

Y la respuesta a esto es

$4 * 2^{k-3}$

Me multiplicar por 4, porque hay $3$ formas de anexar $2$ o más de los elementos de $\{3,4,5\}$ a a $S$ que ha tenido $\{3,4,5\}$ quitado. Son $\{3,4\},\{3,5\},\{4,5\},\{3,4,5\}.$

Lo que me parece inusual acerca de este enfoque es que el $log_{2}(m)$ no es siempre un número entero. Y yo no puedo imaginar que va a través de cada elemento en un conjunto pidiendo a la pregunta " ¿está usted en el subconjunto? si uno de los elementos es sólo una fracción de un elemento como el $0.5849\dots$

Por ejemplo, si $n = 10,$

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

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

Se siente mal preguntar cuántos subconjuntos de un conjunto con $9.58\dots$ elementos.

Y, sin embargo, puedo obtener la respuesta correcta:

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

Answer 1

Lo que han descubierto es que la fórmula $2^n - 2^{n-2}$ tiene una extensión continua de los números naturales $n \in \{1,2,3,...\}$ a todos los números reales $x \in \mathbb{R}$; en otras palabras, la fórmula $2^x - 2^{x-2}$ tiene sentido, no importa lo que el valor de $x$.

Este es un importante descubrimiento. No es en absoluto evidente, a partir de una elemental (precálculo) punto de vista, que una función exponencial como $2^n$ puede ser extendido en forma continua a una función $2^x$, de modo que las leyes de los exponentes siguen siendo válidos, tales como las leyes de $2^x \cdot 2^y = 2^{x+y}$ y así sucesivamente. Se requiere de una o dos semestres de cálculo para probar esto de manera rigurosa, con un método que rigurosamente las construcciones de la función $2^x$ y demuestra sus propiedades.

Sin embargo, usted no debe sobre-interpretar este descubrimiento. Tienes razón en que no tiene sentido preguntar cuántos subconjuntos hay en el conjunto de con $9.58$ elementos, de modo que no es lo que su fórmula dice.

Answer 2

La razón esto funciona es que las dos condiciones de (i): al menos uno de $\{1,2\}$ y (ii): por lo menos dos de $\{3,4,5\}$, son independientes cuando $n\geq5$. La probabilidad de que (i) sea satisfecho es $3/2^2$, y la probabilidad de que (ii) está satisfecho es $4/2^3$. Sigue que ${3\over8}$ % todo $2^n$subconjuntos satisfacen ambas condiciones. Tomando logaritmos en la segunda etapa fue un desvío de la suya que Shannon podría haber gustado $\ldots$.