Sexta, 30 Março 2018 20:41

QUESTÕES PUC-RIO - K-ÉSIMO NÚMERO DA SEQUÊNCIA! (A REENCARNAÇÃO)

Escrito por

Dando sequência as Questões Puc-Rio, hoje veremos uma explicação da Sequência de Farey.

 Essa é a chamada sequência de Farey de ordem N (F(N)).

a/b pertence a F(N) <==> 0 <= a <= b <= N e mdc(a,b) = 1.

Além disso, se o k-ésimo termo é a/b e o (k+1)-ésimo eh c/d então:
a/b < c/d e bc - ad = 1, ou seja:
c/d = a/b + 1/(bd).

Apesar de não fornecer uma fórmula, o algoritmo abaixo (descrito em "An Introduction to the Theory of Numbers" - Hardy-Wright - sec. 3.4) permite determinar o c/d conhecendo-se a/b:

Como mdc(a,b) =1, existem inteiros x e y tais que bx - ay = 1.

Se (p,q) é uma solução particular dessa equação diofantina (ou seja, bp -aq = 1) então, a solução geral será:
x = p + a*k
y = q + b*k (k em Z)

Podemos escolher k de modo que N - b < q + b*k = y <= N.

Dessa forma, teremos uma solução (x,y) tal que:
mdc(x,y) = 1 e N - b < y <= N ==>
x/y pertence a F(N) e x/y = a/b + 1/(by) > a/b.

Vamos provar, por absurdo, que x/y = c/d.

Suponhamos que x/y <> c/d. Então, x/y > c/d ==> x/y - c/d = (dx - cy)/(dy) >= 1/(dy)

Por outro lado,
c/d - a/b = (bc - ad)/(bd) = 1/(bd)

Assim:
1/(by) = (bx - ay)/(by) = x/y - a/b >= 1/(dy) + 1/(bd) =
= (b + y)/(bdy) > N/(bdy) >= 1/(by) ==> contradição ⇒ x/y = c/d

 

Confira a discussão em: http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200304/msg00002.html

Ler 87 vezes Última modificação em Quinta, 12 Abril 2018 19:59

Deixe um comentário

Certifique-se de preencher os campos indicados com (*). Não é permitido código HTML.