Olimpíadas ⇒ (Argentina - 97) Equações diofantinas lineares Tópico resolvido

[Auto Excluído (ID: 23699)]

Quantos números entre 1 e 1000 inclusive podem decompor-se em soma de um múltiplo positivo de 7 mais um múltiplo positivo de 4?

Resposta

---

972

[Auto Excluído (ID: 24633)]

Acho que teu gabarito tá errado.

---

Todo número maior que [tex3]28[/tex3] satisfaz o enunciado.

A prova segue o mesmo raciocínio empregado nesta questão
Desde que [tex3]\operatorname{mdc}(7,4) = 1[/tex3] qualquer inteiro pode ser expresso como soma de um múltiplo de [tex3]7[/tex3] com um múltiplo de [tex3]4;[/tex3] só precisamos saber para quais deles esse múltiplo de [tex3]7[/tex3] e de [tex3]4[/tex3] são ambos positivos.

Considere a equação diofantina (nos inteiros) em [tex3]x,y:[/tex3]

[tex3]7x + 4y = p~(*)[/tex3]

onde [tex3]p[/tex3] é um inteiro positivo; queremos saber para quais valores de [tex3]p[/tex3] essa equação admite uma solução nos inteiros positivos.
A equação [tex3](*)[/tex3] admite uma solução trivial nos inteiros [tex3](x = -p;~y=2p);[/tex3] logo todas as suas soluções (em par ordenado [tex3](x,y)[/tex3]) são da forma [tex3]( -p +4k;~ 2p -7k)[/tex3] onde [tex3]k[/tex3] representa um inteiro qualquer. Dessa forma, a equação possuir solução em inteiros positivos é análogo ao seguinte sistema possuir solução:
[tex3]\begin{cases} -p + 4k >0 \\ 2p - 7k >0 \end{cases} \iff \dfrac{p}{4} < k < \dfrac{2p}{7}.[/tex3]
Queremos saber para quais valores de [tex3]p[/tex3] esse sistema possui solução, ou seja, existe inteiro entre [tex3]\dfrac{p}{4}[/tex3] e [tex3]\dfrac{2p}{7}.[/tex3]

Note que se [tex3]\dfrac{2p}{7} - \dfrac{p}{4} > 1[/tex3] estaremos feitos, pois entre dois números que distam mais que uma unidade sempre existe um inteiro. Temos que [tex3]\dfrac{p}{28} = \dfrac{2p}{7} - \dfrac{p}{4} > 1 \iff p > 28.[/tex3] Ou seja qualquer número maior que [tex3]28[/tex3] está de acordo com o que queremos. Então temos [tex3]1.000 - 28 = 972[/tex3] números satisfazendo o enunciado entre [tex3]28[/tex3] e [tex3]1.000[/tex3] (incluindo 1.000)

Agora precisamos saber quantos inteiros positivos menores ou iguais a [tex3]28[/tex3] estão de acordo com o que desejamos.
Eles são

• [tex3]7 \cdot (1) + 4 \cdot (1) =11;[/tex3]
• [tex3]7 \cdot (1) + 4 \cdot (2) =15;[/tex3]
• [tex3]7 \cdot (1) + 4 \cdot (3) =19;[/tex3]
• [tex3]7 \cdot (1) + 4 \cdot (4) =23;[/tex3]
• [tex3]7 \cdot (1) + 4 \cdot (5) =27[/tex3]
• [tex3]7 \cdot (2) + 4 \cdot (1) =18;[/tex3]
• [tex3]7 \cdot (2) + 4 \cdot (2) =22;[/tex3]
• [tex3]7 \cdot (2) + 4 \cdot (3) =26;[/tex3]
• [tex3]7 \cdot (3) + 4 \cdot (1) =25;[/tex3]

num total de [tex3]9[/tex3] números. Então a resposta à nossa pergunta é [tex3]972 + 9 = 981[/tex3]