João possui apenas moedas de 10 e 25 centavos, que juntas - FATEC 2012

Alternativa Correta: E) no mínimo 9 moedas dos dois tipos.

10x + 25y = 195
2x + 5y = 39

Se você tratar a equação como uma equação diofantina linear (ax + by = c):

Seja d o MDC(a,b). Se d for divisor de c, logo a equação assume soluções inteiras:

a = 2; b = 5;
MDC(2,5):
5 = 2•2 + 1
2 = 2•1
MDC(2,5) = 1

Como 1 divide 39, há soluções inteiras.

Parametrizando a função
x = x0 + (b/d)•t
y = y0 - (a/d)•t

Como a função está parametrizada, x0 e y0 são soluções particulares
Vamos resolver retroagindo a partir do MDC(2,5) para obter as soluções particulares.

1 = 5•(1) - 2•(2) [Multiplicando ambos os lados por 39]
5•(39) + 2•(-78) = 39
Logo x0 = -78 e y0 = 39 são uma solução particular para x e y.

Substitituindo x0 e y0 em x e y:
x = - 78 + (5/1)•t
x = - 78 + 5t
y = 39 - (2/1)•t
y = 39 - 2t

Como x > 0, y > 0
Para x:
-78 + 5t > 0
5t > 78
t > 15,6
t ≥ 16
Para y:

39 - 2t > 0
2t < 39
t < 19,5
t ≤ 19
Logo há solução inteira para t = {16,17,18,19}

Para t = 16
x = -78 + 5•16 = 2
y = 39 - 2•16 = 7
S1 = {2,7}
Para t = 17
x = -78 + 5•17 = 7
y = 39 - 2•17 = 5
S2 = {7,5}
Para t = 18
x = -78 + 5•18 = 12
y = 39 - 2•18 = 3
S3 = {12,3}
Para t = 19
x = -78 + 5•19 = 17
y = 39 - 2•19 = 1
S4 = {17,1}

Logo temos o seguinte conjunto de soluções:
S = {(2,7) , (7,5) , (12,3) e (17,1)}
Comparando o conjunto S com as alternativas:

a) Não é verdadeiro visto que dependendo da solução pode haver mais moedas de 10 do que de 25.
b) Não é verdadeiro visto que o máximo obtido será 18 moedas dos dois tipos, conforme a última solução.
c) Não é verdade visto que o máximo de moedas de 10 será 17, conforme última solução.
d) Não é verdade visto que o mínimo de moedas de 25 centavos será 1, conforme última solução.
e) Verdadeiro, pois a solução que dispõe o menor número de moedas, ou seja, a primeira solução, contém 9 moedas dos dois tipos.

Créditos da Resolução: Yahoo