[13] Dispondo de 150 reais, quais são as quantias que se podem gastar comprando selos de 4 reais e de 9 reais?
Passo 1
Resumimos o problema: temos selos de
e
reais e um orçamento de
reais; queremos saber quais valores inteiros até
podem ser pagos exatamente como combinação não negativa de
e
. O conteúdo envolve combinação linear de inteiros e o chamado problema de Frobenius.
Passo 2
Como
, existe um valor máximo que não pode ser expresso como
(com
) e, acima desse valor, todos os inteiros podem ser representados.
Passo 3
Pela fórmula de Frobenius para dois números coprimos, o maior inteiro não representável é
Logo, todos os inteiros a partir de
podem ser escritos como
.
Passo 4
Fazendo um levantamento dos
que se representam, obtemos
enquanto
não se representam.
Passo 5
Como o orçamento é
, as quantias possíveis de gastar são exatamente todos os inteiros representáveis até
, isto é,