De que modos é possível combinar 50 moedas, misturando moedas de 1 , de 10 e de 25 centavos, de modo a totalizar 3,50 reais?
Passo 1
O enunciado pede que se encontre de que modos (ou seja, quais combinações de quantidades) de moedas de
centavo,
centavos e
centavos permitem usar exatamente
moedas no total e obter a soma de
reais (ou seja,
centavos).
Informações dadas:
Informações dadas:
- Número total de moedas:
.\n - Tipos de moedas e seus valores:
centavo, centavos, centavos.\n - Soma total desejada:
reais centavos.\n
O que devemos retornar: todas as combinações não-negativas de quantidades dessas três moedas que satisfazem ambos os requisitos (total de moedas e total em centavos).
Passo 2
Vamos introduzir variáveis (isso deixa o problema mais claro e organizado):
- Seja
o número de moedas de centavo. - Seja
o número de moedas de centavos. - Seja
o número de moedas de centavos.
As duas condições do problema viram duas equações:
Aqui cada variável é um número inteiro não negativo (
).
Passo 3
Eliminamos uma variável para reduzir para uma equação em duas incógnitas. Da primeira equação:
Substituindo na segunda equação:
Agora vamos simplificar essa expressão passo a passo:
Passo 4
Para simplificar os coeficientes, dividimos por
(pois
são múltiplos de
):
Agora buscamos soluções inteiras não-negativas
dessa equação. Essa é uma equação linear diofantina em
e
.
Passo 5
Usamos aritmética modular para restringir
. Tome a equação
módulo
. Note que
e
. Assim:
ou seja
Multiplicando por
(inverso de
módulo
é
), obtemos
Portanto
pode ser escrito como
para algum inteiro
.
Passo 6
Substituímos
na equação reduzida
:
Como
é inteiro, isso é coerente; agora precisamos impor as condições de não negatividade em
e
.
Passo 7
Impondo
e
:
- Para
basta . - Para
precisamos de . Como é inteiro, .
Logo
pode ser
. Esses são os únicos valores possíveis.
Passo 8
Agora calculamos
para cada
e depois
via
. Fazemos isso um por um (sempre checando não-negatividade):
- Para
:
Verificação rápida:
.
- Para
:
Verificação:
.
- Para
:
Verificação:
.
- Para
:
Verificação:
.
Todos os
são não-negativos e as somas conferem, então essas são as combinações válidas.
Passo 9
Interpretando: cada solução
significa
moedas de
centavo,
moedas de
centavos e
moedas de
centavos. Encontramos exatamente quatro combinações possíveis, listadas acima.