Matemática y Combinatoria
Aritmética modular, conteo, combinatoria.
Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.
📍 Clases relacionadas: módulos 10 de la Ruta de Aprendizaje.
📋 En el temario OCI: desde la Regional: dígitos, módulo, paridad y divisibilidad, primalidad exhaustiva (♡); primalidad hasta √n y MCD de Euclides (⊖).
Números y conteo: divisibilidad, primos, aritmética modular y de cuántas formas puede pasar algo. Suele ser la parte que convierte un problema aparentemente imposible en una fórmula de dos líneas.
📌 Qué abarca
- Enteros y operaciones, exponenciación rápida; paridad y divisibilidad.
- Aritmética modular (suma, resta, multiplicación).
- Criba de primos (lineal y de Eratóstenes), factorización, primalidad O(√n), gcd/lcm (Euclides).
- Enteros de precisión arbitraria (operaciones básicas).
- Conteo: permutaciones y combinaciones, factorial, coeficientes binomiales, inclusión-exclusión, pigeonhole, identidad de Pascal / binomio.
- Teoría de juegos básica: posiciones ganadoras/perdedoras, minimax (⚠️ la poda alpha-beta está excluida, aunque minimax entre).
⛔ Fuera del syllabus IOI
- Inverso / división modular; FFT; álgebra lineal y exponenciación de matrices; interpolación polinomial; números complejos; cónicas; trigonometría; cálculo; estadística.
- Resolver recurrencias formalmente; Burnside; Sprague-Grundy / NIM general.
🎯 En competencia
En la OCI — Es, junto con ad-hoc, el tema más frecuente de la Regional: dígitos de un número, módulo, paridad, divisibilidad, primalidad. En la Nacional se suma poco (primalidad hasta √n, MCD). El conteo combinatorio y la aritmética modular en serio son material IOI. En este vault hay 26 problemas OCI del tema (12 de fases regionales, 11 de fases nacionales y 3 de clasificatorias IOI); están en la tabla de abajo.
En la IOI — La combinatoria suele ser conteo con inclusión-exclusión o binomiales. Como no hay inverso modular, los conteos módulo p se diseñan para no necesitarlo (precómputo directo, no factoriales inversos).
⚠️ La trampa típica
Desbordar antes de aplicar el módulo (a * b ya se pasó, aunque guardes en long long), y olvidar que en C++ -7 % 3 da -1: para índices, usa ((x % m) + m) % m.
⚙️ Algoritmos y técnicas
- Coeficientes binomiales
- Criba de Eratóstenes
- Euclides extendido (gcd)
- Exponenciación rápida (modular)
- Factorización
- Inclusión-exclusión
- Teoría de juegos (posiciones ganadoras)
🇨🇱 Problemas OCI (en español)
Empieza por acá: son problemas oficiales chilenos, con enunciado en español y mirror para enviar. Consulta la orientación de estudio al comienzo de esta página. La dificultad orienta la elección, pero no garantiza una solución completa.
| Problema | Competencia | Dificultad |
|---|---|---|
| ¿Cuánto pan es una marraqueta? | 2015 Regional | 🟢 fácil |
| Partido de ping-pong | 2015 Nacional | 🟢 fácil |
| Cubiertos | 2017 Regional | 🟢 fácil |
| La tarea de matemática | 2017 Nacional | 🟢 fácil |
| Bus de turismo | 2018 Regional | 🟢 fácil |
| Gastón y las baldosas de su cocina | 2018 Nacional | 🟢 fácil |
| Azulejos | 2019 Regional | 🟢 fácil |
| El candado del basurero | 2019 Nacional | 🟢 fácil |
| El cifrado de César | 2020 Nacional | 🟢 fácil |
| Daniela y los múltiplos | 2022 Regional | 🟢 fácil |
| Cachipun | 2023 Nacional | 🟢 fácil |
| Baldosas | 2024 Regional | 🟢 fácil |
| Ricardo y su nóctulo | 2024 Regional | 🟢 fácil |
| Ocimatic | 2017 Regional | 🟡 media |
| Teletransportador cuántico de flujos | 2017 Clasificatoria | 🟡 media |
| La leyenda de Zolda | 2017 Nacional | 🟡 media |
| Empacadora de supermercado | 2020 Regional | 🟡 media |
| Balancín | 2023 Nacional | 🟡 media |
| Gollum vs Golomb | 2015 Nacional | 🔴 difícil |
| Mega Woman | 2018 Regional | 🔴 difícil |
| Catalonia | 2020 Nacional | 🔴 difícil |
| Galletas | 2025 Nacional | 🔴 difícil |
| Dominó | 2016 Clasificatoria | 🔴 difícil |
| El camino del dragón | 2016 Clasificatoria | 🔴 difícil |
| Problema Presidencial: Paltas Promedio | 2019 Regional | 🔴 difícil |
| Apuesta de alto riesgo | 2024 Regional | 🔴 difícil |
🌍 Problemas IOI
De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Mosaic | 2024 | 59/100 | 25% |
| Horses | 2015 | 51/100 | 36% |
| Triple Peaks | 2025 | 43/100 | <1% |
| Prisoner Challenge | 2022 | 38/100 | 2% |
| Message | 2024 | 37/100 | <1% |
| Classroom Game | 2026 | 37/100 | 0% |
| Magic City | 2026 | 34/100 | 1% |
| Packing Biscuits | 2020 | 23/100 | 10% |