Matemáticas discretas: 20 ejemplos resueltos

Después de cualquier natural n aparece n + 1; no existe un último natural.

Podemos enumerarlos como 0, 1, 2, 3, …, aunque la lista no termine.

En la recta real, el intervalo (n − 1/2, n + 1/2) no contiene otro natural distinto de n.

Condición: Naturales con 0; distancia usual en la recta.

Los naturales son infinitos, pero sus puntos están aislados en la recta usual. No basta decir que un conjunto es enumerable para asegurar ese aislamiento: los racionales son enumerables y entre dos racionales distintos hay otro, su punto medio.

Valores mostrados posibles: 53,3; 53,4; 53,5; … km/h.

Si la lectura antes de redondear es 53,46 km/h, la pantalla muestra 53,5 km/h.

La diferencia entre dos valores consecutivos mostrados es 0,1 km/h.

Condición: Ejemplo didáctico; redondeo a la décima más cercana; fuera de empates.

La salida está cuantizada: utiliza escalones de tamaño fijo. La velocidad física puede modelarse con una variable real continua; la pantalla no cambia eso. Muestrear en instantes separados y redondear valores son dos operaciones distintas.

Un conteo de objetos individuales se expresa como entero no negativo.

Para especificarlo hay que fijar qué se cuenta, la región o muestra y el instante.

Una estimación del total puede escribirse de forma aproximada; eso no transforma el conteo subyacente en una variable continua.

Condición: Modelo de conteo; criterio de pertenencia e instante fijados.

La dificultad de obtener el total exacto no cambia la naturaleza del conteo. No debe confundirse un conjunto de objetos contables con el volumen, la masa o la luminosidad que también podríamos medir.

Por posición hay 2 opciones. Total: 2 × 2 × 2 × 2 × 2 = 2⁵ = 32 cadenas.

Se incluyen 00000 y las cadenas que empiezan por 0.

Por ejemplo, 00101 representa 0 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 1 = 5 en binario sin signo.

Condición: Cinco bits; repetición permitida; codificación sin signo en el ejemplo numérico.

El resultado cuenta cadenas, no solo números escritos sin ceros iniciales. La interpretación sin signo permite representar del 0 al 31. Con otra codificación, las mismas cadenas pueden tener otros significados.

Opciones de música: 3. Opciones de dibujo: 5.

Como las listas no se solapan y se elige de una sola, hay 3 + 5 = 8 opciones.

Condición: Listas disjuntas; elección de exactamente un taller.

Sumar exige alternativas disjuntas. Si un mismo taller figurara en ambas listas, habría que descontar ese solapamiento.

Por cada camiseta hay 2 elecciones de pantalón.

Total: 3 × 2 = 6 combinaciones.

Condición: Todas las combinaciones permitidas; una prenda de cada tipo.

Se multiplica porque se elige una opción de cada grupo. Si hubiera combinaciones prohibidas, el producto contaría de más y habría que ajustar el modelo.

Para coordinación hay 4 opciones; después quedan 3 para secretaría y 2 para tesorería.

Total: 4 × 3 × 2 = 24 asignaciones.

Intercambiar coordinación y secretaría entre dos personas produce otra asignación.

Condición: Cuatro personas; tres cargos distintos; sin repetir persona.

Es una selección ordenada sin repetición. No se divide entre 3!, porque los cargos son diferentes.

Si ordenamos la elección contamos 4 × 3 = 12 parejas.

Cada equipo aparece dos veces: Ana–Bea y Bea–Ana, por ejemplo.

Equipos distintos: 12 / 2 = 6.

Condición: Cuatro personas distintas; equipos sin repetición ni cargos.

Dividimos por 2 porque cada equipo tiene exactamente dos órdenes. La tabla enumera los seis equipos y permite contrastar el cálculo.

Al sumar 12 + 9 = 21 se cuenta dos veces a las 4 personas de la intersección.

Estudian al menos una: 12 + 9 − 4 = 17.

Solo inglés: 12 − 4 = 8. Solo francés: 9 − 4 = 5. Ambas: 4.

Comprobación: 8 + 5 + 4 = 17.

Condición: Datos ficticios; dos conjuntos dentro del mismo grupo.

No podemos calcular cuántas no estudian ninguna sin conocer el tamaño total del grupo. «Al menos una» incluye a quienes estudian ambas.

A × B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}.

Número de pares: |A × B| = 2 × 3 = 6.

(1,x) pertenece a A × B; (x,1) pertenece a B × A, no a A × B.

Condición: A y B tal como se definen; pares ordenados.

Una relación de A en B puede elegirse como un subconjunto de A × B. El conjunto de pares posibles y una relación concreta no son lo mismo.

R = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)}.

Reflexiva: cada a cumple a ≤ a.

No simétrica: 1 ≤ 2, pero no 2 ≤ 1.

Antisimétrica: si a ≤ b y b ≤ a, entonces a = b.

Transitiva: si a ≤ b y b ≤ c, entonces a ≤ c.

Condición: Relación ≤ restringida a {1,2,3}.

Las propiedades se atribuyen a R sobre A. «Antisimétrica» no significa simplemente «no simétrica»: permite relaciones en ambos sentidos cuando los elementos son iguales.

Clase par: {0,2}. Clase impar: {1,3}.

Pares de la relación: (0,0), (0,2), (2,0), (2,2), (1,1), (1,3), (3,1), (3,3).

Es reflexiva, simétrica y transitiva: es una relación de equivalencia.

No es antisimétrica: 0 se relaciona con 2 y 2 con 0, aunque 0 ≠ 2.

Condición: Relación de misma paridad en {0,1,2,3}.

La transitividad se comprueba porque, si a tiene la paridad de b y b la de c, a tiene la de c. Las clases separan B en grupos disjuntos que cubren todos sus elementos.

Vértices: 5. Aristas: 5.

Grados: A tiene 2, B tiene 2, C tiene 2, D tiene 3 y E tiene 1.

Suma de grados: 2 + 2 + 2 + 3 + 1 = 10 = 2 × 5.

Cada arista aporta un extremo a cada uno de sus dos vértices.

Condición: Grafo simple no dirigido; sin bucles; cada enlace con el mismo coste.

El dibujo representa conectividad, no distancias físicas. No hay enlace directo A–D, aunque sí existen caminos entre ellos. Cada enlace puede recorrerse en ambos sentidos en este modelo.

Inicio: marcar A y ponerlo en la cola.

Repetir: retirar el primero, revisar sus vecinos en orden alfabético y marcar y encolar solo los que aún no fueron descubiertos.

Capas desde A: {A}, después {B,C}, después {D} y finalmente {E}.

Al descubrir D desde B y E desde D, reconstruimos A–B–D–E: 3 enlaces.

A–C–D–E también tiene 3 enlaces. No existe un camino de menos enlaces entre A y E.

Condición: Grafo del ejemplo 13; enlaces no ponderados; vecinos en orden alfabético.

BFS descubre por capas de distancia en número de enlaces. Al marcar al encolar, D no entra dos veces y los ciclos no provocan un recorrido infinito. En un grafo finito se procesa cada vértice alcanzable una vez. El camino mínimo en enlaces no tiene por qué minimizar tiempos si las aristas tuvieran costes diferentes.

Desde A siguen alcanzándose exactamente A, B, C, D y E.

F no aparece entre los descubiertos cuando se vacía la cola.

La red tiene dos componentes: {A,B,C,D,E} y {F}.

Por tanto, en este modelo no existe camino de A a F.

Condición: Misma red y F aislado; grafo finito conocido.

La ausencia de conexión se concluye tras agotar los vértices alcanzables, no por detenerse después de unos pasos arbitrarios. Es un análisis del grafo dado; no equivale a una prueba de conectividad real entre dispositivos.

Dependencias: A → B, A → C, B → D, C → D y D → E.

Un orden válido es A, B, C, D, E. Otro es A, C, B, D, E.

D necesita que B y C hayan terminado; E necesita D.

Si añadimos E → A, aparece un ciclo A → B → D → E → A y no existe un orden que respete todas las dependencias estrictas.

Condición: Cada flecha exige terminar antes de empezar la tarea siguiente.

La dirección forma parte del modelo. Los dos órdenes indicados son los únicos para estas cinco tareas: A debe ir primero, E último y solo B y C pueden intercambiarse.

48 = 2 × 18 + 12. Sustituimos (48,18) por (18,12).

18 = 1 × 12 + 6. Sustituimos (18,12) por (12,6).

12 = 2 × 6 + 0. El último divisor no nulo es 6.

Resultado: mcd(48,18) = 6.

Condición: Entradas enteras positivas; división con resto euclídeo.

Los divisores comunes de a y b son los mismos que los de b y a − qb. Así se conserva el mcd. El resto es no negativo y menor que el divisor, por lo que la sucesión de restos positivos desciende y termina. Un programa con un bucle indefinido no queda justificado solo por llamarse algoritmo.

Diez días después: 3 + 10 = 13.

13 = 1 × 7 + 6, así que 13 mod 7 = 6.

El índice 6 corresponde a domingo.

Condición: Ciclo semanal de siete días; lunes con índice 0.

El residuo identifica el día dentro de un ciclo de siete. Se suman diez días transcurridos; no se cuenta hoy como el primer día del avance.

Regla de cifrado: y = (x + 3) mod 26.

CASA tiene índices 2, 0, 18, 0. Pasan a 5, 3, 21, 3.

Mensaje cifrado: FDVD.

Para recuperar: x = (y − 3) mod 26. FDVD vuelve a CASA.

Condición: Alfabeto didáctico A–Z de 26 letras; desplazamiento fijo +3.

La operación es reversible porque restar 3 deshace la suma módulo 26. Este cifrado histórico sirve para explicar residuos y codificación; no ofrece seguridad moderna.

Para n ≥ 2, el último paso fue de uno o de dos: f(n) = f(n − 1) + f(n − 2).

Bases: f(0) = 1 y f(1) = 1.

f(2) = 2, f(3) = 3 y f(4) = 5.

Las cinco secuencias son: 1–1–1–1; 1–1–2; 1–2–1; 2–1–1; 2–2.

Condición: Pasos de 1 o 2; orden relevante; sin sobrepasar el destino.

Las dos familias del último paso no se solapan y cubren todas las posibilidades. La secuencia vacía aporta una manera de subir cero peldaños y permite mantener la recurrencia desde n = 2.

Condición: Supuestos indicados en el enunciado.

Antes de calcular, identifica el objeto: cadenas, equipos, relaciones, caminos o secuencias. Una misma cifra puede requerir modelos distintos.

1. ¿Se cuentan objetos, se ordenan elecciones o se mide una magnitud?

2. ¿Importan el orden y la repetición? ¿Hay alternativas que se solapan?

3. Si hay relaciones, ¿cuál es el conjunto base y qué pares pertenecen a la relación?

4. Si hay una red, ¿las aristas tienen dirección o pesos?

5. Si hay un algoritmo, ¿qué conserva cada paso y por qué termina?

6. Comprueba el resultado con una enumeración pequeña, una operación inversa o una propiedad del modelo.

Condición: Supuestos indicados en el enunciado.

Las matemáticas discretas estudian, entre otras cosas, estructuras de conteo, grafos, relaciones y algoritmos. No se definen por que sus elementos sean «más claros» que los de un continuo, ni excluyen usar límites para estudiar sucesiones o costes de algoritmos.