[obm-l] Re: [obm-l] 2� Vingan�a Olimpica - Problema 5

[peterdirichlet1985@xxxxxxxxxxxxxx]

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 � <nicolau@mat.puc-rio.br>
>=========================================================================
>

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 � <nicolau@mat.puc-rio.br>
=========================================================================