Flashcard FC303442
Como resolver uma equação linear diofantina do tipo Ax+By=C em inteiros não-negativos e determinar o total de jogadas n=x+y?
Outros Exercícios de Lógica
FGV · 2024
Como resolver uma equação linear diofantina do tipo Ax+By=C em inteiros não-negativos e determinar o total de jogadas n=x+y?
Mostrar resposta e comentário
Resposta
Montar \(Ax+By=C\), verificar \(d=\gcd(A,B)\) com \(d\mid C\), obter uma solução particular e a solução geral \(x=x_0+\frac{B}{d}t,\;y=y_0-\frac{A}{d}t\); impor \(x,y\ge0\) e então calcular \(n=x+y\).Explicação:
1) Calcule \(d=\gcd(A,B)\). Se \(d\nmid C\) não há solução inteira.
2) Ache uma solução particular \((x_0,y_0)\) de \(Ax+By=C\).
3) Escreva a solução geral: \(x=x_0+\dfrac{B}{d}t,\;y=y_0-\dfrac{A}{d}t\) para \(t\in\mathbb{Z}\).
4) Determine os valores de \(t\) que garantem \(x\ge0\) e \(y\ge0\).
5) Para o total de jogadas calcule \(n=x+y\) na solução escolhida (respeitando qualquer restrição adicional, ex.: último movimento deve ser avanço ⇒ exigir \(x\ge1\)).
Exemplo:
Considere movimentos de +7 e -4 que devem resultar em 50 casas: \(7x-4y=50\).
\(d=\gcd(7,4)=1\), \(1\mid50\) ⇒ há solução.
Resolva modularmente: \(7x\equiv50\pmod4\Rightarrow 3x\equiv2\pmod4\Rightarrow x\equiv2\pmod4\).
Logo \(x=2+4t\). Substituindo: \(y=\dfrac{7x-50}{4}=\dfrac{7(2+4t)-50}{4}=-9+7t\).
Impondo \(y\ge0\) ⇒ \(-9+7t\ge0\Rightarrow t\ge2\). Com \(t=2\) temos \(x=10,\;y=5\) e então \(n=10+5=15\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300532
Conteúdo do catálogo FC Concursos · Atualizado em