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

🇨🇱 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.

ProblemaCompetenciaDificultad
¿Cuánto pan es una marraqueta?2015 Regional🟢 fácil
Partido de ping-pong2015 Nacional🟢 fácil
Cubiertos2017 Regional🟢 fácil
La tarea de matemática2017 Nacional🟢 fácil
Bus de turismo2018 Regional🟢 fácil
Gastón y las baldosas de su cocina2018 Nacional🟢 fácil
Azulejos2019 Regional🟢 fácil
El candado del basurero2019 Nacional🟢 fácil
El cifrado de César2020 Nacional🟢 fácil
Daniela y los múltiplos2022 Regional🟢 fácil
Cachipun2023 Nacional🟢 fácil
Baldosas2024 Regional🟢 fácil
Ricardo y su nóctulo2024 Regional🟢 fácil
Ocimatic2017 Regional🟡 media
Teletransportador cuántico de flujos2017 Clasificatoria🟡 media
La leyenda de Zolda2017 Nacional🟡 media
Empacadora de supermercado2020 Regional🟡 media
Balancín2023 Nacional🟡 media
Gollum vs Golomb2015 Nacional🔴 difícil
Mega Woman2018 Regional🔴 difícil
Catalonia2020 Nacional🔴 difícil
Galletas2025 Nacional🔴 difícil
Dominó2016 Clasificatoria🔴 difícil
El camino del dragón2016 Clasificatoria🔴 difícil
Problema Presidencial: Paltas Promedio2019 Regional🔴 difícil
Apuesta de alto riesgo2024 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.

ProblemaAñoMedia (puntos parciales)Lograron 100
Mosaic202459/10025%
Horses201551/10036%
Triple Peaks202543/100<1%
Prisoner Challenge202238/1002%
Message202437/100<1%
Classroom Game202637/1000%
Magic City202634/1001%
Packing Biscuits202023/10010%