a) Quais valores de postagem podem ser formados usan-do-se apenas selos de 5 e 9 centavos?
b) Demonstre a conjectura que você formulou usando a indução matemática.
c) Demonstre a conjectura que você formulou usando a indução completa.
d) Encontre uma demonstração para a sua conjectura que seja diferente daquelas que você construiu nos itens (b) e (c).
b) Demonstre a conjectura que você formulou usando a indução matemática.
c) Demonstre a conjectura que você formulou usando a indução completa.
d) Encontre uma demonstração para a sua conjectura que seja diferente daquelas que você construiu nos itens (b) e (c).
Passo 1
O problema trata de determinar quais valores inteiros de centavos podem ser obtidos como combinações não negativas de selos de 5 centavos e 9 centavos. O conteúdo é um caso clássico do “problema das moedas” ou “teorema do McNuggets” para duas peças com valores coprimos. Vamos
- listar os primeiros valores formáveis e não formáveis até encontrar o maior buraco (Frobenius),
- conjecturar o padrão,
- provar por indução simples,
- provar por indução completa,
- e dar uma demonstração alternativa usando inverso modular.
Passo 2
Valores da forma
com
. Listando os formáveis menores que 32:
Os inteiros entre 1 e 31 que não aparecem acima não são formáveis. O maior não formável é 31, e a partir de 32 todo inteiro pode ser obtido.
Conjectura: “todo pode ser escrito como
com
”.
Conjectura: “todo
Passo 3
Prova por indução simples (passo de 5 em 5):
Base: os cinco casos iniciais são formáveis, pois
Base: os cinco casos iniciais
Indução: suponha que para algum
o valor
é formável. Então
é formável também. Assim, a partir dos cinco casos-base, podemos gerar todos os inteiros
adicionando incrementos de 5 sucessivamente, cobrindo todas as classes de resto módulo 5.
Passo 4
Prova por indução completa (forte):
Defina é formável sempre que
.
Base: verificamos por inspeção direta (cada um aparece como combinação de 5 e 9).
Passo indutivo: tome . Então
, e como
, pelo pressuposto indutivo
vale, isto é,
. Logo
Defina
Base: verificamos
Passo indutivo: tome
também é formável. Isso completa a indução sobre todos
.
Passo 5
Demonstração alternativa usando inverso modular:
Como , o 5 tem inverso módulo 9, que é
(pois
). Dado
, escolha
Como
Então
, logo
é múltiplo de 9, digamos
. Para
garante-se
(pois
, e nos casos em que isso falharia um exame direto mostra que basta escolher outro representante de
dentro de
). Conclui-se
com
.
Resposta
(a) Exatamente os inteiros da forma
com
. Até 31 formáveis são
e o maior não formável é 31. Para todo
vale
.
(b) Demonstração por indução simples dada no Passo 3.
(c) Demonstração por indução completa dada no Passo 4.
(d) Demonstração alternativa via inverso modular dada no Passo 5.