Olimpíadas ⇒ (Cone Sul - 2010) Frações Irredutíveis Tópico resolvido

[Alexander]

Pedro tem que escolher duas frações irredutíveis, cada uma com numerador e denominador positivos, tais que:

• A soma das duas frações seja igual a 2.
• A soma dos numeradores das duas frações seja igual a 1000.

De quantas maneiras Pedro pode fazer isso?

[poti]

Essa é chata, pelo menos da forma que enxerguei.

[tex3]\begin{cases}\frac{a}{b} + \frac{c}{d} = 2\\a + c = 1000\\b + d \leq 500\\mdc(a,b) = 1\\mdc(c,d)=1\end{cases}[/tex3]

Para a segunda equação nós temos [tex3]\left(\begin{array}{cc} 1000 + 1 \\ 1 \end{array}\right) = 1001[/tex3] soluções não-inteiras.
Para a terceira equação, nós temos que analisar cada caso.

[tex3]b + d = 0 \rightarrow \left(\begin{array}{cc} 0 + 1 \\ 1 \end{array}\right)[/tex3]
[tex3]b + d = 1 \rightarrow \left(\begin{array}{cc} 1 + 1 \\ 1 \end{array}\right)[/tex3]
[tex3]b + d = 2 \rightarrow \left(\begin{array}{cc} 2 + 1 \\ 1 \end{array}\right)[/tex3]
.
.
[tex3]b+d = 500 \rightarrow \left(\begin{array}{cc} 500 + 1 \\ 1 \end{array}\right)[/tex3]

Basta somar os números de soluções, o que fica fácil pelo Teorema das Colunas:
[tex3]\left(\begin{array}{cc} 0 + 1 \\ 1 \end{array}\right) + \left(\begin{array}{cc} 1 + 1 \\ 1 \end{array}\right) + \left(\begin{array}{cc} 2 + 1 \\ 1 \end{array}\right) + ... + \left(\begin{array}{cc} 500 + 1 \\ 1 \end{array}\right) = \left(\begin{array}{cc} 502 \\ 2 \end{array}\right) = 125751[/tex3] soluções não-inteiras.

Estou tentando associar os MDCs pra diminuir o número de soluções, mas nada. Talvez o uso da Função Totiente ajude, mas também não enxerguei aonde.

Quem sabe mais tarde...

[Alexander]

Muito obrigado Poti!

Deu pra dar uma (grande) luz, não fazia a menor ideia de como começar a resolver isso.

[Dick]

[tex3]\frac{a}{b}+\frac{c}{d}=2[/tex3]
[tex3]a+c=1000[/tex3]
Se duas frações irredutíveis somadas dão um número inteiro, então seus denominadores são iguais. Portanto b=d.
[tex3]a+c=2b\rightarrow 1000=2b\rightarrow b=d=500=2^2.5^3[/tex3]

Agora encontraremos todos a com [tex3]1\leq a \leq 999[/tex3]; tais que [tex3](a,500)=1 , (1000-a,500)=1.[/tex3]
Assim os valores de a são tantos quanto os números não divisíveis por 2 e 5 entre 1 e 999:
[tex3]1000-(\frac{1000}{2}+\frac{1000}{5}-\frac{1000}{2.5}) = 1000-500-200+100 = 400[/tex3]
Por simetria de condições [tex3](a,c)=(c,a)[/tex3]; então as possibilidades caem pela metade e a resposta é:

Pedro poderá fazer de 200 maneiras diferentes.