GUÍA DE ESTUDIO · 3 LABORATORIOS INTERACTIVOS · UNOS 12 MIN

Una baraja bien mezclada está casi con seguridad en un orden que nadie ha tenido nunca en la mano.

Hay 52! formas de ordenar una baraja: un número de 68 cifras, muchísimos más que los segundos transcurridos desde el Big Bang. La matemática discreta trata de cosas que se pueden contar una a una: ordenaciones, redes, afirmaciones verdaderas o falsas. Son las matemáticas con las que funcionan de verdad los ordenadores.

LO RÁPIDO QUE CRECEN LOS FACTORIALES
5!120formas de poner en fila a 5 personas
10!3.628.800formas de ordenar 10 libros
13!6.227.020.800más que la población de la Tierra
20!2,43 × 10^18más que los granos de arena de todas las playas (est.)
52!8,07 × 10^67ordenaciones de una baraja

¿Qué es la matemática discreta?

La matemática discreta estudia estructuras formadas por piezas separadas y contables en lugar de cantidades continuas: números enteros, conjuntos, afirmaciones lógicas, grafos (redes de puntos y enlaces) y formas de contar ordenaciones.

El cálculo se pregunta cómo cambian las cosas de forma continua; la matemática discreta se pregunta cuántas, cuáles y si es siquiera posible. Está en la base de los algoritmos, la criptografía, las bases de datos, el enrutamiento de redes y toda demostración de que un programa es correcto.

Teoría de grafosRedes de puntos y enlaces: mapas, redes sociales, la web.
CombinatoriaContar ordenaciones y selecciones.
LógicaRazonamiento de verdadero/falso, la base de los circuitos y las demostraciones.
Teoría de númerosPrimos y restos: las matemáticas del cifrado.
LABORATORIO 1 · TEORÍA DE GRAFOS

Cruza cada puente exactamente una vez

Haz clic en una zona de tierra para empezar y luego en los puentes para cruzarlos. No puedes repetir un puente. En 1736 Euler demostró cuándo es posible: solo hay ruta si cero o dos zonas de tierra tocan un número impar de puentes.

Ngrado 3Sgrado 3Igrado 5Egrado 3
0 / 7puentes cruzados
4zonas de tierra con grado impar
TU RUTAHaz clic en una zona de tierra para empezar
Este mapa tiene 4 zonas de tierra con un número impar de puentes. La regla de Euler dice que son demasiadas. ¡Inténtalo igualmente!
LABORATORIO 2 · CONTEO

¿Importa el orden? Lo cambia todo

Elige k elementos de n. Si el orden importa (un podio, un PIN), es una variación. Si no importa (una mano de cartas, un comité), es una combinación: divide entre las k! ordenaciones de cada grupo.

Oro, plata y bronce entre 8 corredores: 336 podios, pero solo 56 grupos distintos de tres medallistas.
EL ORDEN IMPORTA · nPk336n! / (n − k)!
p. ej., elegir 3 entre A-D:ABCABDACBACDADBADCBACBAD…
EL ORDEN NO IMPORTA · nCk56n! / (k! (n − k)!)
p. ej., elegir 3 entre A-D:ABCABDACDBCD…
TRIÁNGULO DE PASCAL, FILA 8 (nCk PARA CADA k)
LABORATORIO 3 · EL PRINCIPIO DEL PALOMAR

Más palomas que agujeros significa que alguien comparte

Mete n + 1 elementos en n cajas y al menos una caja tendrá dos. Parece obvio, pero demuestra hechos sorprendentes. Aquí, las personas se ordenan por mes de nacimiento: añade una 13.ª persona y habrá seguro un mes compartido.

Ene
Feb
Mar
Abr
May
Jun
Jul
Ago
Sep
Oct
Nov
Dic
Añade personas de una en una. Cada una cae en un mes de nacimiento al azar.

Las ideas clave de un vistazo

Camino euleriano0 o 2 vértices de grado imparNecesario para recorrer cada arista una vez.
Lema del apretón de manosΣ deg(v) = 2 × aristasAsí que el número de vértices de grado impar siempre es par.
VariacionesnPk = n! / (n − k)!El orden importa.
CombinacionesnCk = n! / (k!(n − k)!)El orden no importa.
Palomarn + 1 elementos, n cajas → una caja tiene 2Garantiza una coincidencia.
Implicaciónp → q ≡ ¬p ∨ qSolo es falsa cuando p es verdadera y q es falsa.
De Morgan¬(p ∧ q) ≡ ¬p ∨ ¬qNegar una «y» da una «o».
Árbolesn vértices → n − 1 aristasConexo y sin ciclos.

De Euclides a internet

hacia el 300 a. C.Euclides.Demostró que hay infinitos números primos y dio el algoritmo del máximo común divisor.
1654Pascal y Fermat.Unas cartas sobre un problema de juego fundaron la probabilidad y el conteo sistemático.
1736Los puentes de Euler.Su demostración de Königsberg se considera el primer teorema de la teoría de grafos.
1854Álgebra de Boole.George Boole convirtió la lógica en álgebra; 80 años después, Shannon la usó para diseñar circuitos.
1959El algoritmo de Dijkstra.Caminos más cortos en un grafo, que hoy se usan en mapas y enrutamiento de redes.
1976Teorema de los cuatro colores.Se demostró con un ordenador que comprobó casi 2.000 casos.

Para saber más

Discrete Mathematics and Its ApplicationsKenneth Rosen · el manual universitario de referencia
Mathematics for Computer ScienceLehman, Leighton y Meyer · texto gratuito del MIT
Concrete MathematicsGraham, Knuth y Patashnik · el clásico para profundizar
Ponte a prueba: 20 preguntas de matemática discretaGuía de algoritmos

Los puzles como el de Euler son razonamiento puro. Mide el tuyo.

Nuestro test de CI completo abarca el razonamiento lógico, numérico, verbal y espacial: 60 preguntas, unos 30 minutos.

Hacer el test de CI completo