Em 14 de outubro de 2012 08:38, Athos Couto <athos...@hotmail.com> 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 <peterdirich...@gmail.com>: >> > 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 1111... e 9999... 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 beeeem longe. >> Imagine n = 10000^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 =========================================================================
