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
pode ser paga exatamente usando apenas notas de
e de
reais. Em outras palavras, queremos provar que todo inteiro
admite escrita
com
inteiros não negativos.
Passo 2
Primeiro, verificamos manualmente os três menores casos a partir de
:
Logo, as quantias
,
e
são todas pagáveis sem troco.
Passo 3
Agora usamos indução para
.
Hipótese de indução: suponha que todo inteiro tal que
pode ser escrito como
.
Passo indutivo: queremos mostrar que também se escreve na forma
. Note que
Hipótese de indução: suponha que todo inteiro
Passo indutivo: queremos mostrar que
sempre que
. Então, por hipótese de indução, existe decomposição
para certos
. Somando
em ambos os lados, obtemos
ou seja,
também é representável.
Resposta
Portanto, por indução, toda quantia inteira maior que
pode ser paga exatamente com notas de
e de
reais.