[obm-l] Re: [obm-l] Re: AJUDA produtório

[bmat@xxxxxxxxxxxxxx]

Eu acho que pode haver uma aresta a aparar.... vejam abaixo, mas o problema
deve ficar bem pior.

-- Mensagem original --

>Ola Andre e demais colegas
>desta lista ... OBM-L,
>
>Tudo Legal ? Estou tomando a liberdade de remeter esta resposta tambem
para
>
>a lista OBM-L, pois o problema tambem pode ser do interesse de outras 
>pessoas.
>
>Eu nao conhece o problema a que voce se refere, citado pelo Prof da UFF.
>O 
>problema que o Frederico me propos era o seguinte :
>
>Considere N inteiros I1, I2, I3, ..., In tais que Ii < Ij sempre
>i < j e seja "P" o produto de todas as diferencas da forma (Ij - Ii)
>nas quais i < j. Caracterize o maior natural "D" que sempre dividira "P",
>
>Quais quer que sejam os Ii's escolhidos.
>
>A IDEIA DA SOLUCAO : Descobrir a decomposicao de "D" em fatores primos.
Vou
>
>fazer alguns casos para voce assimilar o raciocinio. Depois passo a 
>generalizacao.
>
>
>
>FATOR PRIMO 2 :
>
>Cada um dos Ii ou e congruo a 0 ou e congruo a 1 modulo 2, Isto e,
>ou Ii==0(mod2) ou Ii==1(mod2), . Segue que os conjuntos :
>
>C0 = {conjunto dos Ii tais que Ii==0(mod2) }
>C1 = {conjunto dos Ii tais que Ii==1(mod2) }
>
>Estao bem definidos e sao, evidentemente, disjuntos, pois um inteiro 
>qualquer nao pode ser, simultanemanete, congruo a 0 e a 1. Mais ainda,
os
>
>conjuntos C0 e C1 constituem uma particao de {I1, I2, ...,In}, pois :
>
>Co intersecao C1 = vazio
>C0 uniao C1 = { I1, I2, ..., In }
>
>Portanto, se chamarmos o numero de elementos de C0 e C1, respectivamente,
>de 
>E0 e E1, teremos :
>
>E0 + E1 = numero de elementos de {I1, I2, ...,In}
>E0 + E1 = N
>
>Agora, pense assim : Uma diferenca qualquer entre dois inteiros de 
>{I1,I2,...,In} so pode ser uma diferenca ENTRE DOIS INTEIROS DE C0, ENTRE
>
>DOIS INTEIROS DE C1 ou ENTRE UM INTEIROS DE C0 E UM INTEIRO DE C1.
>
>Nos dois primeiros casos o resultado sera um multiplo de 2, no terceiro
caso
>
>nao. Segue que haverao tantas diferencas mutiplos de 2 quanto forem a soma
>
>das diferencas que se poderao fazer SOMENTE COM ELEMENTOS DE C0 e SOMENTE
>
>COM ELEMENTOS DE C1.
>
>1) Pelo que vimos, C0 tem E0 elementos. Segue que BINOM(E0,2) e o total
de
>
>diferencas que se pode fazer com os seus elementos de C0 e que atendem
as
>
>condicoes  do problema.
>
>2) Igualmente, C1 tem E1 elementos. Segue que BINOM(E1,2) e o total de

>diferencas que se pode fazer com os seus elementos de C1 e que atendem
as
>
>condicoes  do problema.
>
>Portanto,
>S = BINOM(E0,2)+ BINOM(E1,2)
>e o total de diferencas MULTIPLO DE 2  que sao geradas quando, ao 
>escolhermos os inteiros I1, I2, ..., In "E0" desses inteiros forem congruos
>
>a o modulo 2 e "E1" deles for congruo a 1 modulo 2.
>
>Bom, ate aqui acho que esta bem claro. Acho mesmo que fui prolixo. Mas,

>vamos la.
>
>Nos nao sabemos como sera a escolha dos Ii ... Alguem pode escolher de
forma
>
>que E0=0 e E1=N, ou E0=1 e E1=N-1, ..., ou E0=N e E1=0. Todavia, independe
>
>da forma como a pessoa escolher os Ii, a formula "S" acima dara o numero
>de 
>fatores 2 que, com certeza, ira parecer ... Portanto, se tomarmos o MINIMO
> 
>QUE AQUELA EXPRESSAO ASSUME quando E0 e E1 assumem todos os valores 
>possiveis - de (E0,E1)=(N,0) ate (E0,E1)=(0,N)-NAO DEPENDEREMOS MAIS DA

>ESCOLHA DOS Ii's.
>
>Deve ter ficado claro, agora, que :
>
>S2 = MIN {BINOM(E0,2)+ BINOM(E1,2), E0+E1=N }
>
>E a MAIOR POTENCIA de 2 que SEMPRE DIVIDIRA "P", QUAISQUER QUE SEJAM OS
N
>
>INTEIROS I1, I2, ..., In ESCOLHIDOS ( Ii < Ij se i < j )
>

Eu posso estar errado, mas acho que talvez dê para garantir que um fator
maior pode dividir esse produtório. Por exemplo, se houver 5 números, sabemos
que uma das diferenças pares será múltipla de 4(pelo menos!) e então os
fatores vão começar a aumentar mais rápido do que o mínimo das somas dos
binomiais.

Eu acho(e esse acho é bem mais arriscado) que talvez dê para garantir que
o maior número que divide "P" é o produtório de x!(fatorial de x) de um
até n (ou seja: 1!*2!*3!*4!*...*n!). Se alguém tiver certeza, confirme (ou
dê um contra-exemplo), por favor. (Talvez essa propriedade só funcione se
os números forem 1, 2, 3, 4, ..., n )

Até mais,
Bernardo.

 ----------- ------------
>
>Com os melhores votos
>de paz profunda, sou
>
>Paulo Santa Rita
>3,1458,101202



------------------------------------------
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>
=========================================================================