[0,7 ponto ] Mostre que é possível pagar, sem receber troco, qualquer quantia inteira de reais, maior do que 7 , com notas de 3 reais e 5 reais. (Ok, sabemos que não existe nota de 3 reais, mas admita, para esse problema, que ela existe. Ponto.)

Passo 1

O enunciado pede para mostrar que toda quantia inteira de reais m>7 pode ser paga exatamente usando apenas notas de 3 e de 5 reais. Em outras palavras, queremos provar que todo inteiro m\ge8 admite escrita
m = 3x + 5y
com x,y inteiros não negativos.

Passo 2

Primeiro, verificamos manualmente os três menores casos a partir de 8:
8 = 3 + 5,
9 = 3\cdot3,
10 = 5\cdot2.
Logo, as quantias 8, 9 e 10 são todas pagáveis sem troco.

Passo 3

Agora usamos indução para m\ge8.
Hipótese de indução: suponha que todo inteiro n tal que 8\le n\le k pode ser escrito como n=3x+5y.
Passo indutivo: queremos mostrar que k+1 também se escreve na forma 3x+5y. Note que
(k+1)-3 = k-2 \ge 8
sempre que k\ge10. Então, por hipótese de indução, existe decomposição
(k+1)-3 = 3x + 5y
para certos x,y\ge0. Somando 3 em ambos os lados, obtemos
k+1 = 3(x+1) + 5y,
ou seja, k+1 também é representável.

Resposta

Portanto, por indução, toda quantia inteira maior que 7 pode ser paga exatamente com notas de 3 e de 5 reais.

Exercícios relacionados