Encontre o erro na seguinte “prova”: em qualquer grupo com n pessoas, todas elas têm a mesma idade.
Se um grupo consiste de uma pessoa, todas têm a mesma idade.
Suponha que em qualquer grupo com k pessoas, todas têm a mesma idade.
Sejam a_{1}, a_{2}, \ldots, a_{k+1} as pessoas em um grupo com k+1 pessoas.
Desde que as pessoas a_{1}, a_{2}, \ldots, a_{k} e a_{2}, a_{3}, \ldots, a_{k+1} formam grupos com k pessoas, todas elas têm a mesma idade, por hipótese de indução.
Desde que a_{2} está em cada um destes grupos, segue que todas as k+1 pessoas a_{1}, a_{2}, \ldots, a_{k+1} têm a mesma idade.

Passo 1

O enunciado tenta provar, por indução em n, que em qualquer grupo com n pessoas todas têm a mesma idade. O conteúdo usado é o Princípio da Indução Matemática e a ideia de sobrepor dois subgrupos de tamanho k para concluir que um grupo de tamanho k+1 também é uniforme em idade.

Passo 2

Verificamos a base n=1. Num grupo com uma única pessoa é claro que todas (isto é, essa única pessoa) têm a mesma idade. Logo, a propriedade é verdadeira para n=1.

Passo 3

Hipótese de indução: suponha que todo grupo com k pessoas seja formado por indivíduos da mesma idade.

Passo 4

Passo de indução (pretendido): para um grupo de k+1 pessoas a_{1},a_{2},\dots,a_{k+1}, consideram-se os dois subgrupos de tamanho k \{a_{1},\dots,a_{k}\} e \{a_{2},\dots,a_{k+1}\}.
Pela hipótese de indução, cada um desses subgrupos é uniforme em idade. Como a_{2} pertence a ambos, conclui-se que todos os k+1 membros têm a mesma idade.

Passo 5

Análise do erro: o argumento de sobreposição falha quando k=1. Nesse caso, k+1=2 e os “subgrupos” são \{a_{1}\} e \{a_{2}\}. Cada um tem tamanho 1 e é uniforme, mas sua interseção
\{a_{1}\}\,\cap\,\{a_{2}\}=\emptyset
é vazia. Não há elemento comum para igualar idades, e portanto não se pode passar de n=1 para n=2. A indução não se inicia corretamente nesse passo.

Resposta

O erro está em assumir que os dois subgrupos de tamanho k sempre têm interseção não vazia; isso não vale para k=1, onde os subgrupos \{a_{1}\} e \{a_{2}\} não se sobrepõem.

Exercícios relacionados