Prova por exaustão

 Nota: "Método de força bruta" redireciona para este artigo. Para outros significados, veja Método de força bruta (desambiguação).

Prova por exaustão, também conhecido como prova por casos, indução perfeita ou método de força bruta, é um método de prova matemática em que a afirmação a ser provada é dividida em um número finito de casos e cada caso é checado para verificar se a afirmação é correta. Esse é um método de prova direta. A prova por exaustão é composta por duas etapas:

1. A prova de que os casos são exaustivos; isto é, que cada parte da afirmação a ser provada corresponde com as condições de (pelo menos) um dos casos.
2. A prova de cada um dos casos.

Exemplo

Para provar que um número inteiro que é um cubo perfeito é um múltiplo de nove, ou é um a mais que um múltiplo de nove, ou o um a menos que um múltiplo de nove.

Prova: Cada número cúbico é o cubo de um número inteiro n. Cada número inteiro é ou um múltiplo de 3, ou 1 a mais ou 1 a menos que um múltiplo de 3. Então esses 3 casos são exaustivos:

• Caso 1: Se n = 3p, então n³ = 27p³, que é um múltiplo de 9.
• Caso 2: Se n = 3p+1, então n³ = 27p³ + 27p² + 9p + 1, que é um 1 a mais que um múltiplo de 9. Por exemplo, se n = 4, então n³ = 64 = 9x7 + 1.
• Caso 3: Se n = 3p - 1, então n³ = n³ = 27p³ − 27p² + 9p − 1, que é 1 a menos que um múltiplo de 9. Por exemplo, se n=5, então n³ = 125 = 9x14 -1.∎

Número de casos

Não há um limite máximo para o número de casos permitidos na prova por exaustāo. Ás vezes há apenas dois ou três casos. Ás vezes há milhares ou até milhões de casos. Por exemplo, solucionando o final de um jogo de xadrez pode involver considerar um grande número de possíveis posições na árvore de decisão do problema.

A primeira prova do teorema das quatro cores foi uma prova por exaustão com 1,936 casos. Essa prova foi controversia porque a maioria dos casos foram verificados por um programa de computador, e não a mão. A menor prova conhecida do teorema das quatro cores ainda tem 600 casos.

Matemáticos preferem evitar provas com um grande número de casos, pois é um método pouco elegante, e a probabilidade de erro aumenta com o número de casos. Uma prova com um grande número de casos dá a impressão de que o teorema é verdadeiro apenas por coincidência, e não por um princípio ou conexão. Outros tipos de prova, como a prova por indução, são consideradas mais elegantes. No entanto, há importantes teoremas para quais nenhum outro método de prova foi encontrado, como

• A prova de que não há um plano projetivo finito de ordem 10.
• A classificação de grupos simples finitos.
• A conjetura de Kepler.