Dispondo de R$100,00, quais são as quantias que se podem gastar comprando selos de 5,00 \mathrm{R} $ 7,00$ ?

Passo 1

O enunciado pede todas as quantias s que podemos gastar, com s<=100, escrevendo
s = 5x + 7y
para alguns inteiros não negativos x e y. O conteúdo é soma de múltiplos (equação diofantina linear) e o que vamos usar é o teorema de Frobenius para saber até que ponto precisamos verificar “na mão” e depois um argumento geral.

Passo 2

Como gcd(5,7)=1, o maior inteiro que não se escreve como 5x+7y é
(5-1)(7-1)-1 = 4cdot6 -1 = 23
Isso quer dizer que todo inteiro n>=24 já se expressa como 5x+7y.

Passo 3

Agora precisamos achar todos os valores de 5x+7y menores ou iguais a 23. Fazendo y=0,1,2,dots e ajustando x, os valores obtidos (sempre <=23) são:
5,;7,;10,;12,;14,;15,;17,;19,;20,;21,;22

Passo 4

Juntando tudo, as quantias possíveis são exatamente os valores de
5,7,10,12,14,15,17,19,20,21,22
e todos os inteiros de 24 até 100, pois para n>=24 já temos representação.

Resposta

As quantias possíveis de gasto são
5,7,10,12,14,15,17,19,20,21,22;cup;24,25,26,dots,100

Exercícios relacionados