[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 100 itens usando apenas pacotes de 7 unidades e de 11 unidades. Informações relevantes que temos:
  • Pacotes de cadernos têm 7 unidades cada.
  • Pacotes de canetas têm 11 unidades cada.
  • Queremos comprar exatamente 100 itens no total.
  • Vamos chamar de x o número de pacotes de 7 e de y o número de pacotes de 11.
  • 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 ( x>0, y>0).
A equação que modela o problema é, portanto:
7x + 11y = 100.

Passo 2

Primeiro precisamos verificar se a equação tem solução inteira: isso depende do máximo divisor comum de 7 e 11. Vamos calcular \gcd(7,11) usando o algoritmo de Euclides (divisões sucessivas) e, em seguida, obter uma combinação linear (a parte estendida).
Fazendo as divisões:
11 = 1\cdot 7 + 4,
7 = 1\cdot 4 + 3,
4 = 1\cdot 3 + 1,
3 = 3\cdot 1 + 0.
Como o último resto não nulo é 1, temos \gcd(7,11)=1. Como 1 divide 100, a equação tem soluções inteiras.
Agora a parte estendida: expressar 1 como combinação linear de 7 e 11 (back-substitution):
Da terceira linha temos
1 = 4 - 1\cdot 3.
Da segunda linha 3 = 7 - 1\cdot 4. Substituindo:
1 = 4 - 1\cdot (7 - 1\cdot 4) = 2\cdot 4 - 1\cdot 7.
Da primeira linha 4 = 11 - 1\cdot 7. Substituindo:
1 = 2\cdot (11 - 1\cdot 7) - 1\cdot 7 = 2\cdot 11 - 3\cdot 7.
Portanto encontramos a combinação linear
-3\cdot 7 + 2\cdot 11 = 1.
Multiplicando ambos os lados por 100 obtemos uma solução particular da equação original:
-300\cdot 7 + 200\cdot 11 = 100.
Assim uma solução particular inteira é
x_0 = -300,\qquad y_0 = 200.
(Esta é a solução particular obtida diretamente pelo algoritmo de Euclides estendido; é perfeitamente válida mesmo sendo negativa para x_0.)

Passo 3

Agora usamos a fórmula geral das soluções inteiras de uma equação linear diofantina. Se d=\gcd(7,11)=1 e (x_0,y_0) é uma solução particular de 7x+11y=100, então todas as soluções inteiras são dadas por
x = x_0 + \frac{11}{d}\,t,\qquad y = y_0 - \frac{7}{d}\,t,\qquad t\in\mathbb{Z}.
Como d=1, temos
x = -300 + 11t,\qquad y = 200 - 7t,\qquad t\in\mathbb{Z}.
Aqui a razão: adicionar 11 a x e subtrair 7 de y não altera o valor de 7x+11y, porque 7\cdot 11 - 11\cdot 7 = 0. O parâmetro inteiro t gera todas as soluções inteiras possíveis.

Passo 4

Agora vamos impor a condição de positividade inteira: queremos x>0 e y>0.
Da fórmula geral:
x>0 \Longrightarrow -300 + 11t > 0 \Longrightarrow 11t > 300 \Longrightarrow t > \frac{300}{11}.
Como t é inteiro, isso dá
t \ge 28 \quad\text{(pois }\tfrac{300}{11}\approx 27{,}27\text{)}.
Para y>0:
y>0 \Longrightarrow 200 - 7t > 0 \Longrightarrow 7t < 200 \Longrightarrow t < \frac{200}{7}.
Como t é inteiro, isso dá
t \le 28 \quad\text{(pois }\tfrac{200}{7}\approx 28{,}57\text{)}.
Combinando as duas desigualdades inteiras, obtemos
28 \le t \le 28,
logo a única possibilidade é t=28.
Substituindo t=28 na fórmula geral:
x = -300 + 11\cdot 28 = -300 + 308 = 8,
y = 200 - 7\cdot 28 = 200 - 196 = 4.
Verificação rápida: 7\cdot 8 + 11\cdot 4 = 56 + 44 = 100. Ambas são positivas e inteiras.

Passo 5

Interpretação final: a única maneira de comprar exatamente 100 itens usando apenas pacotes de 7 e de 11 (com x,y inteiros positivos) é comprar 8 pacotes de 7 e 4 pacotes de 11. Ou seja, existe exatamente uma solução inteira positiva.

Resposta

Equação diofantina: 7x+11y=100
Solução particular pelo Euclides estendido: x_0=-300,\\ y_0=200
Soluções inteiras gerais: x=-300+11t,\\ y=200-7t,\\ t\in\mathbb{Z}
Soluções inteiras positivas: (x,y)=(8,4)
Número de maneiras diferentes: 1

Exercícios relacionados