Prueba por agotamiento

Prueba por agotamiento, también conocida como prueba por casos, prueba por análisis de casos, inducción completa o El método de fuerza bruta, es un método de prueba matemática en el que el enunciado a demostrar se divide en un número finito de casos o conjuntos de casos equivalentes, y donde cada tipo de caso se verifica para ver si la proposición en cuestión es válida. Este es un método de prueba directa. Una prueba por agotamiento suele contener dos etapas:

1. Una prueba de que el conjunto de casos es exhaustivo; es decir, que cada instancia de la declaración que se demuestre coincide con las condiciones de (al menos) uno de los casos.
2. Una prueba de cada uno de los casos.

La prevalencia de las computadoras digitales ha aumentado en gran medida la conveniencia de utilizar el método de agotamiento (por ejemplo, la primera demostración asistida por computadora del teorema de los cuatro colores en 1976), aunque tales enfoques también pueden cuestionarse sobre la base de la elegancia matemática. Los sistemas expertos pueden utilizarse para llegar a respuestas a muchas de las preguntas que se les plantean. En teoría, la prueba por agotamiento se puede utilizar siempre que el número de casos sea finito. Sin embargo, debido a que la mayoría de los conjuntos matemáticos son infinitos, este método rara vez se utiliza para derivar resultados matemáticos generales.

En el isomorfismo de Curry-Howard, la prueba por agotamiento y el análisis de casos están relacionados con la coincidencia de patrones de estilo ML.

Ejemplo

La prueba por agotamiento se puede utilizar para demostrar que si un número entero es un cubo perfecto, entonces debe ser múltiplo de 9, 1 más que un múltiplo de 9 o 1 menos que un múltiplo de 9.

Prueba:
Cada cubo perfecto es el cubo de algún número entero n, donde n es un múltiplo de 3, 1 más que un múltiplo de 3 o 1 menos que un múltiplo de 3. Entonces estos tres casos son exhaustivos:

• Caso 1: n = 3p, entonces n³ = 27p³, que es un múltiple de 9.
• Caso 2: n = 3p+ 1, entonces n³ = 27p³+ 27p²+ 9p+ 1, que es 1 más que un múltiple de 9. Por ejemplo, si n= 4 entonces n³ = 64 = 9×7 + 1.
• Caso 3: si n = 3p1, entonces n³ = 27p³27 - 27p²+ 9p− 1, que es 1 menos que un múltiple de 9. Por ejemplo, si n = 5 entonces n³ = 125 = 9×14 - 1. Q.E.D.

Elegancia

Los matemáticos prefieren evitar las pruebas por agotamiento con un gran número de casos, que se consideran poco elegantes. Un ejemplo de cómo tales pruebas pueden ser poco elegantes es observar las siguientes pruebas de que todos los Juegos Olímpicos de verano modernos se celebran en años divisibles por 4:

Prueba: Los primeros Juegos Olímpicos de Verano modernos se celebraron en 1896, y posteriormente cada 4 años (sin tener en cuenta excepciones como cuando los juegos no se celebraron debido a la Primera Guerra Mundial y la Segunda Guerra Mundial junto con Los Juegos Olímpicos de Tokio 2020 se posponen hasta 2021 debido a la pandemia de COVID-19). Como 1896 = 474 × 4 es divisible por 4, las próximas Olimpiadas serían en el año 474 × 4 + 4 = (474 + 1) × 4, que también es divisible por cuatro, y así sucesivamente (esta es una prueba por inducción matemática). Por tanto, la afirmación queda probada.

La afirmación también se puede probar por agotamiento enumerando todos los años en los que se celebraron los Juegos Olímpicos de verano y comprobando que cada uno de ellos se puede dividir por cuatro. Con un total de 28 Juegos Olímpicos de verano a partir de 2016, esto es una prueba de agotamiento con 28 casos.

Además de ser menos elegante, la prueba por agotamiento también requerirá un caso adicional cada vez que se celebren nuevos Juegos Olímpicos de verano. Esto debe contrastarse con la prueba por inducción matemática, que prueba el enunciado indefinidamente en el futuro.

Número de casos

No existe un límite superior para el número de casos permitidos en una prueba por agotamiento. A veces sólo hay dos o tres casos. A veces puede haber miles o incluso millones. Por ejemplo, resolver rigurosamente un final de ajedrez podría implicar considerar un gran número de posiciones posibles en el árbol de juego de ese problema.

La primera demostración del teorema de los cuatro colores fue una prueba por agotamiento con 1834 casos. Esta prueba fue controvertida porque la mayoría de los casos se comprobaron mediante un programa informático, no manualmente. La prueba más corta conocida hoy en día del teorema de los cuatro colores todavía tiene más de 600 casos.

En general, la probabilidad de un error en toda la prueba aumenta con el número de casos. Una demostración con un gran número de casos deja la impresión de que el teorema sólo es verdadero por coincidencia y no debido a algún principio o conexión subyacente. Otros tipos de pruebas, como la prueba por inducción (inducción matemática), se consideran más elegantes. Sin embargo, hay algunos teoremas importantes para los cuales no se ha encontrado ningún otro método de prueba, como

• La prueba de que no hay un plano proyector finito del orden 10.
• La clasificación de grupos simples finitos.
• La conjetura de Kepler.
• El problema de los triples pitagóricos booleanos.