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
editarSe 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- 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
editarRodrigo Gondim, Aritmética em retas e Cônicas, V Semana de Matemática da FFPNM-UPE, UPE-Nazaré da Mata, 2010