🀄️ Discrete Mathematics

🤖 Combinatorics & Counting

• 🤖 Counting paths in a grid, binomial coefficients challenges.

🪢 Graph Theory

• 🪢 “Seven Bridges of Königsberg”, Euler circuits, coloring puzzles.

🌗 Logic Circuits & Boolean Algebra

• 🌘 Minimal logic gates to achieve a certain output.

Mapas y coloraciones Permutaciones Variaciones y Combinatoria

0. Teoría de Números

Naturales ℕ:= {1,2,3,4,.,.}

Enteros ℤ:={.,.,-4,-3,-2,-1,0,1,2,3,4,.,.}

Suma

Diferencia

Producto

División ｂ＝ａ•ｑ＋𝚛 𝚛＝０→ ｂ： multiplo de ａ 𝚛: = ｂmodａ, resto

Algoritmo de la División

Máximo común divisor Mcd(a,b) = d si a mod d = 0 & b mod d = 0

Algoritmo de Euclides

Números Primos p∈ℕ es primo si ｐ mod ｑ≠ 0 Para q<p, q∈ℕ⁺＞１

Teorema fundamental de la aritmética Todo número es una composición de primos. ｎ＝ｐ₁ • p₂ • ｐ₃ .•. ｐₘ

Criba de Eratostenes

Principio de inducción Una propiedad 𝓟(•) Demostrar que 𝓟(1) 𝓟(𝑘)→𝓟(𝑘+1) ⁘𝓟(𝑛) [Traité du Triangle Arithmetic. Blaise Pascal - 1665]

Principio de buena ordenación Todo subconjunto no vacío de números enteros no negativos tiene un primer elemento Un elemento es menor a todos los demás. Este elemento ｍ puede sustituir a 1 para demostrar la propiedad en ｎ＞ｍ

Principio Fuerte de inducción Una propiedad 𝓟(•) Demostrar que 𝓟(1) 𝓟(𝑘)→𝓟(𝑛₀+1) 1≤𝑘≤𝑛₀ ⁘𝓟(𝑛)

Ecuaciones Diofánticas

[Diofanto, Alexandria Ⅲ a.C]

𝒂𝗑＋𝒃𝗒＝𝑛

Con 𝒂，𝒃，𝑛 ∈ ℤ 𝗑，𝗒 Son soluciones enteras sii 𝖽=mcd( 𝒂，𝒃) 𝖽 divide a 𝑛 Soluciones: {𝗑₀＋𝗍•𝒃⁄𝖽 , 𝗒₀＋𝗍•𝒂⁄𝖽 } 𝗍：∈ℤ {𝗑₀, 𝗒₀} es una solución particular

Diof. Cuadráticas 𝗑²＋𝗒²＝𝑛 𝑛>0 Tiene soluciones enteras sii 𝑛 se puede factorizar como producto de dos numeros con la misma paridad Ambos pares ⊻ ambos impares Por cada n=a•b x=(a+b)/2 ,y=(a-b)/2

Teorema de Factorización de Fermat Estudiar la composición de un número impar (si es primo o no) es equivalente a resolver

𝗑²＋𝗒²＝𝑛

Algoritmo de Factorización de Fermat

Ecuación Pitagórica 𝗑²＋𝗒²＝𝗓² Con naturales, es equivalente a encontrar todos los triángulos rectángulos con lados de longitud entera

El Último Teorema de Fermat 𝗑ⁿ＋𝗒ⁿ＝𝗓ⁿ Con n≥3 no tiene soluciones naturales

Reales ℝ

Complejos ℂ

Congruencia a es congruente a b si b mod m = a mod m b≡a [Disquisitiones Arithmeticæ, Gauss (1777-1855)]

13:00 y 1:00 son congruentes en un reloj módulo 12

Al resto de a/m en {0 .,. m-1} se le denomina Menor Residuo No Negativo de a mod m. a ▵ m a ⏃ m = r

Sistemas de numeración Decimal Bases

Babilonios: base 60 Binario 2 Octal 8 Hexadecimal 16