Matemática discreta resuelta: combinatoria, inducción y congruencias

Matemática discreta es contar bien, demostrar bien y hacer cuentas con restos. Parece fácil… hasta que el enunciado dice “sin repetir” o “importa el orden”. ¡Vamos con calma!

1Combinatoria: ¿importa el orden?

En un grupo de 10 estudiantes, ¿de cuántas formas se puede elegir (a) una comisión de 3 personas y (b) un presidente, un secretario y un tesorero?

Paso 1 · Pregunta clave

(a) En una comisión el orden no importa → combinaciones. (b) Los cargos son distintos, el orden sí importa → variaciones.

Paso 2 · Combinaciones

$$\binom{10}{3}=\frac{10\cdot9\cdot8}{3!}=\frac{720}{6}=120$$

Paso 3 · Variaciones

$$V_{10,3}=10\cdot9\cdot8=720$$

Cada comisión se puede ordenar de $3!=6$ formas: $120\cdot6=720$. ✔

Ojo en el examen: antes de aplicar fórmulas, pregúntate “¿si cambio el orden, es otra solución distinta?”. Si sí, variaciones; si no, combinaciones.

2Inducción matemática

Demuestra que para todo $n\ge1$: $$1+2+\cdots+n=\frac{n(n+1)}{2}$$

Paso 1 · Caso base

Para $n=1$: izquierda $1$, derecha $\frac{1\cdot2}{2}=1$. ✔

Paso 2 · Hipótesis de inducción

Suponemos que es cierto para $n=k$: $1+\cdots+k=\frac{k(k+1)}{2}$.

Paso 3 · Paso inductivo

$$1+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$$

Es justo la fórmula con $n=k+1$.

Paso 4 · Conclusión

Por el principio de inducción, la fórmula vale para todo $n\ge1$. ∎

3Congruencias: restos de potencias enormes

Calcula el resto de dividir $7^{100}$ entre 5.

Paso 1 · Reducimos la base

$$7\equiv 2\pmod 5\ \Rightarrow\ 7^{100}\equiv 2^{100}\pmod 5$$

Paso 2 · Buscamos el ciclo

$2^1\equiv2,\ 2^2\equiv4,\ 2^3\equiv3,\ 2^4=16\equiv1\pmod5$. Se repite cada 4.

Paso 3 · Concluimos

$$2^{100}=(2^4)^{25}\equiv1^{25}=1\pmod5$$

El resto es 1.

Truco: con potencias grandes busca siempre la potencia que da resto 1 (el pequeño teorema de Fermat te la garantiza: $a^{p-1}\equiv1$ si $p$ es primo y no divide a $a$).

?Mini-quiz: ¿lo has pillado?

1. $\binom{5}{2}$ vale…

2. El resto de $3^4$ entre 7 es…

3. ¿Cuántos anagramas distintos tiene la palabra CASA?

¡Buen trabajo! Hay mucho más en camino.

Apúntate y te avisamos cuando abra el curso completo.

Únete a la lista de espera