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 últi \operatorname{mos} 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.
Identifique o erro nessa demonstração.

Passo 1

Vou listar com clareza o que o enunciado dá e o que pede (sem resolver nada ainda).
  • Afirmação a ser verificada: “Entre quaisquer n carros, todos têm a mesma cor.”
  • Demonstração proposta pelo aluno:
    • Base: para n=1 a afirmação é verdadeira.
    • Passo indutivo: assumir a afirmação verdadeira para n carros; então, dados n+1 carros c_{1},c_{2},\dots,c_{n},c_{n+1}, os primeiros n (isto é, \{c_{1},\dots,c_{n}\}) têm a mesma cor por hipótese; os últimos n (isto é, \{c_{2},\dots,c_{n+1}\}) também têm a mesma cor por hipótese. Como esses dois grupos “têm carros em comum”, conclui-se que todos os n+1 carros têm a mesma cor.
  • O que o exercício pede: identificar o erro nessa demonstração.

Passo 2

Breve aula sobre como prova por indução funciona (para ficar bem claro o que é exigido).
  • Para provar uma propriedade P(n) para todo inteiro n\ge 1 por indução, precisam ser mostradas duas coisas:
    1. Base: P(1) é verdadeira.
    2. Passo indutivo: para todo n\ge 1, a partir de P(n) deve-se deduzir P(n+1). Ou seja, a implicação P(n)\Rightarrow P(n+1) deve ser válida para todo n na faixa considerada.
  • Importante: o passo indutivo tem de funcionar para qualquer n (inclusive para n=1). Não basta que ele funcione apenas para alguns n; o encadeamento da indução depende de que a implicação valha sempre.

Passo 3

Análise detalhada do argumento do aluno e identificação do ponto frágil.
  • Denotemos os dois grupos usados no passo indutivo por A=\{c_{1},c_{2},\dots,c_{n}\}, \qquad B=\{c_{2},c_{3},\dots,c_{n+1}\}.
  • O argumento do aluno usa que A tem todos os carros de mesma cor (pela hipótese P(n)) e que B também tem todos os carros de mesma cor; então como A\cap B contém carros, isso força as cores a serem iguais em A e B, e assim todos os n+1 carros teriam a mesma cor.
  • Calculemos o tamanho da interseção: A\cap B=\{c_{2},c_{3},\dots,c_{n}\},que tem exatamente n-1 elementos. Logo |A\cap B|=n-1.
  • Observação crucial: se n-1\ge 1 (isto é, se n\ge 2), então A\cap B não é vazio e o raciocínio de “ligar” as cores funciona: um carro comum faz a ponte entre os dois blocos e garante que as cores coincidam.
  • Porém, se n=1, então |A\cap B|=0: os conjuntos são A=\{c_{1}\},\qquad B=\{c_{2}\},que são disjuntos. Nesse caso NÃO existe carro em comum que permita concluir que a cor de c_{1} é igual à cor de c_{2}. Portanto o passo indutivo, tal como foi escrito, falha exatamente na transição n=1\Rightarrow n+1=2.

Passo 4

Um contraexemplo simples para mostrar que a afirmação geral é falsa e que o “buraco” identificado é real.
  • Considere dois carros c_{1} e c_{2} com cores diferentes (por exemplo, c_{1} vermelho e c_{2} azul). Então a propriedade “todos os carros têm a mesma cor” é falsa para n=2.
  • Temos P(1) verdadeira (um único carro tem cor única), mas P(2) é falsa. Logo a prova por indução que só tem a base P(1) e o passo com o argumento acima não consegue estabelecer P(2); e como P(2) é falsa, a afirmação original também é falsa.

Passo 5

Explicação de como consertar (ou esclarecer) o argumento e por que isso não salva a afirmação original.
  • Se o aluno tivesse provado a base para n=1 e também para n=2 (ou, equivalentemente, começasse a indução a partir de n=2 assumindo P(2) e provando P(n)\Rightarrow P(n+1) para todo n\ge 2), então o passo indutivo funcionaria para todo n\ge 2 porque aí sempre teríamos |A\cap B|=n-1\ge 1.
  • Mas na prática P(2) é falsa (como mostrei com o contraexemplo), portanto não há como consertar a prova para obter a afirmação original. O erro não é um mero detalhe de escrita: é uma falha lógica na hipótese necessária para que a implicação indutiva seja válida para todos os n.

Passo 6

Resumo didático e motivador (para você lembrar na prova).
  • A indução exige que o passo indutivo funcione para todo n do domínio; aqui ele falha em n=1 porque os dois subconjuntos considerados ficam disjuntos, então não há elemento que force igualdade de cor entre os blocos.
  • Em linguagem curta: o aluno assumiu implicitamente que os dois grupos de n carros sempre têm interseção não vazia, mas isso é falso quando n=1. Esse é o erro lógico.
  • Fica a dica: quando usar indução, verifique sempre explicitamente se o passo indutivo vale mesmo para os menores valores de n (especialmente na transição do caso base).

Resposta

O erro é supor que os dois subconjuntos de n carros sempre se sobrepõem. Para n=1 os conjuntos \{c_{1}\} e \{c_{2}\} são disjuntos, portanto não há elemento comum que ligue as cores, e o passo indutivo falha na transição 1\Rightarrow 2.

Exercícios relacionados