Usando indução, vamos provar que em um conjunto com n frutas todas têm a mesma cor. Descubra onde está o erro nesta demonstração.

Passo 1

Beleza, aqui o enunciado diz assim: “Usando indução, vamos provar que em um conjunto com frutas todas têm a mesma cor.” A gente precisa perceber qual é o conteúdo (Princípio da Indução Matemática) e o que vai ser necessário:
  • Definir a propriedade : “Em qualquer conjunto de frutas, todas têm a mesma cor.”
  • Mostrar o caso base .
  • Mostrar o passo indutivo: se é verdade, então também é.
    Depois disso, descobrir onde o raciocínio dá ruim.

Passo 2

Caso base ( ):
diz “num conjunto de 1 fruta, todas têm a mesma cor”. Isso é trivial, porque só existe uma fruta ali — não tem como comparar, então OK: é verdadeira.

Passo 3

Passo indutivo (ideia clássica):
  • Suponha que para certo valha : “todo conjunto de frutas tem todas as frutas da mesma cor”.
  • Agora pegue um conjunto com frutas. Chamemos duas frutas de destaque de e .

Passo 4

Construa dois subconjuntos de tamanho :
  1. , tem frutas.
  2. , também tem frutas.
    Pela hipótese de indução, em cada subconjunto tudo é da mesma cor.
    Como e têm frutas cada, eles se sobrepõem em frutas (isto é, tem frutas).
    Aí o argumento diz: nessas frutas comuns, tudo tem uma única cor, então essa cor “liga” a cor de (que vem de ) e a cor de (que vem de ). Conclusão: todas as frutas têm a mesma cor.

Passo 5

E onde está o pulo do gato (o erro)? O raciocínio só funciona se , ou seja, se . No primeiro passo indutivo (ir de para ), temos:
  • e teriam 1 fruta cada,
  • Mas aí é vazio (0 frutas), não há nenhum elemento comum para “garantir” a mesma cor.
    Sem essa interseção não dá pra “ligar” a cor de com a de . O argumento assume que sempre existe essa fruta em comum, o que falha exatamente em .

Resposta

O erro está na suposição de que os dois subconjuntos de tamanho (formados ao tirar cada fruta) sempre têm interseção não vazia. Isso não vale para , então o passo indutivo falha ao passar de 1 para 2 frutas.

Exercícios relacionados