Jarras de Bezout (Solução)

O nome “Jarras de Bezout” está relacionado ao matemático Étienne Bézout(1730 — 1783), que trabalhou na teoria dos números e equações diofantinas, que envolvem problemas de encontrar inteiros que satisfaçam certas relações matemáticas. O problema das Jarras de Bezout é um exemplo prático desse tipo de problema.

A equação do tipo ax+by=c com a,b,c \in \mathbb{Z} é chamada de Equação Diofantina Linear (em duas incógnitas, no caso x e y). O Teorama de Bezout garante que existem infinitas soluções inteiras, ou seja, infinitos pares x, y \in \mathbb{Z} sempre que c for múltiplo do máximo divisor comum entre a e b. Em linguagem matemática, \exists x, y  \in \mathbb{Z} tal que ax+by=c sempre que mdc(a,b) \mid c ( o mdc(a,b) divide c) .

Como consequência direta desse teorema, sempre que a, b forem coprimos, isto é, mdc(a,b)=1, o problema tem solução para qualquer valor de c.

Para que entenda a relação, utilizar jarros de 7 e 5 litros para obter 1 litro, é o mesmo que resolver a seguinte equação:

5x + 7y = 1.

Como mdc(7,5)=1, a equação 5x + 7y = c, c \in \mathbb{Z} tem infinitas soluções pois mdc(7,5)=1 \mid c, e particularmente vale para c=1. Ou seja, existem infinitas formas de encher e esvaziar os jarros para obter 1 litro de água. Verificando que o total dentro dos dois jarros se altera apenas quando se enche ou esvazia um dos jarros, vamos analisar uma solução para o exemplo utilizado no applet :

1. Encha o jarro de 5 litros e transfira para o jarro de 7 litros, ficando 5 litros no jarro de 7 litros e  o  jarro de 5 litros vazio. (Observe que temos 5 litros de água no total:  5 \cdot 1 + 7 \cdot 0 = 5)
2. Encha novamente o jarro de 5 litros e transfira dois litros do jarro de 7 litros. (temos agora 10 litros no total, 3 no jarro de 5 litros e 7 no jarro de 7 litros: 5 \cdot 2  + 7 \cdot 0 = 10
3. Esvazie o jarro de 7 litros e transfira os 3 litros do jarro de 5 litros para o jarro de 7 litros, nesse passo, sobram 3 litros no jarro de 7 litros enquanto o jarro de 5 litros fica vazio, total 3 litros: 5 \cdot 2 - 7 \cdot 1 = 3
4. Pela terceira vez, encha o jarro de 5 litros e transfira 4 litros para o jarro de 7 litros, restando 1 litro no jarro de 5 litros e 7 no jarro de 7 litros: 5 \cdot 3 - 7 \cdot 1 = 8.
5. Finalmente, esvazie o jarro de 7 litros, restando apenas 1 litro no jarro de 5 litros: 5 \cdot 1 - 7 \cdot 2 =1.

Assim, uma solução para a equação 5x + 7y = 1 é (x,y)=(3,-2) que corresponde às ações anteriores em que o jarro de 5 litros foi enchido 3 vezes e o de 7 litros foi esvaziado 2 vezes.

Portanto, para jarros de capacidade de a e b litros sempre é possível obter c litros quando c for múltiplo de mdc(a,b). 

 E sobre o caso em que temos jarros de 2 e 4 litros, é possível obter 1 litro?

Veja que isso seria semelhante a resolver a equação 2x + 4y = 1. Observe que o mdc(4,2)=2 e que a equação pode ser reescrita como  2(x + 2y) = 1. Como x + 2y é um inteiro, de um lado temos um número par e do outro um número ímpar e isso é suficiente para convencer que não há solução inteira. 

Mas geralmente, dado ax + by = c, com a=mdc(a,b)q_1,  mdc(a,b)q_2:

mdc(a,b)q_1 x + mdc(a,b)q_2 y = c  \Rightarrow  q_1 x + q_2 y = \dfrac{c}{ mdc(a,b)}

Veja que do lado esquerdo da igualdade temos um número inteiro e necessariamente precisamos que mdc(a,b) divida c, caso contrário não teremos um número inteiro.