2012/4/26 marcone augusto araújo borges <[email protected]>: > Prove que, entre 2^(n+1) números naturais quaisquer,existem 2^n números cuja > soma é divisível por 2^n
> Eu sei que em uma divisão por 2^n existem 2^n restos possíveis > Se em 2^n divisões ocorressem 2^n restos iguais a r,a soma deles seria > r*2^n,que é divisível por 2^n O problema dessa idéia é que você não tem certeza que dá pra fazer "de forma independente"... > Não sei se conseguiria resolver por congruência,mas eu gostaria de ver uma > solução por outro caminho. Bom, olhando a questão, parece ser um caso de recorrência. E é mesmo! (enfim, funciona) Mostre que é verdade para n = 1. Esse caso é fácil, mas já é a base de tudo... Agora, tente ver como faz para n = 2. Você tem 8 números (quaisquer!!!) e você tem que conseguir 4 cuja soma seja divisível por 4. Por indução, você sabe que para cada decomposição 8 = 4+4, você consegue 2 vezes 2 números cuja soma é divisível por 2. Mas isso não garante que é divisível por 4!! Podia dar 2 + 0... e aí? A dica é ver que o caso n = 1 não é optimal... 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 =========================================================================
