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 é <[EMAIL PROTECTED]> > ========================================================================= ========================================================================= 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]> =========================================================================