Percebe-se que, por termos múltiplos de 5, sempre será utilizada a moeda de 1 centavo para fechar 37 centavos.
Logo, partiremos para as maneiras diferentes possíveis de se utilizar essa moeda:
2 moedas de 1 centavo + maneiras de formar 35 centavos com as demais moedas (6 maneiras distintas):
1 de 25, 1 de 10 e 0 de 5
1 de 25, 0 de 10 e 2 de 5
0 de 25, 3 de 10 e 1 de 5
0 de 25, 2 de 10 e 3 de 5
0 de 25, 1 de 10 e 5 de 5
0 de 25, 0 de 10 e 7 de 5
7 moedas de 1 centavo + maneiras de formar 30 centavos com as demais moedas (5 maneiras distintas):
1 de 25, 0 de 10 e 1 de 5
0 de 25, 3 de 10 e 0 de 5
0 de 25, 2 de 10 e 2 de 5
0 de 25, 1 de 10 e 4 de 5
0 de 25, 0 de 10 e 6 de 5
12 moedas de 1 centavo + maneiras de formar 25 centavos com as demais moedas (4 maneiras distintas):
1 de 25, 0 de 10 e 0 de 5
0 de 25, 2 de 10 e 1 de 5
0 de 25, 1 de 10 e 3 de 5
0 de 25, 0 de 10 e 5 de 5
17 moedas de 1 centavo + maneiras de formar 20 centavos com as demais moedas (3 maneiras distintas):
0 de 25, 2 de 10 e 0 de 5
0 de 25, 1 de 10 e 2 de 5
0 de 25, 0 de 10 e 4 de 5
22 moedas de 1 centavo + maneiras de formar 15 centavos com as demais moedas (2 maneiras distintas):
0 de 25, 1 de 10 e 1 de 5
0 de 25, 0 de 10 e 3 de 5
27 moedas de 1 centavo + maneiras de formar 10 centavos com as demais moedas (2 maneiras distintas):
0 de 25, 1 de 10 e 0 de 5
0 de 25, 0 de 10 e 2 de 5
32 moedas de 1 centavo + maneiras de formar 5 centavos com as demais moedas (1 maneira distinta):
0 de 25, 0 de 10 e 1 de 5
37 moedas de 1 centavo (1 maneira distinta):
0 de 25, 0 de 10 e 0 de 5
Total: 24 maneiras diferentes.
Pra mim, não tem nada a ver a resposta ser 4!, porque ele não quer fazer uma permutação. Repare que se fosse assim, ele teria que usar uma moeda de cada para pagar, então 1+5+10+25=41, mas o troco é 37, e não importa se você vai receber primeiro a moeda de 5 ou a moeda de 10.
Fazendo dessa forma seria bem mais rápido mesmo, mas eu não consegui entender o raciocínio por trás dessa conta. Seria bom se quem fez assim pudesse comentar explicando como chegou nessa fórmula. Ajudaria muito. Mas eu fiz assim:
37, mas 2 centavos serão obrigatoriamente pagos com moedas de 1, então sobra 35. Dá pra chegar em 35 com:
1 moeda de 25: aqui em posso colocar uma moeda de 10 ou uma moeda de 5 e o restante de 1, ou duas de 5, ou todo o restante de 1. São 4 possibilidades.
3 moedas de 10: Posso colocar uma de 5 ou todas de 1. São 2 possibilidades.
2 moedas de 10: Posso colocar três de 5, duas de 5 e o resto de 1, uma de 5 e o resto de 1, ou todas de 1. Repare que dá pra adiantar o lado dividindo o valor que sobra por cinco e acrescentando um, que é a possibilidade de não usar nenhuma de 5. São 4 possibilidades.
1 moeda de 10: 35-10=25 -> 25/5=5 -> 5+1=6 -> 6 possibilidades.
Usando apenas moedas de 5 e 1: 35/5=7 -> 7+1=8, 8 possibilidades.
Agora soma tudo: 4+2+4+6+8=24
LETRA A