Explorando o problema da moeda de Frobenius

uma proposta de atividade para alunos do ensino médio

Resumen

Certo país só tem dois valores de moedas, 2 e 15, que são as únicas formas possíveis de se comprar qualquer item nesse lugar. Para montar um time de RPG nesse país, alguns amigos se uniram para comprar os materiais necessários para o jogo e, pelo fato de não existir a ideia de troco (devolução de um dinheiro a mais que se é pago por um produto ou serviço), os amigos perceberam duas situações. A primeira é que eles não conseguiriam fazer uma compra de qualquer valor para esse jogo. Por exemplo, se o orçamento desse jogo fosse de 9, eles não teriam como pagar, já que para isso, a moeda de 15 seria muito (geraria troco) e a de 2 insuficiente (mesmo que usada mais de uma). Com isso, chegaram na segunda questão: qual seria então, o maior valor para esse jogo que não pode ser pago com essas moedas? Essa situação é um caso do conhecido problema da moeda de Frobenius, que pergunta qual é o maior valor inteiro que não pode ser obtido usando apenas moedas de valores fixados sem utilizar troco. Esse problema aparentemente simples era apresentado por Frobenius (1849–1917) em palestras no século XIX, mas sua solução (ou falta dela) tem desdobramentos até os dias atuais. Para dois valores de moedas, a solução é conhecida. Sejam m,n esses valores, o teorema de Sylvester nos garante que: se m,n são inteiros positivos, com mdc(m,n) = 1, então a solução para o problema de Frobenius com valores m,n é dada por mn− (m+ n). Voltando ao exemplo do nosso país, o maior valor que não pode ser pago é 15.2 − 2 − 15 = 13. Agora, para mais de dois valores, não existe solução com fórmula fechada.