Re: [obm-l] Lista 4 Cone Sul 2008
2014-05-20 8:05 GMT-03:00 Bernardo Freitas Paulo da Costa bernardo...@gmail.com: 2014-05-19 23:13 GMT-03:00 terence thirteen peterdirich...@gmail.com: Ah, é claro! Uma desigualdade deve resolver! n! cresce muito mais rápido que n^2007, então f é estritamente decrescente e negativa a partir de certo ponto. Assim ela é certamente injetiva daí, pois ab daria f(a)f(b). f(a) f(b), mas é isso. O problema agora é antes deste ponto... Bom, usando Stirling, n! n^2007 mais ou menos para n ~ 2007. Mais exatamente, n! n^n / e^n, e esse último é n^2007 = n^(n - 2007) e^n = (n - 2007) log(n) n = x * log(x + 2007) 2007 + x Como log(2000) log(729) = log(3^6) 6 log(3) 6, basta 6x 2007 + x ou seja x 2007/5 = 401 Restam 2500 casos para fazer na mão ;-)) Bom, juntando as idéias de divisibilidade e assintótico, sai. Suponha que 0 = b a 2500, que é o único caso que resta. Se b não divide a, mas f(b) = f(a), temos b^2007 - b! = a^2007 - a! = a! - b! + b^2007 = a^2007. Como b divide a! (pois a b), isso dá b | a^2007. Assim, os fatores primos de b aparecem nos fatores primos de a. Bom, vamos nos livrar de um caso simples: b = 1. Ou seja, não existe a 1 tal que a^2007 = a!: Note que (a-1) divide a! (e a-1 diferente de zero pela nossa hipótese da ordem do a e do b). Mas (a-1) é primo com a. Logo ele não divide a^2007. Assim, temos que a = AC e b = BC, onde A e B são primos entre si, C é um fator comum maior do que 1 (por isso que a gente se livrou do caso b = 1 antes). Rearrumando as coisas, temos (AC)! - (BC)! = C^2007 * (A^2007 - B^2007), logo C^2007 divide (AC)! - (BC)!. Como A B, temos que C divide (AC)!/(BC)! = AC * (AC -1) * ... * (AC - BC + 1), logo C não divide (AC)!/(BC)! - 1. Note que isso vale, na verdade, para qualquer fator primo (digamos p) de C. Assim, p^2007 divide (AC)! - (BC)! = (BC)! [ (AC)! / (BC)! - 1 ], logo p^2007 divide (BC)! = b!. Ou seja, se p é um fator de b, p^2007 divide b! Mas qualquer primo p aparece menos de b vezes em b!, para qualquer b: esse número de vezes é igual a [b/p] + [b/p^2] + ... + [b/p^n] + ... onde a soma é finita (alguma hora, p^n b, e as partes inteiras vão dar zero). Essa soma também é menor do que b/p * (1/(1-1/p)) (soma da PG sem as partes inteiras) = b / (p - 1) = b (e só poderia ser igual quando p = 2, e nesse caso, o mais próximo que chega é (b-1) porque a série é finita, e precisa de termos fracionários para dar exatamente b/(p-1)). Agora, note que a 2500, e a = AC, com C 1, implica que a 1250. Idem para b a. Assim, p aparece no máximo 1250 vezes em b!, o que é absurdo pois queríamos que p^2007 | b! Talvez tenha algo sem usar explicitamente o 2007 e as estimativas de Stirling, mas saiu ! Abraços -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] Lista 4 Cone Sul 2008
Só tem que lembrar que Stirlinbg é pesado demais pra galera. Talvez uma desigualdade mais bobinha que saia com indução... Em 21 de maio de 2014 11:06, Bernardo Freitas Paulo da Costa bernardo...@gmail.com escreveu: 2014-05-20 8:05 GMT-03:00 Bernardo Freitas Paulo da Costa bernardo...@gmail.com: 2014-05-19 23:13 GMT-03:00 terence thirteen peterdirich...@gmail.com: Ah, é claro! Uma desigualdade deve resolver! n! cresce muito mais rápido que n^2007, então f é estritamente decrescente e negativa a partir de certo ponto. Assim ela é certamente injetiva daí, pois ab daria f(a)f(b). f(a) f(b), mas é isso. O problema agora é antes deste ponto... Bom, usando Stirling, n! n^2007 mais ou menos para n ~ 2007. Mais exatamente, n! n^n / e^n, e esse último é n^2007 = n^(n - 2007) e^n = (n - 2007) log(n) n = x * log(x + 2007) 2007 + x Como log(2000) log(729) = log(3^6) 6 log(3) 6, basta 6x 2007 + x ou seja x 2007/5 = 401 Restam 2500 casos para fazer na mão ;-)) Bom, juntando as idéias de divisibilidade e assintótico, sai. Suponha que 0 = b a 2500, que é o único caso que resta. Se b não divide a, mas f(b) = f(a), temos b^2007 - b! = a^2007 - a! = a! - b! + b^2007 = a^2007. Como b divide a! (pois a b), isso dá b | a^2007. Assim, os fatores primos de b aparecem nos fatores primos de a. Bom, vamos nos livrar de um caso simples: b = 1. Ou seja, não existe a 1 tal que a^2007 = a!: Note que (a-1) divide a! (e a-1 diferente de zero pela nossa hipótese da ordem do a e do b). Mas (a-1) é primo com a. Logo ele não divide a^2007. Assim, temos que a = AC e b = BC, onde A e B são primos entre si, C é um fator comum maior do que 1 (por isso que a gente se livrou do caso b = 1 antes). Rearrumando as coisas, temos (AC)! - (BC)! = C^2007 * (A^2007 - B^2007), logo C^2007 divide (AC)! - (BC)!. Como A B, temos que C divide (AC)!/(BC)! = AC * (AC -1) * ... * (AC - BC + 1), logo C não divide (AC)!/(BC)! - 1. Note que isso vale, na verdade, para qualquer fator primo (digamos p) de C. Assim, p^2007 divide (AC)! - (BC)! = (BC)! [ (AC)! / (BC)! - 1 ], logo p^2007 divide (BC)! = b!. Ou seja, se p é um fator de b, p^2007 divide b! Mas qualquer primo p aparece menos de b vezes em b!, para qualquer b: esse número de vezes é igual a [b/p] + [b/p^2] + ... + [b/p^n] + ... onde a soma é finita (alguma hora, p^n b, e as partes inteiras vão dar zero). Essa soma também é menor do que b/p * (1/(1-1/p)) (soma da PG sem as partes inteiras) = b / (p - 1) = b (e só poderia ser igual quando p = 2, e nesse caso, o mais próximo que chega é (b-1) porque a série é finita, e precisa de termos fracionários para dar exatamente b/(p-1)). Agora, note que a 2500, e a = AC, com C 1, implica que a 1250. Idem para b a. Assim, p aparece no máximo 1250 vezes em b!, o que é absurdo pois queríamos que p^2007 | b! Talvez tenha algo sem usar explicitamente o 2007 e as estimativas de Stirling, mas saiu ! Abraços -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instru�ões para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
2014-05-21 13:11 GMT-03:00 terence thirteen peterdirich...@gmail.com: Só tem que lembrar que Stirlinbg é pesado demais pra galera. Talvez uma desigualdade mais bobinha que saia com indução... Bom, a demonstração funciona com b 2007, ou seja, podemos ter até a = 2*2007, ou seja, tem que mostrar que f(n) = n^2007 - n! é decrescente e negativa para n 4000. Vou deixar você achar a desigualdade por indução ;-) -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] Lista 4 Cone Sul 2008
2014-05-19 23:13 GMT-03:00 terence thirteen peterdirich...@gmail.com: Ah, é claro! Uma desigualdade deve resolver! n! cresce muito mais rápido que n^2007, então f é estritamente decrescente e negativa a partir de certo ponto. Assim ela é certamente injetiva daí, pois ab daria f(a)f(b). f(a) f(b), mas é isso. O problema agora é antes deste ponto... Bom, usando Stirling, n! n^2007 mais ou menos para n ~ 2007. Mais exatamente, n! n^n / e^n, e esse último é n^2007 = n^(n - 2007) e^n = (n - 2007) log(n) n = x * log(x + 2007) 2007 + x Como log(2000) log(729) = log(3^6) 6 log(3) 6, basta 6x 2007 + x ou seja x 2007/5 = 401 Restam 2500 casos para fazer na mão ;-)) -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] Lista 4 Cone Sul 2008
MAS acho que podemos melhorar: Minha impressão é que a sequência é negativa a partir de certo ponto, e antes disso é positiva. Mas em cada trecho ela deve ser monótona. Como negativos não são iguais a positivos (exceto na França em que 0 é positivo E negativo :P), o problema acabaria. Em 20 de maio de 2014 08:05, Bernardo Freitas Paulo da Costa bernardo...@gmail.com escreveu: 2014-05-19 23:13 GMT-03:00 terence thirteen peterdirich...@gmail.com: Ah, é claro! Uma desigualdade deve resolver! n! cresce muito mais rápido que n^2007, então f é estritamente decrescente e negativa a partir de certo ponto. Assim ela é certamente injetiva daí, pois ab daria f(a)f(b). f(a) f(b), mas é isso. O problema agora é antes deste ponto... Bom, usando Stirling, n! n^2007 mais ou menos para n ~ 2007. Mais exatamente, n! n^n / e^n, e esse último é n^2007 = n^(n - 2007) e^n = (n - 2007) log(n) n = x * log(x + 2007) 2007 + x Como log(2000) log(729) = log(3^6) 6 log(3) 6, basta 6x 2007 + x ou seja x 2007/5 = 401 Restam 2500 casos para fazer na mão ;-)) -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instru�ões para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
2014-05-20 12:21 GMT-03:00 terence thirteen peterdirich...@gmail.com: MAS acho que podemos melhorar: Minha impressão é que a sequência é negativa a partir de certo ponto, e antes disso é positiva. Mas em cada trecho ela deve ser monótona. Como negativos não são iguais a positivos (exceto na França em que 0 é positivo E negativo :P), o problema acabaria. Não, a sequência (n^2007 - n!) vale zero em n = 1 (e -1 em n = 0). Para n = 2, isso já vale 2^2007 - 2 = número grandão. E vai AUMENTANDO até chegar no ponto em que a derivada é zero. E só depois diminui. O problema, portanto, é ver que essa parábola não passa duas vezes no mesmo ponto com coordenadas inteiras... -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] Lista 4 Cone Sul 2008
Talvez alguma desigualdade? Hum, vou ver casos pequenos assim que der. Em 20 de maio de 2014 12:35, Bernardo Freitas Paulo da Costa bernardo...@gmail.com escreveu: 2014-05-20 12:21 GMT-03:00 terence thirteen peterdirich...@gmail.com: MAS acho que podemos melhorar: Minha impressão é que a sequência é negativa a partir de certo ponto, e antes disso é positiva. Mas em cada trecho ela deve ser monótona. Como negativos não são iguais a positivos (exceto na França em que 0 é positivo E negativo :P), o problema acabaria. Não, a sequência (n^2007 - n!) vale zero em n = 1 (e -1 em n = 0). Para n = 2, isso já vale 2^2007 - 2 = número grandão. E vai AUMENTANDO até chegar no ponto em que a derivada é zero. E só depois diminui. O problema, portanto, é ver que essa parábola não passa duas vezes no mesmo ponto com coordenadas inteiras... -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instru�ões para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
Estou sem ideias ... No site do Treinamento Cone Sul onde encontrei a questão , os organizadores não disponibilizaram as resoluções das listas... Alguém tem ideia de como resolver a questão? Em 17 de maio de 2014 16:03, Vanderlei Nemitz vanderma...@gmail.comescreveu: Saulo, não entendi. Para mostrar que a função é injetiva, uma maneira é mostrar que f(x1) = f(x2) implica em x1 = x2. Além disso, é n^ 2007 e não n!^2007. Concorda? Em 17/05/2014 15:36, saulo nilson saulo.nil...@gmail.com escreveu: n1!(n1!^2006-1)=f(n1) n2!(n2!^2006-1)=f(n2) n1=n2 f(n1)=f(n2) n1=!n2 f(n1)=!f(n2) 2014-05-17 10:47 GMT-03:00 Gabriel Lopes cronom...@gmail.com: 9 . Prove que a função f : N -- Z definida por : f(n) = (n^2007) − n! é injetiva. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
f(n) = (n^2007) − n! Suponha que f(a) = f(b) com ab (a^2007) − a! = (b^2007) − b! (a^2007) − (b^2007) = a! − b! = b!(a!/b!-1) O lado de lá é múltiplo de b! (a^2007) = (b^2007) (mod b!) Agora emperrei! Taí, vou ver em casa... Acaso precise, 2007=9*223. Em 19 de maio de 2014 14:16, Gabriel Lopes cronom...@gmail.com escreveu: Estou sem ideias ... No site do Treinamento Cone Sul onde encontrei a questão , os organizadores não disponibilizaram as resoluções das listas... Alguém tem ideia de como resolver a questão? Em 17 de maio de 2014 16:03, Vanderlei Nemitz vanderma...@gmail.comescreveu: Saulo, não entendi. Para mostrar que a função é injetiva, uma maneira é mostrar que f(x1) = f(x2) implica em x1 = x2. Além disso, é n^ 2007 e não n!^2007. Concorda? Em 17/05/2014 15:36, saulo nilson saulo.nil...@gmail.com escreveu: n1!(n1!^2006-1)=f(n1) n2!(n2!^2006-1)=f(n2) n1=n2 f(n1)=f(n2) n1=!n2 f(n1)=!f(n2) 2014-05-17 10:47 GMT-03:00 Gabriel Lopes cronom...@gmail.com: 9 . Prove que a função f : N -- Z definida por : f(n) = (n^2007) − n! é injetiva. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
Ah, é claro! Uma desigualdade deve resolver! n! cresce muito mais rápido que n^2007, então f é estritamente decrescente e negativa a partir de certo ponto. Assim ela é certamente injetiva daí, pois ab daria f(a)f(b). O problema agora é antes deste ponto... Em 19 de maio de 2014 23:07, terence thirteen peterdirich...@gmail.comescreveu: f(n) = (n^2007) − n! Suponha que f(a) = f(b) com ab (a^2007) − a! = (b^2007) − b! (a^2007) − (b^2007) = a! − b! = b!(a!/b!-1) O lado de lá é múltiplo de b! (a^2007) = (b^2007) (mod b!) Agora emperrei! Taí, vou ver em casa... Acaso precise, 2007=9*223. Em 19 de maio de 2014 14:16, Gabriel Lopes cronom...@gmail.com escreveu: Estou sem ideias ... No site do Treinamento Cone Sul onde encontrei a questão , os organizadores não disponibilizaram as resoluções das listas... Alguém tem ideia de como resolver a questão? Em 17 de maio de 2014 16:03, Vanderlei Nemitz vanderma...@gmail.comescreveu: Saulo, não entendi. Para mostrar que a função é injetiva, uma maneira é mostrar que f(x1) = f(x2) implica em x1 = x2. Além disso, é n^ 2007 e não n!^2007. Concorda? Em 17/05/2014 15:36, saulo nilson saulo.nil...@gmail.com escreveu: n1!(n1!^2006-1)=f(n1) n2!(n2!^2006-1)=f(n2) n1=n2 f(n1)=f(n2) n1=!n2 f(n1)=!f(n2) 2014-05-17 10:47 GMT-03:00 Gabriel Lopes cronom...@gmail.com: 9 . Prove que a função f : N -- Z definida por : f(n) = (n^2007) − n! é injetiva. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- /**/ 神が祝福 Torres -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Lista 4 Cone Sul 2008
9 . Prove que a função f : N -- Z definida por : f(n) = (n^2007) − n! é injetiva. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
n1!(n1!^2006-1)=f(n1) n2!(n2!^2006-1)=f(n2) n1=n2 f(n1)=f(n2) n1=!n2 f(n1)=!f(n2) 2014-05-17 10:47 GMT-03:00 Gabriel Lopes cronom...@gmail.com: 9 . Prove que a função f : N -- Z definida por : f(n) = (n^2007) − n! é injetiva. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
Poderia elaborar mais um pouco ? Não compreendi as passagens. Obs: Talvez eu que não tenha entendido mas , no enunciado consta como : f(n) : ( n elevado a 2007) menos ( n fatorial) ; e não : f(n) : ( n fatorial elevado a 2007) menos ( n fatorial) Em 17 de maio de 2014 15:32, saulo nilson saulo.nil...@gmail.com escreveu: n1!(n1!^2006-1)=f(n1) n2!(n2!^2006-1)=f(n2) n1=n2 f(n1)=f(n2) n1=!n2 f(n1)=!f(n2) 2014-05-17 10:47 GMT-03:00 Gabriel Lopes cronom...@gmail.com: 9 . Prove que a função f : N -- Z definida por : f(n) = (n^2007) − n! é injetiva. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Lista 4 Cone Sul 2008
Saulo, não entendi. Para mostrar que a função é injetiva, uma maneira é mostrar que f(x1) = f(x2) implica em x1 = x2. Além disso, é n^ 2007 e não n!^2007. Concorda? Em 17/05/2014 15:36, saulo nilson saulo.nil...@gmail.com escreveu: n1!(n1!^2006-1)=f(n1) n2!(n2!^2006-1)=f(n2) n1=n2 f(n1)=f(n2) n1=!n2 f(n1)=!f(n2) 2014-05-17 10:47 GMT-03:00 Gabriel Lopes cronom...@gmail.com: 9 . Prove que a função f : N -- Z definida por : f(n) = (n^2007) − n! é injetiva. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
