[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 4 e 9 reais e um orçamento de 150 reais; queremos saber quais valores inteiros até 150 podem ser pagos exatamente como combinação não negativa de 4 e 9. O conteúdo envolve combinação linear de inteiros e o chamado problema de Frobenius.

Passo 2

Como gcd(4,9)=1, existe um valor máximo que não pode ser expresso como 4x+9y (com x,y>=0) 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 é
4cdot9 - 4 - 9 = 23
Logo, todos os inteiros a partir de 24 podem ser escritos como 4x+9y.

Passo 4

Fazendo um levantamento dos n<24 que se representam, obtemos
4,;8,;9,;12,;13,;16,;17,;18,;20,;21,;22,
enquanto
1,2,3,5,6,7,10,11,14,15,19,23
não se representam.

Passo 5

Como o orçamento é 150, as quantias possíveis de gastar são exatamente todos os inteiros representáveis até 150, isto é,
4,8,9,12,13,16,17,18,20,21,22cup 24,25,dots,150

Resposta

4,8,9,12,13,16,17,18,20,21,22cup24,25,dots,150

Exercícios relacionados