Prueba por exhaución
De Wikipedia, la enciclopedia libre
Prueba por exhaución, también conocida como el método de fuerza bruta, es un método de demostración matemática en el cual la proposición a ser probada se divide en un número finito de casos, y cada caso es demostrado por separado. Una prueba por exhaución consta dos etapas:
- Una prueba de que los casos son exhaustivos; es decir, que cada instancia de la proposición a ser probada coincide con las condiciones de (al menos) uno de los casos.
- Una demostración de cada uno de los casos.
Por el contrario, el método de exhaución de Eudoxo de Cnidos era una forma geométrica y esencialmente rigurosa de calcular límites matemáticos.
[editar] Ejemplo
Para probar que todo número al cubo es o múltiplo de 9, o es 1 más o 1 menos que un múltiplo de 9. Demostración
Todo número al cubo es el cubo de algún natural n. Este natural es o un múltiplo de 3, o uno más o uno menos que un múltiplo de 3. Entonces los siguientes casos son exhaustivos:
- Caso 1: Si n es un múltiplo de 3 entonces el cubo de n es un múltiplo de 27, y entonces ciertamente un múltiplo de 9.
- Caso 2: Si n es 1 más que un múltiplo de 3 entonces el cubo de n es uno más que un múltiplo de 9.
- Caso 3: Si n es 1 menos que un múltiplo de 3 entonces el cubo de n es uno menos que un múltiplo de 9.
[Para completar la demostración, los enunciados de los casos 2 y 3 pueden ser probados mediante simple álgebra.]
[editar] ¿Cuántos casos?
No hay un tope al número de casos permitidos en una prueba por exhaución. A veces solamente hay 2 o 3 casos. A veces puede haber miles o incluso millones. Por ejemplo, resolver rigurosamente un problema de final de juego en ajedrez puede involucrar la consideración de un número muy elevado de posibles posiciones en el árbol de juego de ese problema.
La primera demostración del teorema de los cuatro colores fue una prueba por exhaución con 1.936 casos. Esta prueba fue controvertida porque la mayoría de los casos fueron examinados por un programa de computadora, no a mano. La prueba más breve conocida de este teorema aún tiene más de 600 casos.
Los matemáticos prefieren evitar demostraciones con grandes números de casos porque sienten que son poco elegantes —dejan una impresión de que el teorema es solamente cierto por coincidencia, y no por algún principio o conexión subyacente. No obstante, hay algunos teoremas importantes para los cuales ningún otro método de demostración ha sido hallado.
Además del teorema de los cuatro colores, otros ejemplos de grandes pruebas por exhaución son:
- La prueba de que no existe ningún plano proyectivo de orden 10.
- La clasificación de grupos finitos simples.
- La conjetura de Kepler.
[editar] Véase también
- Análisis de casos
- Demostración asistida por computadora
