Nem sei direito mas esse ai e parecido com o 6 da IMO do Canada. Tente o site imo.math.ca.La deve ter.Ou cace em www.cms.math.ca
ATE MAISSSS!!!!Ass.:Johann PS.:Ninguem fez geometria????? -- Mensagem original -- >5)(Guilherme Issao)Existem p²,onde p e primo,crianças dispostas num bairro >como um tabuleiro p por p.Ha tambem duas distribuidoras de doces,a >Cledmilson Marmotta e a Estrogonofre's.A Cledmilson Marmotta manda um >vendedor para cada uma das p linhas horizontais,sendo que o vendedor da >i-esima linha tem i Kg de doce de jilo e distribui igualmente entre as p >crianças. Da mesma forma Estrogonofre's manda um vendedor para cada uma das >p linhas verticais,sendo que o vendedor da j-esima linha tem j Kg de doce >de >jaca e distribui igualmente entre as p crianças. De quantas maneiras podemos >escolher um grupo de crianças desse bairro para roubar-lhes os doces de modo >que a quantidade de cada tipo de doce roubada seja inteira?[6] > >Acho que encontrei a solução. De qualquer jeito, gostaria de comentários, >especialmente se a solução estiver errada. > >Se as linhas escolhidas forem i_1, ..., i_r e as colunas j_1, ..., j_s, >então as quantidades serão: >(i_1 + ... + i_r)/p kg de doce de jiló >e >(j_1 + ... + j_s)/p kg de doce de jaca. > >O peso total de cada doce será inteiro se e somente se >{i_1, ..., i_r} e {j_1, ..., j_s} forem subconjuntos de {1, 2, ..., p} cujas >somas dos elementos sejam = 0 (mod p). > >Dessa forma, o problema pode ser refraseado como: >Determinar o número de subconjuntos de {1, 2, ..., p}x{1, 2, ...,p} cuja >soma dos >elementos (definida da forma usual: (a,b)+(c,d)=(a+c,b+d) ) seja um par >ordenado da forma (mp,np) onde m e n são inteiros. > >Assim, se M = número de subconjuntos de {1,2,...,p} que tenham a soma de >seus elementos = 0 (mod p), então o número desejado será igual a M^2. > >Inicialmente, vamos determinar o valor de M. > >Consideremos os subconjuntos de {1,2,...,p}com n elementos ( 1 <= n <= p >). >Seja f(n) = número de tais subconjuntos cuja soma seja = 0 (mod p) > >Então: M = f(1) + f(2) = ... = f(p-1) + f(p) > >Se n = p, então o único subconjunto com soma = 0 (mod p) será {1,2,...,p} >==> >f(p) = 1 > >Consideremos agora o caso 1 <= n <= p-1. >Tomemos um subconjunto de n elementos {a(1),...,a(n)} com soma = 0 (mod p). > >Para 1 <= k <= p-1, se somarmos k a cada um dos a(i), teremos que: >a(1) + ... + a(n) = kn (mod p) > >Como p é primo e n < p, os números 0, n, 2n, ..., (p-1)n formarão um sistema >completo de restos (mod p). > >Assim, para cada k ( 1 <= k <= p-1) e a cada subconjunto {a(1), ...,a(n)}com >soma = 0 (mod p), podemos fazer >corresponder exatamente um conjunto cuja soma é = k (mod p). > >Logo, o número de subconjuntos de n elementos cuja soma é = k (mod p), será >o mesmo >para cada k (0 <= k <= p-1) > >Como o número total de subconjuntos de n elementos de {1, 2, ..., p} é >C(p,n), teremos que f(n) = C(p,n)/p. > >M = f(1) + f(2) + ... + f(p-1) + f(p) = >= C(p,1)/p + C(p,2)/p + ... + C(p,p-1)/p + 1 = >= (2^p - 2)/p + 1 > >Logo, M^2 = [(2^p - 2)/p + 1]^2 > >Obs: Existe uma maneira de roubar um número inteiro de cada tipo de doce >que >não foi computada acima. Trata-se de não roubar doce nenhum (ou seja, roubar >zero doces), o que corresponde ao subconjunto vazio de {1,...,p} x >{1,...,p}. >Se incluirmos essa maneira (e acho que devemos, pois é a única moral e >legalmente aceitável), a resposta será: >[(2^p - 2)/p + 1]^2 + 1. > >Um abraço, >Claudio. > >========================================================================= >Instruções para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >O administrador desta lista é <[EMAIL PROTECTED]> >========================================================================= > TEA WITH ME THAT I BOOK YOUR FACE ------------------------------------------ Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================