(2,0) Prove que qualquer quantia em selos maior ou igual a 14 centavos pode ser obtida usando-se apenas selos de 3 e de 8 centavos.

Passo 1

O enunciado pede para mostrar que todo valor inteiro de centavos n\ge14 pode ser escrito na forma
n = 3a + 8b
com a,b inteiros não negativos. O conteúdo usado aqui é forte indução sobre inteiros, aplicando o fato de que, se um valor é obtido, então somando um selo de 3 c dá outro valor também obtido.

Passo 2

Base da indução: verificamos diretamente para n=14,15,16:
14 = 3\cdot2 + 8\cdot1,\qquad 15 = 3\cdot5 + 8\cdot0,\qquad 16 = 3\cdot0 + 8\cdot2.
Logo, os valores 14,15,16 são alcançáveis com selos de 3 e 8.

Passo 3

Passo indutivo (forte): suponha que todo inteiro m com 14\le m \le n seja representável como m=3a+8b. Queremos mostrar que n+1 também é representável.
Como já cobrimos a base até n=16, assumimos n\ge16. Então
(n+1)-3 = n-2 \;\ge\; 16-2 = 14,
o que garante que n-2 entra na faixa da hipótese indutiva.

Passo 4

Pela hipótese indutiva, existe representação
n-2 = 3a + 8b
com a,b\ge0. Então
n+1 = (n-2) + 3 = 3(a+1) + 8b,
ou seja, n+1 também é combinação de 3 e 8 centavos.

Resposta

Portanto, por indução forte, todo inteiro n\ge14 pode ser escrito como n=3a+8b com a,b inteiros não negativos.

Exercícios relacionados