Olimpíadas ⇒ (POTI) Frações Irredutíveis Tópico resolvido
Moderador: [ Moderadores TTB ]
-
- Última visita: 31-12-69
Jun 2020
15
16:35
(POTI) Frações Irredutíveis
A sequência [tex3]F_n[/tex3]
[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]
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]
-
- 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
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.
-
- 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
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.
Última edição: Tassandro (Ter 16 Jun, 2020 21:42). Total de 4 vezes.
Dias de luta, dias de glória.
-
- Ú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.
Última edição: Deleted User 24633 (Ter 16 Jun, 2020 22:31). Total de 3 vezes.
-
- 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
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.
-
- Ú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: ↑Ter 16 Jun, 2020 21:56pedro1729,
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]
-
- 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
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 msg
-
- 1 Respostas
- 2080 Exibições
-
Última msg por Carlosft57
-
- 1 Respostas
- 2071 Exibições
-
Última msg por Carlosft57
-
- 1 Respostas
- 2194 Exibições
-
Última msg por Carlosft57
-
- 1 Respostas
- 1190 Exibições
-
Última msg por LostWalker
-
- 4 Respostas
- 978 Exibições
-
Última msg por Stich