6.1: El Teorema Fundamental

Comenzamos con una regla básica que va por el audaz nombre de El teorema fundamental del conteo. ¹ Va así:

Ejemplo: Jane está ordenando un Lamborghini nuevo. Tiene doce colores de pintura diferentes para elegir (incluyendo Luscious Red y Sassy Yellow), tres interiores diferentes (Premium Leather, Bonded Leather o Vinyl) y tres sistemas estéreo diferentes. También debe elegir entre transmisión automática y manual, y puede obtener cerraduras eléctricas y ventanas (o no). ¿Cuántas configuraciones diferentes tiene que elegir Jane? Dicho de otra manera, ¿cuántos tipos diferentes de autos podrían salirse de la línea para ella?

La clave es que cada una de sus elecciones es independiente de todas las demás. Elegir un exterior de Envious Green no limita su elección de transmisión, estéreo o cualquier otra cosa. Entonces, no importa cuál de los 12 colores de pintura elija, puede elegir independientemente cualquiera de los tres interiores, y no importa cuáles sean estas dos primeras opciones, puede elegir libremente cualquiera de los estéreos, etc. Es una mezcla y combinación. Por lo tanto la respuesta es:

\[12 \times 3 \times 3 \times 2 \times 2 = 432\ \text{choices}.\]

Aquí hay una notación alternativa con la que te encontrarás para esto, por cierto:

\[\prod_{i=1}^k{n_i}\]que es solo una forma más corta de escribir\[n_1 \times n_2 \times n_3 \times \cdots \times n_k.\]

Como se menciona en la sección 5, la\(\Sigma\) notación es esencialmente un bucle con un contador, y dice sumar la expresión a la derecha de la misma para cada valor del contador. La\(\Pi\) notación es exactamente la misma, solo que en lugar de sumar las expresiones juntas para cada valor del contador, las estamos multiplicando. (La razón por la que los matemáticos eligieron los símbolos\(\Sigma\)\(\Pi\) (sigma) y (pi) para esto, por cierto, es que “sigma” y “pi” comienzan con la misma letra que “suma” y “producto”, respectivamente).

De hecho, podemos obtener mucho apalancamiento solo con el teorema fundamental. ¿Cuántos PIN diferentes son posibles para una tarjeta ATM? Hay cuatro dígitos, cada uno de los cuales puede ser cualquier valor de 0 a 9 (diez valores totales), por lo que la respuesta es:

\[10 \times 10 \times 10 \times 10 = 10,000\ \text{different PINs}.\]

Entonces un ladrón en un cajero automático ingresando frenéticamente PIN al azar (con la esperanza de romper su cuenta antes de llamar y detener su tarjeta de débito) tendría que probar alrededor de 5,000 de ellos en promedio antes de descodificar el código.

¿Qué pasa con los matones de secundaria que están tratando de entrar en tu casillero? Bueno, la mayoría de las cerraduras de combinación se abren mediante una secuencia de tres números, cada número de los cuales es cualquier cosa de 0 a 39. Entonces hay:

\[40 \times 40 \times 40 = 64,000\ \text{different combinations}.\]

Eso probablemente sea un poco exagerado, ya que apuesto a que no se permiten números repetidos consecutivos (el Maestro probablemente no fabrica un candado con una combinación de 17—17—23, por ejemplo). Pero sí parece al menos tan seguro como un número PIN.

Cada automóvil en el estado de Virginia debe recibir su propio número de placa. Eso es un montón de autos. ¿Cuántas combinaciones diferentes de matrículas hay disponibles?

Este requiere un poco más de reflexión, ya que no todos los números de licencias tienen el mismo número de caracteres. Además de “SED4756" y “PXY1927" también se puede tener “DAWG" o “LUVME" o incluso “U2”. ¿Cómo podemos incorporarlos?

El truco es dividir nuestro conjunto en subconjuntos mutuamente excluyentes, y luego sumar las cardinalidades de los subconjuntos. Si solo caben 7 caracteres en una placa, entonces claramente cada número de placa tiene 1, 2, 3, 4, 5, 6 o 7 caracteres. Y ninguna placa tiene dos de estos (es decir, no hay placa que tenga tanto 5 caracteres de largo como 6 caracteres de largo). Por lo tanto, son subconjuntos mutuamente excluyentes y seguros de agregar. Este último punto muchas veces no se aprecia del todo, lo que lleva a errores. ¡Ten cuidado de no sumar con caballerosidad las cardinalidades de los conjuntos no mutuamente exclusivos! Terminarás contabilizando artículos dobles.

Entonces sabemos que el número de placas posibles es igual a:

el # de placas de 7 caracteres +
el # de placas de 6 caracteres +
el # de placas de 5 caracteres +
\(\cdots\) +
el # de placas de 1 carácter.

Muy bien. Ahora podemos averiguar cada uno por separado. ¿Cómo sabemos cuántas placas de 7 caracteres hay? Bueno, si cada carácter debe ser una letra o un dígito, entonces tenemos 26 + 10 = 36 opciones para cada carácter. Esto implica\(36^7\) diferentes placas posibles de 7 caracteres. Por lo tanto, el número total de placas es:\[36^7 + 36^6 + 36^5 + 36^4 + 36^3 + 36^2 + 36 = \text{80,603,140,212 plates}\]

que es como diez veces la población de la tierra, así que creo que estamos a salvo por ahora.

Aquí tienes un interesante experimento de pensamiento para poner a prueba tu intuición sobre los números. Mira el cálculo anterior, y pregúntate: “¿y si el estado de Virginia decidiera, por razones de consistencia, que todas las placas tenían que tener los 7 caracteres completos? ¿Eso reduciría significativamente el número total de placas posibles?” Mi primera inclinación sería decir “sí”, porque estamos agregando siete cosas en esa ecuación, y si exigimos placas de 7 caracteres para todos eliminaríamos 6 de los 7. ¡Seguramente estaríamos en peligro de quedarnos sin placas para dar a todos los autos! Pero de hecho el nuevo número total de placas resultaría ser:\[36^7 = \text{78,364,164,096 plates}.\]

Guau. Apenas hemos perdido nada desguazando todas las placas de menos de 7 caracteres. Resulta que en comparación con las placas de 7 caracteres, todas las demás longitudes fueron una gota en el cubo. Esta es una poderosa ilustración del crecimiento exponencial. Cuando modificas el exponente, pasando de algo así como\(36^6\) a\(36^7\), te haces astronómicamente más grande muy, muy rápidamente. Esto es algo bueno saber cuando lo único que quieres es una aproximación de alguna cantidad. ¿Cuántas contraseñas son posibles en un sistema que exige 6-10 caracteres por contraseña? Bueno, prácticamente puedes ignorar todas las contraseñas de 6-9 caracteres y simplemente contar las contraseñas de 10 caracteres, porque hay muchas más de esas.

Un último retoque al ejemplo de matrícula antes de seguir adelante. Supongamos (de nuevo, en aras de la consistencia) que Virginia proscribió los platos personalizados y les dio a todos un plato de 7 caracteres generado aleatoriamente. Además, los últimos cuatro caracteres del plato tenían que ser dígitos en lugar de letras, por lo que algo así como “” sería imposible. Ahora, ¿cuántas placas posibles habría?

En este caso, no cada una de las\(k\) partes de\(n\) tiene igual número de opciones. \(n_1\)a través\(n_3\) siguen siendo 36, pero ahora\(n_4\) a través\(n_7\) son solo 10. Entonces esto nos da:\[36 \times 36 \times 36 \times 10 \times 10 \times 10 \times 10 =\ \text{466,560,000 plates}\]

o sólo alrededor de .006 veces más que antes. Mejor apegarse con caracteres alfanuméricos para las siete posiciones.

Un truco sencillo

A veces tenemos algo difícil de contar, pero podemos darle la vuelta en términos de algo mucho más fácil. A menudo esto implica contar el complemento de algo, luego restar del total.

Por ejemplo, supongamos que un determinado sitio web exige que las contraseñas de usuario tengan entre 6 y 10 caracteres de longitud, siendo cada carácter una letra mayúscula, minúscula, dígito o carácter especial (*, #, @,% o &), pero también requiere cada contraseña tenga al menos un dígito o carácter especial. ¿Cuántas contraseñas son posibles?

Sin la parte de “al menos un dígito o carácter especial”, es bastante fácil: hay 26 + 26 + 10 + 5 = 67 opciones diferentes para cada personaje, así que tenemos\[67^{10} + 67^9 + 67^8 + 67^7 + 67^6 = \text{1,850,456,557,795,600,384 strings}.\]

Pero, ¿cómo manejamos la parte de “al menos una”?

Una forma sería enumerar todas las formas posibles de tener una contraseña con al menos un carácter no alfa. El no-alfa podría aparecer en la primera posición, o la segunda, o la tercera\(\dots\), o la décima, pero claro esto solo funciona para contraseñas de 10 dígitos, y en cualquier caso no es como los otros caracteres tampoco podrían ser no alfa. Se pone desordenado muy rápido.

Sin embargo, hay un truco simple, una vez que te das cuenta de que es fácil contar las contraseñas que no satisfacen la restricción adicional. Hazte esta pregunta: de todas las cadenas posibles de 6-10 caracteres, ¿cuántas de ellas no tienen al menos un carácter no alfa? (¿y por lo tanto son ilegales, de acuerdo con las reglas del sitio web?)

Resulta que eso es lo mismo que preguntar “¿cuántas cadenas hay con 6-10 caracteres alfabéticos (solo)?” que es, por supuesto:\[52^{10} + 52^9 + 52^8 + 52^7 + 52^6 = \text{147,389,519,403,536,384 (illegal) passwords}.\]

Ahora, todo lo que tenemos que hacer es restar para obtener contraseñas\[\begin{aligned} \text{total # of strings -- # of illegal passwords} & = \text{# of legitimate passwords} \\ \text{1,850,456,557,795,600,384 -- 147,389,519,403,536,384} &= \text{1,708,735,865,301,022,720}\end{aligned}\] legítimas. Parece que no perdemos mucho al requerir el carácter no alfa.

La lección aprendida es que si contar los elementos en algún conjunto implica dar cuenta de muchos escenarios pegajosos diferentes, vale la pena intentar contar los elementos que no están en el conjunto en su lugar, y ver si eso es más fácil.

---

1. ¿Cuántos otros “Teoremas Fundamentales” de las matemáticas conoces? Aquí hay algunos: el Teorema Fundamental de la Aritmética dice que cualquier número natural se puede descomponer en sus factores primos de una sola manera. El Teorema Fundamental del Álgebra dice que el mayor poder de un polinomio es cuántas raíces (ceros) tiene. El Teorema Fundamental del Álgebra Lineal dice que el espacio de fila y el espacio de columna de una matriz tienen la misma dimensión. El Teorema Fundamental del Cálculo dice que la integración y diferenciación son la inversa entre sí.