Problema do troco de Frobenius
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Setembro de 2016) |
 | Esta página ou se(c)ção precisa ser formatada para o padrão wiki. (Agosto de 2015) |
O problema do troco de Frobenius, ou simplesmente problema de Frobenius, em sua formulação geral é o seguinte:
- Considere que existem moedas dos seguintes denominações: V1, V2, ..., Vn. Qual o menor valor que pode ser pago utilizando tais moedas?
Matematicamente, podemos traduzí-lo da seguinte forma:
- Sejam V1, V2, ..., Vn inteiros positivos. Determinar o inteiro positivo T = T(V1, V2, ..., Vn) tal que todo inteiro positivo a ≥ T pode ser rescrito como combinação inteira positiva de V1, V2, ..., Vn, isto é, a equação
V1x1 + v2x2 + ... + Vnxn = a (1)
possui solução não negativa, isto é, xi ≥ 0 para i = 1, 2, ..., n.
O problema está bem posto, uma vez que se a é suficientemente grande, então existe solução natural. O caso n = 2 será tratado a seguir. O caso n = 3 possui uma cota conhecida e, em geral, são conhecidos algoritmos rápidos tais que: dados b, c, d determinam o maior a que não pode ser escrito como combinação natural de b, c, d.
Pontos naturais em retas[editar | editar código-fonte]
Se considerarmos o problema de Frobenius em dimensão dois, isto é, com apenas dois tipos de moedas, então o mesmo possui uma solução simples. Digamos que as denominações das moedas sejam b e c. gostaríamos de determinar os inteiros positivos a tais que a equação diofantina linear bx + cy = a possui solução positiva. Mais precisamente, desejamos obter uma cota T = T(b,c) tal que a ≥ T possa ser escrito como combinação inteira positiva de b e c. Considere o seguinte exemplo:
- Os caixas eletrônicos da empresa “Banco 24 Horas” (máquinas vermelhas espalhadas pelas principais cidades do país) operam, exclusivamente, com notas de R$ 20,00 e R$ 50,00. Claramente não são todos os valores que podem ser sacados destes terminais, por exemplo não é possível sacar quantias que não sejam múltiplas de 10, mas também, não podemos sacar as quantias de R$ 10,00 e R$ 30,00. É possível sacar qualquer quantia maior ou igual a R$ 40,00 e que seja múltiplo de 10? Infelizmente, para confundir ainda mais, há uma mensagem no visor: digite a quantia múltiplo de 20 ou 50 reais!!!
A Solução, em geral, desse tipo de problema é a conclusão do seguinte:
- Teorema 1. Sejam a, b, c Є Z números inteiros positivos, mdc(b,c) = 1, e suponha que a ≥ bc – b – c. Então a equação
bx + cy = a possui (pelo menos) uma solução inteira não negativa. Ou seja, (m,n) Є Z, m, n ≥ 0.
- Prova: Observe que a condição da existência de solução em inteiros não negativos é equivalente a existência de solução (m,n) Є Z² satisfazendo m + 1 > 0 e n + 1 > 0. Se somamos b + c em ambos os lados da equação original obtemos:
b(x + 1) + c(y + 1) = a + b + c
e agora exigimos que ẋ = x + 1 > 0 e ẏ = y + 1 > 0 na equação
bẋ + cẏ = d (2)
Na qual d = a + b + c.
Como mdc(b,c) = 1, o vetor diretor v=(c,-b) é um vetor diretor inteiro primitivo da reta (2). Assim, pelo corolário: Sejam a, b, c Є Z e d = mdc(b, c). Considere a equação Diofantina
bx + cy = a.
Suponhamos que d|a (d divide a), isto é, a reta possui infinitos pontos inteiros. Então a distância entre dois pontos inteiros consecutivos na reta é √(b^2+ c^2 )/d; a distância entre dois pontos consecutivos na reta (2) é ‖v‖= √(b^2+c^2).
Observamos que os pontos de interseção da reta com os eixos coordenados ẋ e ẏ são (0,d/c) e (d/b,0) respectivamente, e se os mesmo encontram-se a uma distância
√((d^2/c^2)+(d^2/b^2)) = d/bc*√(b^2+c^2).
Claramente, se
- √(b^2+c^2) < √((d^2/c^2) + (d^2/b^2)) = d/bc*√(b^2+c^2) (3)
Então a equação 2 possuirá algum ponto com ẋ > 0 e ẏ > 0.
Mas a desigualdade citada é equivalente a
d > bc → a > bc – b – c.
Exemplos[editar | editar código-fonte]
- Prove que toda quantia inteira maior ou igual a R$4,00 pode ser paga utilizando notas de R$2,00 e R$5,00.
Segundo o algoritmo:
Para b = 2 e c = 5, temos:
a > 2*5 – 2 – 5
a > 10 – 2 – 5
a > 3, isto é, a é qualquer valor ≥ 4.
2. Originalmente as caixas de McNuggets eram de 3 tipos: 6, 9 ou 20. Mostre que qualquer número de McNuggets maior que 43 pode ser comprado.
Uma vez que 6, 9, e 20 são relativamente primos, qualquer número inteiro suficientemente grande pode ser expressa como uma combinação linear das três. Por conseguinte, existe um maior número de não-McNugget, e todos os inteiros maiores do que são números McNugget. Ou seja, todo inteiro positivo é um número McNugget, com o número finito de exceções:
1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 e 43
Assim, o maior número não é McNugget 43.
O facto de que qualquer número inteiro maior do que 43 é um número de McNugget pode ser visto, considerando as seguintes partições inteiras
Qualquer número inteiro maior pode ser obtida pela adição de um certo número de 6s à partição apropriado acima.
Além disso, uma verificação simples demonstra que 43 McNuggets não pode de fato ser comprados, como:
- caixas de 6 e 9 sozinho não pode formar 43 uma vez que estas só podem criar múltiplos de 3 (com a excepção de 3 si);
- incluindo uma única caixa de 20 não ajuda, como o restante requerido (23) também não é um múltiplo de três; e
- mais do que uma caixa de 20, complementada com caixas de 6 ou maior tamanho, obviamente, não pode conduzir a um total de 43 McNuggets.
Desde a introdução das caixas de 4 partes pepita feliz Refeição de tamanho, o maior número não é McNugget 11. Em países em que o tamanho de 9-peça é substituído com o tamanho de 10 partes, não há maior número não-McNugget, como qualquer número impar não podem ser feitas.
Referências[editar | editar código-fonte]
Rodrigo Gondim, Aritmética em retas e Cônicas, V Semana de Matemática da FFPNM-UPE, UPE-Nazaré da Mata, 2010