Re: [obm-l] Mais Problemas em Aberto

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Dá pra melhorar bastante esse limitante:

A idéia baseia-se no seguinte fato:
todo inteiro entre 1...2^(n+1)-1 pode ser expresso como soma de elementos de
uma combinação de {1, 2, 2², ..., 2^n}.

Seja k um inteiro tal que 2^(k-1) < p < 2^k
Da matriz A já definida, separe os elementos:
S1 = {(1, 0); (2, 0); ...; (2^(k-1), 0)}
S2 = {(0, 1); ...; (0, 2^(k-1))}
|S1| = |S2| = k
todo elemento de Zp X Zp pode ser expresso como uma soma de elementos de uma
combinação dos elementos de S1 e S2, sendo assim, para toda a combinação de
elementos do resto da matriz, há sempre pelo menos uma combinação de
elementos de S1 e S2 que se cancela com a combinação do resto.

O limitante inferior passa então a ser: 2^[p² - 2k]
Onde k < lg(p).

Além do limitante inferior dá pra determinar um limitante superior:
2^(k-1) < p < 2^k
logo
2^k < 2p => 2^k - 1 <= 2p - 2
o conjunto das possíveis somas é no máximo {0, 1, ..., p-1, p, p+1, ...
2p-2}.
repare que nesse conjunto não há nenhum elemento (mod p) que se repete mais
do que 2 vezes, sendo assim, no máximo temos 2 maneiras de escrever um mesmo
elemento e, por consequência, no máximo 4 maneiras de escrever um par de Zp
X Zp como soma dos elementos de S1 e S2.

Sob essas condições um limitante superior é 4*2^[p² - 2k] = 2^[p² - 2k + 2]

Temos então:
2^[p² - 2k] <= RESPOSTA <= 2^[p² - 2k + 2]

[ ]'s

> Consegui estimar um limitante inferior para o número de grupos de
> crianças:
>
> Considere uma matriz com elementos A[i, j] = (i, j) pertence a (Zp)²
> O problema proposto é equivalente a calcular o número de combinações de
> elementos de A cuja soma dê (0, 0).
>
> Agora desenhando a matriz A e separando a última linha e a última coluna,
> formamos uma matriz A', com (p-1) x (p-1) elementos em (Zp)².
>
> Os elementos da última linha são:
> { (1, 0), (2, 0), ..., (p-1, 0) , (0,0)}
> e os da última coluna são:
> { (0, 1), (0, 2), ..., (0, p-1) , (0,0)}
> * o elemento (0, 0) é compartilhado!
>
> Repare que toda combinação de elementos da matriz A' tem soma em (Zp)² e
> todo elemento e (Zp)² tem um oposto aditivo em (Zp)², além disso, é
possível
> obter todos os elementos de (Zp)² através dos elementos da última linha e
da
> última coluna (basta tomar a soma de dois deles, por exemplo), por tanto,
> para cada combinação de A' existe pelo menos uma maneira de selecionar
> elemento(s) na última linha e coluna de A tal que a soma total dê (0, 0).
>
> Por tanto, um limitante inferior para o número de grupo crianças do
problema
> é:
>
> 2^[(p-1)²] == total de combinações em A'.
>
> Esse limitante tem bastante folga pois na verdade existe várias maneiras
de
> obter o mesmo elemento de (Zp)² através da última linha e da última
coluna.
>
> por exemplo o elemento (3, 2) = (3,0) + (0,2) = (2,0) + (1,0) + (0,2) =
...
>
> Idéias?
>
> [ ]'s
>
> -----
>
> 7.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]
>
> =========================================================================
> 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>
=========================================================================