Usando indução matemática, mostre que é possível obter qualquer valor igual ou superior a 20 cêntimos usando apenas selos de 5 ou 6 cêntimos.

Passo 1

O enunciado pede para provar, por indução matemática, que para qualquer inteiro n ≥ 20 existe uma combinação de selos de 5 cêntimos e 6 cêntimos que soma n. O conteúdo principal é indução (forte), e vamos precisar usar a hipótese para vários casos anteriores.

Passo 2

Vamos fazer o caso base verificando explicitamente n = 20, 21, 22, 23 e 24:
Para n = 20:
20 = 5times 4 + 6times 0
Para n = 21:
21 = 5times 3 + 6times 1
Para n = 22:
22 = 5times 2 + 6times 2
Para n = 23:
23 = 5times 1 + 6times 3
Para n = 24:
24 = 5times 0 + 6times 4
Assim, todos os inteiros de 20 a 24 podem ser obtidos.

Passo 3

Suponha agora, como hipótese de indução forte, que para todo inteiro m com 20 ≤ m ≤ k (k ≥ 24) existe combinação de selos de 5 e 6 que soma m.

Passo 4

Queremos mostrar que k+1 também pode ser obtido. Observe que k ≥ 24 implica k + 1 − 5 ≥ 20. Pela hipótese de indução forte, existe combinação de selos que soma k + 1 − 5. Basta então adicionar mais um selo de 5 cêntimos para obter k+1:
k+1 = (k+1-5) + 5

Passo 5

Pela base e pelo passo indutivo, pelo princípio da indução forte concluímos que todo inteiro n ≥ 20 pode ser escrito como combinação de 5 e 6 cêntimos.

Resposta

Por indução, fica provado que para todo inteiro n ≥ 20 existem inteiros não negativos a e b tais que n = 5a + 6b, ou seja, qualquer valor igual ou superior a 20 cêntimos pode ser obtido usando apenas selos de 5 ou 6 cêntimos.

Exercícios relacionados