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]
Olá, Comunidade!
Vocês devem ter notado que o site ficou um período fora do ar (do dia 26 até o dia 30 de maio de 2024).
Consegui recuperar tudo, e ainda fiz um UPGRADE no servidor! Agora estamos em um servidor dedicado no BRASIL!
Isso vai fazer com que o acesso fique mais rápido (espero
)
Já arrumei os principais bugs que aparecem em uma atualização!
Mas, se você encontrar alguma coisa diferente, que não funciona direito, me envie uma MP avisando que eu arranjo um tempo pra arrumar!
Vamos crescer essa comunidade juntos
Grande abraço a todos,
Prof. Caju
Vocês devem ter notado que o site ficou um período fora do ar (do dia 26 até o dia 30 de maio de 2024).
Consegui recuperar tudo, e ainda fiz um UPGRADE no servidor! Agora estamos em um servidor dedicado no BRASIL!
Isso vai fazer com que o acesso fique mais rápido (espero
)Já arrumei os principais bugs que aparecem em uma atualização!
Mas, se você encontrar alguma coisa diferente, que não funciona direito, me envie uma MP avisando que eu arranjo um tempo pra arrumar!
Vamos crescer essa comunidade juntos
Grande abraço a todos,
Prof. Caju
Olimpíadas ⇒ (POTI) Frações Irredutíveis Tópico resolvido
Moderador: [ Moderadores TTB ]
-
Tassandro
- Mensagens: 1905
- Registrado em: 15 Fev 2020, 17:01
- Última visita: 03-10-23
- Localização: Teresina, PI.
- Agradeceu: 129 vezes
- Agradeceram: 136 vezes
Jun 2020
15
16:57
Re: (POTI) Frações Irredutíveis
pedro1729,
Aqui tem uma demonstração por vetores.
https://en.m.wikipedia.org/wiki/Farey_sequence
Amanhã eu tento fazer essa...
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.
-
Tassandro
- Mensagens: 1905
- Registrado em: 15 Fev 2020, 17:01
- Última visita: 03-10-23
- Localização: Teresina, PI.
- Agradeceu: 129 vezes
- Agradeceram: 136 vezes
Jun 2020
16
18:54
Re: (POTI) Frações Irredutíveis
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.
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.
Editado pela última vez por Tassandro em 16 Jun 2020, 21:42, em um total de 4 vezes.
Dias de luta, dias de glória.
-
Deleted User 24633
- Última visita: 31-12-69
Jun 2020
16
21:15
Re: (POTI) Frações Irredutíveis
Não entendi essa parte:
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.
Editado pela última vez por Deleted User 24633 em 16 Jun 2020, 22:31, em um total de 3 vezes.
-
Tassandro
- Mensagens: 1905
- Registrado em: 15 Fev 2020, 17:01
- Última visita: 03-10-23
- Localização: Teresina, PI.
- Agradeceu: 129 vezes
- Agradeceram: 136 vezes
Jun 2020
16
21:56
Re: (POTI) Frações Irredutíveis
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!
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.
-
Deleted User 24633
- Última visita: 31-12-69
Jun 2020
16
22:30
Re: (POTI) Frações Irredutíveis
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.Tassandro escreveu: ↑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!
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]
-
Tassandro
- Mensagens: 1905
- Registrado em: 15 Fev 2020, 17:01
- Última visita: 03-10-23
- Localização: Teresina, PI.
- Agradeceu: 129 vezes
- Agradeceram: 136 vezes
Jun 2020
17
07:49
Re: (POTI) Frações Irredutíveis
pedro1729,
Excelente! Obrigado por completar a solução! Não havia percebido que deixei esse detalhe passar!
Tamo junto
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.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última mensagem
-
- 2 Respostas
- 1293 Exibições
-
Última mensagem por jomatlove
-
- 3 Respostas
- 1431 Exibições
-
Última mensagem por Tassandro
-
-
Nova mensagem (Revista Quantum - Jornal Kvant) Frações Irredutíveis
por Deleted User 24633 » » em Olimpíadas - 1 Respostas
- 1054 Exibições
-
Última mensagem por Tassandro
-
-
- 1 Respostas
- 3975 Exibições
-
Última mensagem por Carlosft57
-
- 1 Respostas
- 3859 Exibições
-
Última mensagem por Carlosft57
