Adalberto Spezamiglio
São José do Rio Preto – UNESP

A RPM 45, de 2001, traz, na seção probleminhas, a seguinte questão: de quantas maneiras é possível trocar um real? Como é de costume com os probleminhas, não apresenta resolução e sim a resposta, encontrada na página 54: 242. O problema foi passado a alunos do nosso curso de Matemática e depois de um tempo Ricardo Sampaio, aluno do terceiro ano do período noturno da Licenciatura, apresentou a listagem de todas as possibilidades, encontrando o total de 292. (A RPM publicou no número seguinte, RPM 46, uma errata indicando a resposta correta, 292.) Dado à discordância das respostas, nos interessamos pelo problema e chegamos a uma forma indireta de contar as possibilidades. Vamos em seguida exibir uma resolução que vai mostrar que a resposta do Ricardo está correta.

Para ser mais preciso, o problema é o seguinte: de quantas maneiras é possível trocar um real em moedas de 1, 5, 10, 25 e 50 centavos? Denotando por x, y, z, w e t o número de moedas, respectivamente, de 1, 5, 10, 25 e 50 centavos e tomando o centavo como unidade, queremos saber o número de soluções inteiras não negativas da equação

x + 5y + 10z + 25w + 50t = 100.

Como x = 100 – 5y – 10z – 25w – 50t, então é múltiplo de 5, logo x = 5n, com n inteiro não negativo. A equação anterior fica

5n + 5y + 10z + 25w + 50t = 100, que é equivalente a

n + y + 2z + 5w + 10t = 20              (1)

Vemos que na equação (1) n + y + 2z pode assumir todos os valores múltiplos de 5 de 0 a 20. Assim, n + y + 2z = 5m com 0 m 4 inteiro, e portanto 5w + 10t = 20 – 5m, que é equivalente a w + 2t = 4 – m. A equação (1) fica decomposta em duas equações,

n + y + 2z = 5m,               (A)

w + 2t = 4 – m                 (B)

onde m inteiro, 0 m 4. Temos (n, y, z, w, t) solução de (1) se e somente se (n, y, z) é solução de (A), para algum m, e (w, t) é solução de (B) para o mesmo m. Fixado m, cada solução de (A) pode ser combinada com todas as soluções de (B), dando soluções de (1). Daí, o número de soluções de (1), para cada m fixado, é o produto do número de soluções de (A) pelo número de soluções de (B). Depois, somamos os números de soluções encontradas com m variando de 0 a 4.

Pondo a equação (A) na forma y + 2z = 5m – n, vemos que n pode assumir todos os valores inteiros entre 0 e 5m. Portanto, o sistema (A), (B) pode ser substituído pelo sistema

w + 2t = 4 – m,                 (B)

y + 2z = 5m – n,                (C)

sendo 0 m 4 e 0 n 5m.

Em nossa análise vamos utilizar o fato simples dado em seguida. Se x é um número real não negativo, vamos denotar por [x] a parte inteira de x. Por exemplo, [1] = 1, [] = 1, [p] = 3, [5/2] = 2.

Lema: Dado N inteiro não negativo, o número de soluções inteiras não negativas da equação X + 2Y = N é [] + 1.

Prova: Se N = 2k é par, X pode assumir os valores 0, 2, 4, ..., 2k. Cada um desses valores substituído na equação fornece um único valor para Y, obtendo uma solução da equação. Temos k + 1 = [] +1 soluções. Se N = 2k + 1 é ímpar, a equação fica (X – 1) + 2Y = 2k e, pela parte anterior, X – 1 pode assumir os valores 0, 2, 4, ..., 2k. Portanto, X pode ser 1, 3, 5, ..., 2k + 1. Cada um desses valores substituído na equação fornece um único valor para Y. Temos novamente k + 1 = [] +1 soluções. O lema está provado.

Vamos considerar agora o sistema de equações (B), (C). Para simplificar, vamos usar a notação j(k) = [] +1, para k inteiro não negativo.

m = 0: Neste caso, n só pode ser 0. (B) fica w + 2t = 4, que tem j(4) = 3 soluções. (C) fica y + 2z = 0, que tem j(0) = 1 solução. O total de soluções para m = 0 é 3.1 = 3.

m = 1: Neste caso, n varia de 0 a 5. (B) fica w + 2t = 3, que tem j(3) = 2 soluções. (C) fica y + 2z = 5 – n, com 0 n 5. O número de soluções de (C) é

j(5 – k) : j(0) + j(1) + j(2) + ... + j(5) = 12.

O número de soluções para m = 1 é 2.12 = 24.

m = 2: Neste caso, n varia de 0 a 10. (B) fica w + 2t = 2, que tem j(2) = 2 soluções. (C) fica y + 2z = 10 – n, com 0 n 10. O número de soluções de (C) é

j(0) + j(1) + ... + j(10) = 36.

O número de soluções para m = 2 é 2.36 = 72.

m = 3: Neste caso, n varia de 0 a 15. (B) fica w + 2t = 1, que tem j(1) = 1 solução. (C) fica y + 2z = 15 – n, com 0 n 15. O número de soluções de (C) é

j(0) + j(1) + ... + j(15) = 72.

O número de soluções para m = 3 é 1.72 = 72.

m = 4: Neste caso, n varia de 0 a 20. (B) fica w + 2t = 0, que tem j(0) = 1 solução. (C) fica y + 2z = 20 – n, com 0 n 20. O número de soluções de (C) é

j(0) + j(1) + ... + j(20) = 121.

O número de soluções para m = 4 é 1.121 = 121.

Assim, o número total de soluções de (1) é 121 + 72 + 72 + 24 + 3 = 292.

Podemos representar o número total de soluções da equação (1), decomposta no sistema (B), (C), usando a notação introduzida, através da seguinte fórmula:

[j(4 – m) j(5m – n)].

O método usado nesta resolução pode, por exemplo, ser empregado para resolver de quantas maneiras é possível trocar uma nota de 100 reais por moedas/notas de 1, 2, 5, 10, 20 e 50 reais. Um quadro de possibilidades neste caso é bem mais complicado. A resposta é 4 562.