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).

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
  1. listar os primeiros valores formáveis e não formáveis até encontrar o maior buraco (Frobenius),
  2. conjecturar o padrão,
  3. provar por indução simples,
  4. provar por indução completa,
  5. e dar uma demonstração alternativa usando inverso modular.

Passo 2

Valores da forma \,5a+9b com a,b\ge0. Listando os formáveis menores que 32:
5,\;9,\;10,\;14,\;15,\;18,\;19,\;20,\;23,\;24,\;25,\;28,\;29,\;30.
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 n\ge32 pode ser escrito como 5a+9b com a,b\ge0”.

Passo 3

Prova por indução simples (passo de 5 em 5):
Base: os cinco casos iniciais n=32,33,34,35,36 são formáveis, pois
32=5\cdot1+9\cdot3,\quad 33=5\cdot3+9\cdot2,\quad 34=5\cdot5+9\cdot1,\quad 35=5\cdot7+9\cdot0,\quad 36=5\cdot0+9\cdot4.
Indução: suponha que para algum k\ge32 o valor k é formável. Então
k+5 = (5a+9b)+5 =5(a+1)+9b
é formável também. Assim, a partir dos cinco casos-base, podemos gerar todos os inteiros \ge32 adicionando incrementos de 5 sucessivamente, cobrindo todas as classes de resto módulo 5.

Passo 4

Prova por indução completa (forte):
Defina P(n)\!: n é formável sempre que n\ge32.
Base: verificamos P(32),P(33),P(34),P(35),P(36),P(37),P(38),P(39),P(40) por inspeção direta (cada um aparece como combinação de 5 e 9).
Passo indutivo: tome N\ge41. Então N-5\ge36, e como N-5\ge32, pelo pressuposto indutivo P(N-5) vale, isto é, N-5=5a+9b. Logo
N = (5a+9b)+5 =5(a+1)+9b
também é formável. Isso completa a indução sobre todos n\ge32.

Passo 5

Demonstração alternativa usando inverso modular:
Como \gcd(5,9)=1, o 5 tem inverso módulo 9, que é 5^{-1}\equiv2\pmod9 (pois 5\cdot2=10\equiv1). Dado n\ge32, escolha
a \equiv 2\,n \pmod9,\quad 0\le a\le8.
Então 5a\equiv n\pmod9, logo n-5a é múltiplo de 9, digamos n-5a=9b. Para n\ge32 garante-se b\ge0 (pois n-5\cdot8\ge32-40=-8, e nos casos em que isso falharia um exame direto mostra que basta escolher outro representante de 2n\pmod9 dentro de [0,8]). Conclui-se n=5a+9b com a,b\ge0.

Resposta

(a) Exatamente os inteiros da forma 5a+9b com a,b\ge0. Até 31 formáveis são
5,9,10,14,15,18,19,20,23,24,25,28,29,30,
e o maior não formável é 31. Para todo n\ge32 vale n=5a+9b.
(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.

Exercícios de Livros Relacionados