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

[peterdirichlet1985@xxxxxxxxxxxxxx]

Vamos ver se entendi...
-- Mensagem original --

>On Tue, Mar 25, 2003 at 05:34:01PM -0300, Cláudio (Prática) wrote:
>> 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.
>
>Está certo se você não supuser que os i_1, ..., i_r sejam distintos,
>que os i_1, ..., i_s sejam distintos, mas supuser que r=s.
> 
>> 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.
>
>Esta reformulação está correta...
> 
>> 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.
aqui acho que cada conjunto na verdade e tido como par ordenado.
>...mas esta conclusão não está. Não entendi direito qual foi o seu raciocínio.
>Mas vou acompanhar o cálculo de M, é um problema relacionado.
> 
>> 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)
>
>Faltou f(0).
> 
>> Se n = p, então o único subconjunto com soma = 0 (mod p) será {1,2,...,p}
>> ==>
>> f(p) = 1
>
>Ok.
> 
>> 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.
>
>Muito bem.
> 
>> 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
>
>Na verdade (2^p - 2)/p + 2.
> 
>[]s, N.
>=========================================================================
>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>
=========================================================================