[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Re: [obm-l] 2ª Vingança Olimpica- Problema 5
Caro JP:
Voce tem razao. Sao escolhidas criancas e nao linhas e colunas.
Portanto, a minha solucao abaixo esta errada e o problema eh bem mais
complicado do que eu supuz inicialmente.
Por exemplo, para p = 3, a minha solucao eh ((2^3-2)/3 + 1)^2 = 3^2 = 9, mas
existem mais de nove maneiras de escolher as criancas:
Soma = (3,3)
(3,3)
(1,2) (2,1)
(1,1) (2,2)
Soma = (3,6)
(1,3) (2,3)
(1,1) (1,2) (1,3)
Soma = (6,3)
(3,1) (3,2)
(1,1) (2,1) (3,1)
Soma = (6,6)
(1,2) (2,1) (3,3)
(1,1) (2,2) (3,3)
(2,1) (2,2) (2,3)
(1,2) (2,2) (3,2)
(1,1) (1,2) (2,1) (2,2)
Soma = (6,9)
(1,3) (2,3) (3,3)
...
De qualquer forma, como cada crianca corresponde a um par (i,j) com
1 <= i, j <= p acho que a minha reformulacao esta correta, ou seja, o
problema eh realmente o de se 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.
O erro na solucao abaixo foi assumir que um subconjunto de um produto
cartesiano tambem eh um produto cartesiano, o que nao eh verdade em geral.
on 25.03.03 20:55, peterdirichlet1985@zipmail.com.br at
peterdirichlet1985@zipmail.com.br wrote:
> Nessa parte de conjuntos,lembre-se de que a criança(i;j)tem i kg de doce
> de jilo e j kg de doce de jaca.E sao escolhidas crianças e nao linhas e
> colunas.Tente verificar isso.Essa ultima parte foi considerada dificil.Mas
> beleza sao so detalhes(acho)
>
> -- 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>
> =========================================================================
>
=========================================================================
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>
=========================================================================