Exercício 1.21. Considere a seguinte afirmação:
“Entre quaisquer n carros, todos têm a mesma cor.”
Um aluno apresenta a seguinte “demonstração” por indução no número n de carros:
Base: Para n=1, a afirmação é verdadeira, pois um grupo com apenas um carro tem, trivialmente, todos os seus integrantes da mesma cor.
Passo indutivo: Suponha que a afirmação seja verdadeira para n carros. Considere agora n+1 carros,
c_{1}, c_{2}, \ldots, c_{n}, c_{n+1}
Os primeiros n carros,
c_{1}, \ldots, c_{n},
têm todos a mesma cor, pela hipótese de indução. Analogamente, os últimos n carros,
c_{2}, \ldots, c_{n}, c_{n+1},
também têm todos a mesma cor. Como esses dois grupos têm carros em comum, conclui-se que todos os n+1 carros têm a mesma cor.

Passo 1

O enunciado apresenta a afirmação: “Entre quaisquer n carros, todos têm a mesma cor.”
O aluno dá uma prova por indução com estas partes:
  • Base: para n=1 a afirmação é verdadeira (um carro só tem uma cor).
  • Passo indutivo: assumindo a afirmação verdadeira para n carros, toma-se uma coleção de n+1 carros c_{1},c_{2},\ldots,c_{n},c_{n+1},considera-se o primeiro subconjunto de n carros S_1=\{c_{1},\ldots,c_{n}\} e o segundo S_2=\{c_{2},\ldots,c_{n+1}\}. Pela hipótese de indução S_1 é monocromático e S_2 também; como S_1\cap S_2\neq\varnothing conclui-se que as cores coincidem e, assim, todos os n+1 carros têm a mesma cor.
O que nos pede: verificar se a prova está correta; se não, apontar o erro e explicar didaticamente por que falha (mostrando o que exatamente não vale e um contraexemplo simples).

Passo 2

Relembrando o princípio da indução (de forma clara e simples): para provar uma propriedade P(n) para todo inteiro n\ge1 por indução, é preciso:
  1. Provar a base: P(1) é verdadeira.
  2. Provar o passo indutivo: para todo k\ge1, assumir P(k) verdadeira e a partir disso provar P(k+1).
Se ambas as etapas valem para todo k apropriado, então P(n) vale para todo n\ge1. Importante: o passo indutivo deve ser válido para o primeiro k que segue a base (ou seja, deve funcionar para k=1 se a base foi n=1). Não se pode tacitamente assumir que o passo funciona apenas para k grandes — ele precisa valer já logo após a base.

Passo 3

Formalizando o argumento do aluno:
  • Define-se P(n): “qualquer conjunto de n carros é monocromático”.
  • Base: P(1) é verdadeira.
  • Passo: suponha P(n) verdadeira e tome n+1 carros c_{1},\ldots,c_{n+1}. Os conjuntos S_1=\{c_{1},\ldots,c_{n}\},\qquad S_2=\{c_{2},\ldots,c_{n+1}\}têm tamanho n. Pela hipótese S_1 é toda de uma cor e S_2 também. O argumento final usa que S_1\cap S_2 contém carros (por exemplo c_2,\ldots,c_n), logo como esse carro comum pertence a ambos os conjuntos suas cores coincidem e assim todos os n+1 carros têm a mesma cor.
Esse é o raciocínio dado — parece elegante e curto. Agora vamos checar cada passo com cuidado.

Passo 4

Onde está o problema? analisar a interseção dos conjuntos:
  • S_1\cap S_2=\{c_{2},\ldots,c_{n}\}. O número de elementos dessa interseção é n-1.
  • Se n-1\ge1 (ou seja, se n\ge2), então a interseção não é vazia e de fato há um carro comum cuja cor faz a ligação entre os dois subconjuntos.
  • Porém, quando n=1 temos n-1=0. Ou seja, para n=1 os conjuntos são S_1=\{c_1\},\qquad S_2=\{c_2\},e então S_1\cap S_2=\varnothing. Neste caso NÃO há carro em comum que force as cores a coincidirem. Portanto o argumento do aluno usa implicitamente a hipótese S_1\cap S_2\neq\varnothing, que só é verdadeira quando n\ge2. Mas a prova de indução precisa que o passo indutivo funcione também para n=1 (para poder deduzir P(2) a partir de P(1)). Logo existe uma falha lógica: o passo indutivo, tal como apresentado, não é válido para k=1.
Em termos simples: o argumento só funciona a partir do caso em que os dois subconjuntos de tamanho n têm interseção não vazia, ou seja, para n\ge2. Ele não prova P(2) a partir de P(1). Como a indução começa em 1, o elo 1\to2 falta.

Passo 5

Exemplo concreto que destrói a afirmação (contraexemplo fácil): considere n=2 e dois carros distintos c_1,c_2 tais que c_1 é vermelho e c_2 é azul. Claramente nem todos os carros (os dois) têm a mesma cor, logo P(2) é falsa. Portanto a afirmação “entre quaisquer n carros todos têm a mesma cor” não é verdadeira para todo n. Uma prova por indução que pretendesse mostrar isso deveria ser capaz de provar P(2) a partir de P(1), mas o passo do aluno não faz isso (porque falta interseção).

Passo 6

Como interpretar e aprender com isso (dica prática para a prova):
  • Verifique sempre se o passo indutivo funciona para o menor k possível (o que segue imediatamente da base). Não aceite argumentos que tacitamente usam propriedades que só surgem em casos maiores.
  • Identifique hipóteses escondidas: aqui a hipótese escondida era “os dois subconjuntos de tamanho n têm interseção não vazia”. Tornar essa hipótese explícita mostra que o argumento só vale para n\ge2.
  • Se um passo indutivo requer uma propriedade adicional (como interseção não vazia), então ou:
    • prove essa propriedade separadamente para o caso inicial (por exemplo prove P(2) diretamente), ou
    • ajuste a base da indução para começar num n maior (por exemplo comece a indução em n=2) — mas isso só é aceitável se a afirmação for verdadeira a partir daquele ponto. No nosso caso P(2) é falsa, então não há conserto possível: a afirmação original é falsa.

Passo 7

Resumo final e conclusão: a prova do aluno é falaciosa porque o passo indutivo usa a interseção não vazia de S_1 e S_2, o que falha no caso n=1 (passo de 1 para 2). A afirmação é falsa (contraexemplo: dois carros de cores diferentes). Portanto a “demonstração” não é correta.

Resposta

A demonstração é falha; o erro ocorre no passo indutivo ao assumir que S_1\cap S_2\neq\varnothing (isso requer n\ge2), logo o passo de n=1 para n=2 não está provado. A afirmação é falsa (contraexemplo: dois carros de cores diferentes).

Exercícios relacionados