Re: [obm-l] OBM 2011
Uma ideia legal é tomar o numero chapa C = 55...534343434...34, com k²-r cincos, r três e r quatros. Tomando k²<= n<(k+1)², e 0<=r<=2k. Tome n= 2k-r+2r e a soma dos digitos de C é S(C)=5²(k²-r) + (3²+4²)r=5²k² acho que é isso Em 14 de outubro de 2012 10:52, terence thirteen escreveu: > Em 14 de outubro de 2012 08:38, Athos Couto > escreveu: > > Bem, na verdade são (n+8)!/n!8! somas, até porque 9^n/9! nem número > inteiro > > (também cheguei a pensar que era isso...) é. > > Realmente, não entendi seus argumentos Bernardo. > > E que teorema é esse? "um teorema de Bezout nos afirma que todo natural > > grande pode ser escrito como somas de vários m^2 e n^2." > > Também tentei por indução: > > Se d é o maior divisor comum de a e b, existem inteiros X,Y tal que > Xa+Yb=d. > > Em especial, se a,b são primos entre si qualquer natural pode ser > escrito como uma combinação linear de a,b. Para naturais > suficientemente grandes, eles podem ser escritos usando apenas > adições. > > > Numa sequencia de n-1 números você terá: (n+7)!/(n-1)!8! somas > diferentes. > > Supomos que alguma(s) seja(m) quadrado(s) perfeito(s). > > Deixe-me quebrar a linha de pensamento: > > Também pensei no seguinte: (m+1)^2 - m^2 = 2m+1 > > Se pudéssemos relacionar esse fato com a indução... > > Voltando à indução: > > Formaríamos (n+8)!/n!8! números. > > Na verdade teríamos formado (n+7)!/n!7! a mais do que da última coluna. > > Se alguém conseguir continuar... não consegui ver mais nada. Acho que > esse > > não é o caminho.. > > > >> Date: Sun, 14 Oct 2012 01:24:09 -0400 > >> Subject: Re: [obm-l] OBM 2011 > >> From: bernardo...@gmail.com > >> To: obm-l@mat.puc-rio.br > > > >> > >> 2012/10/13 terence thirteen : > >> > Eu pensei em alguma indução, mas fala sério, tem que somar com alguma > >> > propriedade legal. > >> > > >> > Se pudéssemos fazer algo com ALPHA*m^2+BETA*n^2, em que m e n são > >> > primos entre si, um teorema de Bezout nos afirma que todo natural > >> > grande pode ser escrito como somas de vários m^2 e n^2. > >> Que tal contar? > >> > >> Entre ... e ... as somas dos quadrados dos dígitos variam de n > >> a 81n. Por outro lado, as somas possíveis são 9^n / 9! (descontando a > >> ordem). Logo deve haver um monte que coincidem. Mas acho que, com um > >> pouquinho de sorte, para n suficientement grade, temos praticamente > >> todos os valores possíveis entre n e 81n. Deve ter um número aí no > >> meio que seja um quadrado. Por exemplo, ([sqrt(n)] + 1)^2 é com > >> certeza menor do que 4n para n > 1. > >> > >> Chutando com um computador: para n suficientemente grande, todos os > >> números entre n+14 e 64n são factíveis. Provavelmente deve ser até > >> melhor do que isso no upper bound. O lower bound é mais fácil: você > >> tem um monte de "1". Trocar 1 por 2 aumenta três, 1 por 3 aumenta 8. > >> Fazer n+14 = n+8+3+3. n+15 é trocar 1 por 4. Fazer n+13 não dá, porque > >> as combinações com 8 e 3 não permitem. Mas o real problema é achar um > >> quadrado perto de n, o mais próximo pode ser ainda bm longe. > >> Imagine n = 1^2 + 1. O próximo está a 2*sqrt(n) de distância... > >> hum, e você pode somar 8 ou 3, e se sqrt(n) é grande o suficiente, > >> Bézout, acabou. (Você tem n casas para alterar, e 8 e 3 são maoires do > >> que 2, e n > sqrt(n)). O único caso "ruim" em que o próximo quadrado é > >> justamente n+13 (que não podemos fazer), o quadrado seguinte está a > >> 2*sqrt(n+13) + 1 de distância, e o Bézout garante que podemos fazer > >> todas os inteiros entre 7*2 e 8*n - 7*2 (ou algo próximo a isso), se > >> tivermos no máximo n termos para escolher entre 3 e 8, e o crescimento > >> linear é mais do que suficiente. Agora, basta provar para os casos em > >> que n é pequeno, mas a gente já fez! > >> > >> Quem se aventura a provar que dá pra fazer quase todos os números? Eu > >> aposto que tem a ver com a^2 + b^2 = (a-1)^2 + (b+1)^2 + 2(a-b-1). > >> > >> Abraços, > >> -- > >> Bernardo Freitas Paulo da Costa > >> > >> > = > >> 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 > > = > 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] OBM 2011
Em 14 de outubro de 2012 08:38, Athos Couto escreveu: > Bem, na verdade são (n+8)!/n!8! somas, até porque 9^n/9! nem número inteiro > (também cheguei a pensar que era isso...) é. > Realmente, não entendi seus argumentos Bernardo. > E que teorema é esse? "um teorema de Bezout nos afirma que todo natural > grande pode ser escrito como somas de vários m^2 e n^2." > Também tentei por indução: Se d é o maior divisor comum de a e b, existem inteiros X,Y tal que Xa+Yb=d. Em especial, se a,b são primos entre si qualquer natural pode ser escrito como uma combinação linear de a,b. Para naturais suficientemente grandes, eles podem ser escritos usando apenas adições. > Numa sequencia de n-1 números você terá: (n+7)!/(n-1)!8! somas diferentes. > Supomos que alguma(s) seja(m) quadrado(s) perfeito(s). > Deixe-me quebrar a linha de pensamento: > Também pensei no seguinte: (m+1)^2 - m^2 = 2m+1 > Se pudéssemos relacionar esse fato com a indução... > Voltando à indução: > Formaríamos (n+8)!/n!8! números. > Na verdade teríamos formado (n+7)!/n!7! a mais do que da última coluna. > Se alguém conseguir continuar... não consegui ver mais nada. Acho que esse > não é o caminho.. > >> Date: Sun, 14 Oct 2012 01:24:09 -0400 >> Subject: Re: [obm-l] OBM 2011 >> From: bernardo...@gmail.com >> To: obm-l@mat.puc-rio.br > >> >> 2012/10/13 terence thirteen : >> > Eu pensei em alguma indução, mas fala sério, tem que somar com alguma >> > propriedade legal. >> > >> > Se pudéssemos fazer algo com ALPHA*m^2+BETA*n^2, em que m e n são >> > primos entre si, um teorema de Bezout nos afirma que todo natural >> > grande pode ser escrito como somas de vários m^2 e n^2. >> Que tal contar? >> >> Entre ... e ... as somas dos quadrados dos dígitos variam de n >> a 81n. Por outro lado, as somas possíveis são 9^n / 9! (descontando a >> ordem). Logo deve haver um monte que coincidem. Mas acho que, com um >> pouquinho de sorte, para n suficientement grade, temos praticamente >> todos os valores possíveis entre n e 81n. Deve ter um número aí no >> meio que seja um quadrado. Por exemplo, ([sqrt(n)] + 1)^2 é com >> certeza menor do que 4n para n > 1. >> >> Chutando com um computador: para n suficientemente grande, todos os >> números entre n+14 e 64n são factíveis. Provavelmente deve ser até >> melhor do que isso no upper bound. O lower bound é mais fácil: você >> tem um monte de "1". Trocar 1 por 2 aumenta três, 1 por 3 aumenta 8. >> Fazer n+14 = n+8+3+3. n+15 é trocar 1 por 4. Fazer n+13 não dá, porque >> as combinações com 8 e 3 não permitem. Mas o real problema é achar um >> quadrado perto de n, o mais próximo pode ser ainda bm longe. >> Imagine n = 1^2 + 1. O próximo está a 2*sqrt(n) de distância... >> hum, e você pode somar 8 ou 3, e se sqrt(n) é grande o suficiente, >> Bézout, acabou. (Você tem n casas para alterar, e 8 e 3 são maoires do >> que 2, e n > sqrt(n)). O único caso "ruim" em que o próximo quadrado é >> justamente n+13 (que não podemos fazer), o quadrado seguinte está a >> 2*sqrt(n+13) + 1 de distância, e o Bézout garante que podemos fazer >> todas os inteiros entre 7*2 e 8*n - 7*2 (ou algo próximo a isso), se >> tivermos no máximo n termos para escolher entre 3 e 8, e o crescimento >> linear é mais do que suficiente. Agora, basta provar para os casos em >> que n é pequeno, mas a gente já fez! >> >> Quem se aventura a provar que dá pra fazer quase todos os números? Eu >> aposto que tem a ver com a^2 + b^2 = (a-1)^2 + (b+1)^2 + 2(a-b-1). >> >> Abraços, >> -- >> Bernardo Freitas Paulo da Costa >> >> = >> 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 = 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] OBM 2011
Bem, na verdade são (n+8)!/n!8! somas, até porque 9^n/9! nem número inteiro (também cheguei a pensar que era isso...) é.Realmente, não entendi seus argumentos Bernardo.E que teorema é esse? "um teorema de Bezout nos afirma que todo natural grande pode ser escrito como somas de vários m^2 e n^2."Também tentei por indução:Numa sequencia de n-1 números você terá: (n+7)!/(n-1)!8! somas diferentes.Supomos que alguma(s) seja(m) quadrado(s) perfeito(s).Deixe-me quebrar a linha de pensamento:Também pensei no seguinte: (m+1)^2 - m^2 = 2m+1Se pudéssemos relacionar esse fato com a indução...Voltando à indução:Formaríamos (n+8)!/n!8! números.Na verdade teríamos formado (n+7)!/n!7! a mais do que da última coluna.Se alguém conseguir continuar... não consegui ver mais nada. Acho que esse não é o caminho.. > Date: Sun, 14 Oct 2012 01:24:09 -0400 > Subject: Re: [obm-l] OBM 2011 > From: bernardo...@gmail.com > To: obm-l@mat.puc-rio.br > > 2012/10/13 terence thirteen : > > Eu pensei em alguma indução, mas fala sério, tem que somar com alguma > > propriedade legal. > > > > Se pudéssemos fazer algo com ALPHA*m^2+BETA*n^2, em que m e n são > > primos entre si, um teorema de Bezout nos afirma que todo natural > > grande pode ser escrito como somas de vários m^2 e n^2. > Que tal contar? > > Entre ... e ... as somas dos quadrados dos dígitos variam de n > a 81n. Por outro lado, as somas possíveis são 9^n / 9! (descontando a > ordem). Logo deve haver um monte que coincidem. Mas acho que, com um > pouquinho de sorte, para n suficientement grade, temos praticamente > todos os valores possíveis entre n e 81n. Deve ter um número aí no > meio que seja um quadrado. Por exemplo, ([sqrt(n)] + 1)^2 é com > certeza menor do que 4n para n > 1. > > Chutando com um computador: para n suficientemente grande, todos os > números entre n+14 e 64n são factíveis. Provavelmente deve ser até > melhor do que isso no upper bound. O lower bound é mais fácil: você > tem um monte de "1". Trocar 1 por 2 aumenta três, 1 por 3 aumenta 8. > Fazer n+14 = n+8+3+3. n+15 é trocar 1 por 4. Fazer n+13 não dá, porque > as combinações com 8 e 3 não permitem. Mas o real problema é achar um > quadrado perto de n, o mais próximo pode ser ainda bm longe. > Imagine n = 1^2 + 1. O próximo está a 2*sqrt(n) de distância... > hum, e você pode somar 8 ou 3, e se sqrt(n) é grande o suficiente, > Bézout, acabou. (Você tem n casas para alterar, e 8 e 3 são maoires do > que 2, e n > sqrt(n)). O único caso "ruim" em que o próximo quadrado é > justamente n+13 (que não podemos fazer), o quadrado seguinte está a > 2*sqrt(n+13) + 1 de distância, e o Bézout garante que podemos fazer > todas os inteiros entre 7*2 e 8*n - 7*2 (ou algo próximo a isso), se > tivermos no máximo n termos para escolher entre 3 e 8, e o crescimento > linear é mais do que suficiente. Agora, basta provar para os casos em > que n é pequeno, mas a gente já fez! > > Quem se aventura a provar que dá pra fazer quase todos os números? Eu > aposto que tem a ver com a^2 + b^2 = (a-1)^2 + (b+1)^2 + 2(a-b-1). > > Abraços, > -- > Bernardo Freitas Paulo da Costa > > = > 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] OBM 2011
2012/10/13 terence thirteen : > Eu pensei em alguma indução, mas fala sério, tem que somar com alguma > propriedade legal. > > Se pudéssemos fazer algo com ALPHA*m^2+BETA*n^2, em que m e n são > primos entre si, um teorema de Bezout nos afirma que todo natural > grande pode ser escrito como somas de vários m^2 e n^2. Que tal contar? Entre ... e ... as somas dos quadrados dos dígitos variam de n a 81n. Por outro lado, as somas possíveis são 9^n / 9! (descontando a ordem). Logo deve haver um monte que coincidem. Mas acho que, com um pouquinho de sorte, para n suficientement grade, temos praticamente todos os valores possíveis entre n e 81n. Deve ter um número aí no meio que seja um quadrado. Por exemplo, ([sqrt(n)] + 1)^2 é com certeza menor do que 4n para n > 1. Chutando com um computador: para n suficientemente grande, todos os números entre n+14 e 64n são factíveis. Provavelmente deve ser até melhor do que isso no upper bound. O lower bound é mais fácil: você tem um monte de "1". Trocar 1 por 2 aumenta três, 1 por 3 aumenta 8. Fazer n+14 = n+8+3+3. n+15 é trocar 1 por 4. Fazer n+13 não dá, porque as combinações com 8 e 3 não permitem. Mas o real problema é achar um quadrado perto de n, o mais próximo pode ser ainda bm longe. Imagine n = 1^2 + 1. O próximo está a 2*sqrt(n) de distância... hum, e você pode somar 8 ou 3, e se sqrt(n) é grande o suficiente, Bézout, acabou. (Você tem n casas para alterar, e 8 e 3 são maoires do que 2, e n > sqrt(n)). O único caso "ruim" em que o próximo quadrado é justamente n+13 (que não podemos fazer), o quadrado seguinte está a 2*sqrt(n+13) + 1 de distância, e o Bézout garante que podemos fazer todas os inteiros entre 7*2 e 8*n - 7*2 (ou algo próximo a isso), se tivermos no máximo n termos para escolher entre 3 e 8, e o crescimento linear é mais do que suficiente. Agora, basta provar para os casos em que n é pequeno, mas a gente já fez! Quem se aventura a provar que dá pra fazer quase todos os números? Eu aposto que tem a ver com a^2 + b^2 = (a-1)^2 + (b+1)^2 + 2(a-b-1). Abraços, -- Bernardo Freitas Paulo da Costa = 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] OBM 2011
l; Em 13 de outubro de 2012 21:28, Bernardo Freitas Paulo da Costa escreveu: >> Pensando aqui, 3^2+4^2=25, logo 34 é chapa. Não deve ser difícil ver >> que 34344433 é chapa, pois a soma é 4*(3^2+4^2). >> >> Assim, para todo N múltiplo de 8, existe um chapa de N algarismos. >> Difícil vai ser cobrir os restantes... :( > Eu sei fazer com 4, 5, 6, e 7 algarismos, roubando a idéia do Torres. > Só não sei como ele faz com 16 algarismos, já que 8*(3^2 + 4^2) não é > um quadrado... Você provou que dá pra fazer todos os 8N^2, na verdade, > com 3 e 4, você faz todos os 2n^2 com o mesmo argumento. Usando que > 13^2 = 5^2 + 12^2 (12 = 2*6, ou 3*4, ou 4*3, ou 6*2) você deve > conseguir um monte de outros alfa*n^2. Mas o problema é que quadrados > são mutio raros nos números inteiros... Eu pensei em alguma indução, mas fala sério, tem que somar com alguma propriedade legal. Algo como "se X^2+Y^2 é quadrado, e X^2 é soma de quadrados de alguns caras, enquanto Y^2 também é, podemos juntar os caras". Por exemplo, 5^2+12^2=13^2, assim encontrando caras cujos quadrados somam 144 = por exemplo 9731, basta juntar um 5 nisso e obtemos um cara de 9 dígitos. Outro seria 884, a soma dos quadrados dá 12^2. Igualmente, 8845 daria 4 dígitos Se pudéssemos fazer algo com ALPHA*m^2+BETA*n^2, em que m e n são primos entre si, um teorema de Bezout nos afirma que todo natural grande pode ser escrito como somas de vários m^2 e n^2. > -- > Bernardo Freitas Paulo da Costa > > = > 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 = 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] OBM 2011
> Pensando aqui, 3^2+4^2=25, logo 34 é chapa. Não deve ser difícil ver > que 34344433 é chapa, pois a soma é 4*(3^2+4^2). > > Assim, para todo N múltiplo de 8, existe um chapa de N algarismos. > Difícil vai ser cobrir os restantes... :( Eu sei fazer com 4, 5, 6, e 7 algarismos, roubando a idéia do Torres. Só não sei como ele faz com 16 algarismos, já que 8*(3^2 + 4^2) não é um quadrado... Você provou que dá pra fazer todos os 8N^2, na verdade, com 3 e 4, você faz todos os 2n^2 com o mesmo argumento. Usando que 13^2 = 5^2 + 12^2 (12 = 2*6, ou 3*4, ou 4*3, ou 6*2) você deve conseguir um monte de outros alfa*n^2. Mas o problema é que quadrados são mutio raros nos números inteiros... -- Bernardo Freitas Paulo da Costa = 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] OBM 2011
Em 13 de outubro de 2012 12:53, Victor Hugo escreveu: > 3, 4 e 5 > > Sent from my iPad > > On 13/10/2012, at 11:16, Athos Couto wrote: > > Dizemos que um número inteiro positivo é chapa quando ele é formado apenas > por algarismos não nulos e a > soma dos quadrados de todos os seus algarismos é também um quadrado > perfeito. > Prove que, para todo inteiro positivo n, existe um número chapa com > exatamente n algarismos. > > Alguma ideia? Pensando aqui, 3^2+4^2=25, logo 34 é chapa. Não deve ser difícil ver que 34344433 é chapa, pois a soma é 4*(3^2+4^2). Assim, para todo N múltiplo de 8, existe um chapa de N algarismos. Difícil vai ser cobrir os restantes... :( -- /**/ 神が祝福 Torres = 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] OBM 2011
3, 4 e 5 Sent from my iPad On 13/10/2012, at 11:16, Athos Couto wrote: > Dizemos que um número inteiro positivo é chapa quando ele é formado apenas > por algarismos não nulos e a > soma dos quadrados de todos os seus algarismos é também um quadrado perfeito. > Prove que, para todo inteiro positivo n, existe um número chapa com > exatamente n algarismos. > > Alguma ideia?
