Prueba por agotamiento

La prueba por agotamiento , también conocida como prueba por casos , prueba por análisis de casos , inducción completa o método de fuerza bruta , es un método de prueba matemática en el que una afirmación se establece dividiendo el argumento en varios casos distintos y demostrando que la afirmación se cumple en cada caso. Los casos deben ser exhaustivos en su conjunto, asegurando que se consideren todas las situaciones posibles. ^{[ 1 ]}

La proliferación de ordenadores digitales ha aumentado considerablemente la conveniencia de utilizar el método de agotamiento (por ejemplo, la primera demostración asistida por ordenador del teorema de los cuatro colores en 1976), aunque tales enfoques también pueden ser cuestionados en función de la elegancia matemática . Los sistemas expertos pueden utilizarse para obtener respuestas a muchas de las preguntas que se les plantean. En teoría, el método de demostración por agotamiento puede utilizarse siempre que el número de casos sea finito. Sin embargo, dado que la mayoría de los conjuntos matemáticos son infinitos, este método rara vez se utiliza para derivar resultados matemáticos generales. ^{[ 2 ]}

Una demostración por casos generalmente sigue estos pasos: ^{[ 3 ]}

1. Identificar todos los casos posibles que agoten todas las posibilidades.
2. Demuestra la afirmación para el primer caso.
3. Demuestra la afirmación para cada caso restante.
4. Concluya que si todos los casos se han demostrado correctos, la afirmación es válida. Si alguno de los casos refuta la afirmación, esta no es válida.

La demostración por casos se usa comúnmente cuando un problema se separa naturalmente en categorías distintas, como por ejemplo: ^{[ 4 ]}

• Números pares e impares
• Valores positivos, negativos y cero
• Diferentes intervalos de una función

Este argumento resulta especialmente útil cuando un solo argumento no puede abordar fácilmente todas las situaciones posibles a la vez.

Demuestra que para cualquier entero n, el número n² ^es par si n es par, y n² ^es impar si n es impar.

Prueba:

Consideremos dos casos:

Caso 1

• n es par
• Entonces n=2k para algún entero k
• Entonces n ² = (2k) ² = 4k ² = 2(2k ² ), que es par

Caso 2

• n es impar
• Entonces n = 2k+1 para algún entero k
• Entonces n² ⁼ (2k+1) ^² = 4k² ⁺ 4k + 1 = 2(2k² ⁺ 2k) + 1, que es impar.

Dado que ambos casos han sido probados, la afirmación es válida para todos los números enteros n.

Demuestra que si un número entero es un cubo perfecto , entonces debe ser un múltiplo de 9, uno más que un múltiplo de 9 o uno menos que un múltiplo de 9. ^{[ 5 ]}

Demostración : Cada cubo perfecto es el cubo de algún entero n , donde n es un múltiplo de 3, uno más que un múltiplo de 3 o uno menos que un múltiplo de 3. Por lo tanto, estos tres casos son exhaustivos:

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

Los matemáticos prefieren evitar las demostraciones por agotamiento con un gran número de casos, que se consideran poco elegantes . La elegancia matemática puede definirse como un juicio subjetivo de una demostración matemática basado en su simplicidad y eficacia. A menudo se representa al encontrar la manera más sencilla de expresar un concepto complejo. ^{[ 6 ]} Una razón importante por la que esto se considera matemáticamente poco elegante es que este método se utiliza mejor en escenarios con un número finito de resultados. Los escenarios con una gran cantidad, o infinita, de resultados serían mucho más difíciles de demostrar con este método. ^{[ 7 ]} Un ejemplo de cómo tales demostraciones podrían ser poco elegantes es observar las siguientes demostraciones 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 desde entonces se han celebrado cada 4 años (sin contar situaciones excepcionales como las interrupciones en el calendario de los juegos causadas por la Primera Guerra Mundial, la Segunda Guerra Mundial y la pandemia de COVID-19 ). Dado que 1896 = 474 × 4 es divisible por 4, los siguientes Juegos Olímpicos se celebrarían en el año 474 × 4 + 4 = (474 ​​+ 1) × 4, que también es divisible por cuatro, y así sucesivamente (esta es una demostración por inducción matemática ). Por lo tanto, la afirmación queda demostrada.

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

Además de ser menos elegante, la demostración por agotamiento requerirá un caso adicional cada vez que se celebren unos nuevos Juegos Olímpicos de Verano. Esto contrasta con la demostración por inducción matemática, que prueba la afirmación indefinidamente en el futuro.

No existe un límite máximo para el número de casos permitidos en una demostración por agotamiento. A veces solo hay dos o tres casos, pero puede haber miles o incluso millones. Por ejemplo, resolver rigurosamente un problema de final de ajedrez podría implicar considerar un número muy grande de posiciones posibles en el árbol de juego de dicho problema.

La primera demostración del teorema de los cuatro colores fue una demostración por agotamiento con 1834 casos. ^{[ 8 ]} Esta demostración fue controvertida porque la mayoría de los casos fueron verificados por un programa informático, no manualmente. La demostración más corta conocida del teorema de los cuatro colores aún tiene más de 600 casos.

En general, la probabilidad de un error en toda la demostración 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 es verdadero solo por coincidencia, y no debido a algún principio o conexión subyacente. Otros tipos de demostraciones, como la demostración por inducción ( inducción matemática ), se consideran más elegantes . Sin embargo, hay algunos teoremas importantes para los que no se ha encontrado otro método de demostración, como

• La prueba de que no existe un plano proyectivo finito de orden 10.
• La clasificación de grupos simples finitos .
• La conjetura de Kepler .
• El problema de las ternas pitagóricas booleanas .

• Algoritmo del Museo Británico
• Prueba asistida por computadora
• Inducción enumerativa
• Inducción matemática
• Demostración por contradicción
• eliminación de disyunción