Olimpíadas(POTI) Frações Irredutíveis Tópico resolvido

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Autor do Tópico
Deleted User 24633
6 - Doutor
Última visita: 31-12-69
Jun 2020 15 16:35

(POTI) Frações Irredutíveis

Mensagem não lida por Deleted User 24633 »

A sequência [tex3]F_n[/tex3] de Farey é a sequência de todos as frações irredutíveis [tex3]\dfrac{a}{b}[/tex3] com [tex3]0 ≤ a ≤ b ≤ n[/tex3] arranjados em ordem crescente.
[tex3]F_1 = \{\frac{0}{1}, \frac{1}{1}\}[/tex3]
[tex3]F_2 = \{\frac{0}{1}, \frac{1}{2}, \frac{1}{1}\}[/tex3]
[tex3]F_3 = \{\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}\}[/tex3]
[tex3]F_4 = \{\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}\}[/tex3]
[tex3]F_5 = \{\frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}\}[/tex3]
[tex3]F_6 = \{\frac{0}{1}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{1}{1}\}[/tex3]
Claramente, toda fraçã [tex3]\dfrac{a}{b}< 1[/tex3] com [tex3]mdc(a, b) = 1[/tex3] , está em algum [tex3]F_n[/tex3] .
Mostre que se [tex3]\dfrac{m}{n}[/tex3] e [tex3]\dfrac{m′}{n′}[/tex3] são frações consecutivas em [tex3]F_n[/tex3] temos [tex3]|mn′ − nm′| = 1.[/tex3]




Avatar do usuário
Tassandro
5 - Mestre
Mensagens: 1905
Registrado em: Sáb 15 Fev, 2020 17:01
Última visita: 03-10-23
Localização: Teresina, PI.
Jun 2020 15 16:57

Re: (POTI) Frações Irredutíveis

Mensagem não lida por Tassandro »

pedro1729,
Aqui tem uma demonstração por vetores.
https://en.m.wikipedia.org/wiki/Farey_sequence
Amanhã eu tento fazer essa...



Dias de luta, dias de glória.

Avatar do usuário
Tassandro
5 - Mestre
Mensagens: 1905
Registrado em: Sáb 15 Fev, 2020 17:01
Última visita: 03-10-23
Localização: Teresina, PI.
Jun 2020 16 18:54

Re: (POTI) Frações Irredutíveis

Mensagem não lida por Tassandro »

pedro1729,
Podemos fazer isso com nada mais do que indução e resolver um sistema de duas equações em duas incógnitas. Para a etapa de indução, suponha que [tex3]\frac {a} b <\frac {c} d[/tex3] sejam vizinhos em [tex3]F_n[/tex3] e que [tex3]bc-ad = 1 [/tex3] . Se [tex3]\frac {a} b[/tex3] e [tex3]\frac {c} d[/tex3] são vizinhos em [tex3]F_ {n + 1}[/tex3] , não há nada a provar. Caso contrário, existe algum [tex3]\frac {k} \ell[/tex3] entre [tex3]\frac {a} b[/tex3] e [tex3]\frac {c} d [/tex3] em [tex3]F_ {n + 1}[/tex3] . Suponha que possamos mostrar que [tex3]\frac {k}\ell = \frac {a + c} {b + d}[/tex3] ; então [tex3]bk-a \ell = b (a + c) -a (b + d) = bc-ad = 1[/tex3] e [tex3]\ell c-kd = (b + d) c- (a + c) d = bc-ad = 1 \;,[/tex3] como desejado. Para mostrar que [tex3]\frac {k} \ell = \frac {a + c} {b + d} [/tex3] , observe primeiro que [tex3]\frac {a + c} {b + d} - \frac {a} b = \frac {bc-ad} {b (b + d)}> 0[/tex3] e [tex3]\frac {c} d- \frac {a + c} {b + d} = \frac {bc-ad} {d (b + d)}> 0 \;, [/tex3] então [tex3]\frac {a} b <\frac {a + c} {b + d} <\frac {c} d [/tex3] .
Em qualquer caso, podemos resolver o sistema
[tex3]ax + cy = k \\ bx + dy = \ell [/tex3]
Ao multiplicar a primeira equação por d e a segunda por c e subtrair a primeira da segunda vem que [tex3]x = (bc-ad) x = c \ell-dk> 0 \;, [/tex3] e, da mesma forma, descobrimos que [tex3]y = bk-a \ell> 0 [/tex3] (As desigualdades seguem de [tex3]\frac {a} b <\frac {k} \ell <\frac {c} d [/tex3] .)
Portanto, existem números inteiros positivos x e y tais que [tex3]\frac {k} \ell = \frac {ax + cy} {bx + dy}[/tex3] , o que implica que [tex3]\ell = bx + dy \ge b + d [/tex3] . Em particular, se houver qualquer fração entre [tex3]\frac {a} b[/tex3] e [tex3]\frac {c} d [/tex3] com um denominador menor ou igual a [tex3]n + 1 [/tex3] , a sua mediana será [tex3]\frac {a + c} {b + d} [/tex3] .
Nota : substitui por a, b, c e d para facilitar minha vida digitando.
Última edição: Tassandro (Ter 16 Jun, 2020 21:42). Total de 4 vezes.


Dias de luta, dias de glória.

Autor do Tópico
Deleted User 24633
6 - Doutor
Última visita: 31-12-69
Jun 2020 16 21:15

Re: (POTI) Frações Irredutíveis

Mensagem não lida por Deleted User 24633 »

Não entendi essa parte:
Tassandro escreveu:
Ter 16 Jun, 2020 18:54
pedro1729,
Portanto, existem números inteiros positivos x e y tais que [tex3]\frac {k} \ell = \frac {ax + cy} {bx + dy}[/tex3] , o que implica que [tex3]\ell = bx + dy \ge b + d [/tex3]
Isso seria verdade se e só se [tex3](ax+cy,bx+dy)=1[/tex3] , mas eu não consegui prová-lo só com a hipótese de que [tex3](a,b)=1[/tex3] e [tex3](c,d)=1[/tex3] , ou seja, não entendi porque a fração [tex3]\dfrac{ax+cy}{bx+dy}[/tex3] é irredutível.
Última edição: Deleted User 24633 (Ter 16 Jun, 2020 22:31). Total de 3 vezes.



Avatar do usuário
Tassandro
5 - Mestre
Mensagens: 1905
Registrado em: Sáb 15 Fev, 2020 17:01
Última visita: 03-10-23
Localização: Teresina, PI.
Jun 2020 16 21:56

Re: (POTI) Frações Irredutíveis

Mensagem não lida por Tassandro »

pedro1729,
Isso foi uma consequência da hipótese de que o sistema
[tex3]ax + cy = k \\ bx + dy = \ell [/tex3]
possui solução. Por hipótese, [tex3]k[/tex3] e [tex3]\ell[/tex3] são primos entre si. Assim, se esse sistema tiver solução, então [tex3]ax+cy[/tex3] e [tex3]bx+dy[/tex3] serão, obviamente, primos entre si. Mostramos que o sistema tem solução, então estamos feitos!


Dias de luta, dias de glória.

Autor do Tópico
Deleted User 24633
6 - Doutor
Última visita: 31-12-69
Jun 2020 16 22:30

Re: (POTI) Frações Irredutíveis

Mensagem não lida por Deleted User 24633 »

Tassandro escreveu:
Ter 16 Jun, 2020 21:56
pedro1729,
Isso foi uma consequência da hipótese de que o sistema
[tex3]ax + cy = k \\ bx + dy = \ell [/tex3]
possui solução. Por hipótese, [tex3]k[/tex3] e [tex3]\ell[/tex3] são primos entre si. Assim, se esse sistema tiver solução, então [tex3]ax+cy[/tex3] e [tex3]bx+dy[/tex3] serão, obviamente, primos entre si. Mostramos que o sistema tem solução, então estamos feitos!
Nesse caso a sua hipótese de indução não é sólida. Pois não se pode supor que [tex3](1,1)[/tex3] é a solução do sistema.
Então, se eu não estou muito enganado, o seu raciocínio está incompleto!
faltou:
Se [tex3]\dfrac{k}{l}=\dfrac{a+c}{b+d}[/tex3] é a fração anterior a [tex3]\dfrac{c}{d}[/tex3] e [tex3](1,1)[/tex3] é a solução nada temos a provar já que, como foi provado anteriormente, caso isso aconteça [tex3]cl-dk=1[/tex3] e [tex3]bk-al=1[/tex3] . Caso contrário, considere a fração [tex3]\dfrac{a' }{b' }[/tex3] , onde [tex3]a'=a+c, b'=b+d[/tex3] e [tex3]\dfrac{k'}{l'}=\dfrac{a'+c}{b'+d}[/tex3] se essa satisfaz as relações anteriores, nada temos a provar,
caso contrário, defina [tex3]a''=a'+c,b''=b+d[/tex3] e assim suscetivamente.
Assim, por decadência infinita, como a sequência [tex3]F_n[/tex3] é limitada ( se considerarmos só as frações [tex3]\dfrac{a}{b},[/tex3] com [tex3]0 \le a\le b\le n[/tex3] sem a restrição de que [tex3](a,b)=1[/tex3] isso já é limitado) este processo terá de terminar um dia [tex3]\blacksquare [/tex3]



Avatar do usuário
Tassandro
5 - Mestre
Mensagens: 1905
Registrado em: Sáb 15 Fev, 2020 17:01
Última visita: 03-10-23
Localização: Teresina, PI.
Jun 2020 17 07:49

Re: (POTI) Frações Irredutíveis

Mensagem não lida por Tassandro »

pedro1729,
Excelente! Obrigado por completar a solução! Não havia percebido que deixei esse detalhe passar!
Tamo junto 👊



Dias de luta, dias de glória.

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”