[Difícil] Use o algoritmo de Euclides estendido para encontrar todas as soluções inteiras positivas do problema a seguir:
Um professor deseja montar kits de materiais didáticos para seus alunos. Cada kit é composto por cadernos e canetas. Cadernos são vendidos em pacotes de 7 unidades e canetas em pacotes de 11 unidades. De quantas maneiras diferentes é possível comprar exatamente 100 itens (entre cadernos e canetas), usando apenas pacotes fechados de 7 e de 11 ?
Escreva a equação diofantina correspondente, encontre uma solução particular com o algoritmo de Euclides estendido e depois descreva todas as soluções inteiras positivas.
Passo 1
O enunciado pede que você conte de quantas maneiras diferentes é possível comprar exatamente
itens usando apenas pacotes de
unidades e de
unidades. Informações relevantes que temos:
- Pacotes de cadernos têm
unidades cada. - Pacotes de canetas têm
unidades cada. - Queremos comprar exatamente
itens no total. - Vamos chamar de
o número de pacotes de e de o número de pacotes de . - O enunciado pede explicitamente que você escreva a equação diofantina correspondente, encontre uma solução particular usando o algoritmo de Euclides estendido e descreva todas as soluções inteiras positivas (
, ).
A equação que modela o problema é, portanto:
Passo 2
Primeiro precisamos verificar se a equação tem solução inteira: isso depende do máximo divisor comum de
e
. Vamos calcular
usando o algoritmo de Euclides (divisões sucessivas) e, em seguida, obter uma combinação linear (a parte estendida).
Fazendo as divisões:
Como o último resto não nulo é
, temos
. Como
divide
, a equação tem soluções inteiras.
Agora a parte estendida: expressar
como combinação linear de
e
(back-substitution):
Da terceira linha temos
Da segunda linha
. Substituindo:
Da primeira linha
. Substituindo:
Portanto encontramos a combinação linear
Multiplicando ambos os lados por
obtemos uma solução particular da equação original:
Assim uma solução particular inteira é
(Esta é a solução particular obtida diretamente pelo algoritmo de Euclides estendido; é perfeitamente válida mesmo sendo negativa para
.)
Passo 3
Agora usamos a fórmula geral das soluções inteiras de uma equação linear diofantina. Se
e
é uma solução particular de
, então todas as soluções inteiras são dadas por
Como
, temos
Aqui a razão: adicionar
a
e subtrair
de
não altera o valor de
, porque
. O parâmetro inteiro
gera todas as soluções inteiras possíveis.
Passo 4
Agora vamos impor a condição de positividade inteira: queremos
e
.
Da fórmula geral:
Como
é inteiro, isso dá
Para
:
Como
é inteiro, isso dá
Combinando as duas desigualdades inteiras, obtemos
logo a única possibilidade é
.
Substituindo
na fórmula geral:
Verificação rápida:
. Ambas são positivas e inteiras.
Passo 5
Interpretação final: a única maneira de comprar exatamente
itens usando apenas pacotes de
e de
(com
inteiros positivos) é comprar
pacotes de
e
pacotes de
. Ou seja, existe exatamente uma solução inteira positiva.
Resposta
Equação diofantina:
Solução particular pelo Euclides estendido:
Soluções inteiras gerais:
Soluções inteiras positivas:
Número de maneiras diferentes:
Solução particular pelo Euclides estendido:
Soluções inteiras gerais:
Soluções inteiras positivas:
Número de maneiras diferentes: