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 )
FATOR PRIMO 3 :
Voce aqui e identico ...
Cada um dos Ii ou e congruo a 0 ou e congruo a 1 ou e congruo a 2 modulo 3, Isto e, ou Ii==0(mod3) ou Ii==1(mod3) ou Ii==1(mod3) . Segue que os conjuntos :
C0 = {conjunto dos Ii tais que Ii==0(mod3) }
C1 = {conjunto dos Ii tais que Ii==1(mod3) }
C2 = {conjunto dos Ii tais que Ii==2(mod3) }
Estao bem definidos e sao, evidentemente, disjuntos, pois um inteiro qualquer nao pode ser, simultanemanete, pertencer a dois ou mais dos conjuntos acima. Mais ainda, os conjuntos C0, C1 e C2 constituem uma particao de
{ I1, I2, I3 ..., In }, pois :
Ci intersecao Cj = vazio, para quaisquer i ,j em { 0.1.2 } com i # j
C0 uniao C1 uniao C2 = { I1, I2, I3 ..., In }
Portanto, se chamarmos o numero de elementos de C0, C1 e C2 , respectivamente, de E0, E1 e E2, teremos :
E0 + E1+E2 = numero de elementos de {I1, I2, ...,In}
E0 + E1+ E2 = N
E0, E1, E2 inteiros nao-negativos
Agora, basta re-pensar 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 DOIS INTEIROS DE C2 OU ENTRE UM INTEIROS DE Ci E UM INTEIRO DE Cj com I # J e I, J em {0,1,2}
Nos tres primeiros casos o resultado sera um multiplo de 3, nos demais casos nao. Segue que haverao tantas diferencas mutiplos de 3 quanto forem a soma das diferencas que se poderao fazer SOMENTE COM ELEMENTOS DE C0 e SOMENTE COM ELEMENTOS DE C1 e SOMENTE COM OS ELEMENTOS DE C2.
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.
3) Igualmente, C2 tem E2 elementos. Segue que BINOM(E2,2) e o total de diferencas que se pode fazer com os seus elementos de C2 e que atendem as condicoes do problema.
Portanto,
S = BINOM(E0,2)+ BINOM(E1,2) + BINOM(E2,2)
e o total de diferencas MULTIPLO DE 3 que sao geradas quando, ao escolhermos os inteiros I1, I2, ..., In, "E0" desses inteiros forem congruos a ZERO modulo 3 e "E1" deles for congruo a 1 modulo 3 e "E2" forem congruos a 2 modulo 3. .
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=0 e E2=N, ou E0=0 e E1=1 e E2=N-1, ..., ou E0=N e E1=0 e E2=0. Todavia, independe da forma como a pessoa escolher os Ii, a formula "S" acima dara o numero de fatores 3 que, com certeza, ira parecer ... Portanto, se tomarmos o MINIMO QUE AQUELA EXPRESSAO ASSUME quando E0, E1 e E2 assumem todos os valores possiveis - de (E0,E1,E2)=(0,0,N ) ate (E0,E1,E2)=(N,0,0)-NAO DEPENDEREMOS MAIS DA ESCOLHA DOS Ii's.
Deve ter ficado claro, agora, que :
S3 = MIN {BINOM(E0,2)+ BINOM(E1,2)+BINOM(e2,2), E0+E1+E2=N }
E a MAIOR POTENCIA de 3 que SEMPRE DIVIDIRA "P", QUAISQUER QUE SEJAM OS N INTEIROS I1, I2, ..., In ESCOLHIDOS ( Ii < Ij se i < j )
O MAIOR FATOR PRIMO A SE CONSIDERAR
Para ver qual o maior fator primo a ser considerado, quando escolhemos N inteiros, basta notar que para cada primo Q precisamos determinar o minimo de uma expressao
S=BINOM(E0,2) + BINOM(E1,2) + ... + BINOM(Eq-1,2)
com "Q" parcelas ( de E0 ate Eq-1 ) e sendo E0+E1+...+Eq-1=N. Se Q >= N a equacao E0+E1+...+Eq-1=N admitira uma solucao na qual Ei=0 ou Ei=1 para qualquer i em {0, 1, ... ,q-1 }, ou seja,
S=BINOM(E0,2) + BINOM(E1,2) + ... + BINOM(Eq-1,2)
admitira o minimo ZERO e, portanto, havera uma escolha dos Ii em que nao surgira um fator primo Q. Daqui segue necessariamente que o ultimo fator primo que precisamos considerar e O MAIOR PRIMO MENOR QUE "N", pois, neste caso, precisaremos distribuir N em Q parcelas e como N > Q havera ao menos uma parcela >= 2 e o minimo de S sera, pelo menos, 1.
Seja portanto "Q" o ultimo primo considerado. O valor de "D" que procuramos sera :
D=(2^S2)*(3^S3)*(5^S5)*(7^S7)*...*(Q^Sq)
Esse e O MAIOR NUMERO NATURAL "D" QUE SEMPRE DIVIDIRA "P" INDEPENDE DA ESCOLHA DOS Ii's
Bom, eu vou ficar por aqui ... Antes, porem, algumas observacoes :
1) Voce vai precisar determinar os minimos das funcoes S descritas acima. Esse problema tem o merito de trazer a cena esta funcoes, muito uteis em outras circunstancias. Mas isso fica pra voce. Todavia, vou dizer : O demonio de Socrates esta soprando em minha orelha que o minimo ocorre quando a distribuicao de N nas parcelas Ei e a mais uniforme possivel ... Ou seja, se sao "Q" parcelas, coloque a parte inteira de N/Q em cada parcela e distribua o RESTO de N/Q acrescentando UMA UNIDADE no maior numero possivel de parcelas.
3) Novidade e Flexibilidade com numeros binomiais voce vai encontrar na MATEMATICA QUANTICA. Eu sinto que esta e uma interpretacao poderosa, que nos permitira compreender e manifestar fenomenos matematicos que ainda nao conseguimos explicar ou sequer perceber... O Livro do Prof Nicolau sobre esse tema esta disponivel e voce pode le-lo em :
http://www.mat.puc-rio.br/~nicolau/publ/publ.html
clicar em TOPICOS DE MATEMATICA QUANTICA
3)Voce pode publicar suas conjecturas aqui, nesta lista. E obrigado pelos elogios.
Com os melhores votos
de paz profunda, sou
Paulo Santa Rita
3,1458,101202
From: Andr� Silva <[EMAIL PROTECTED]>
To: "Paulo Santa Rita" <[EMAIL PROTECTED]>
Subject: AJUDA produt�rio
Date: Tue, 10 Dec 2002 11:43:10 -0200
Caro Paulo,
� sempre um prazer, ver suas contribui��es � lista. N�o sou ass�duo, mas sempre que posso acompanho a movimenta��o e invariavelmente sua presen�a � sempre muito esclarecedora. N�o lhe escrevo s� para elogi�-lo. Recentemente escreveu ao Frederico Gomes indicando a solu��o de um problema que n�o tive acesso ao enunciado. Nela, se n�o estou delirando - isto � comum :) - h� um "esbo�o" de como calcularmos o menor expoente de um primo que divide o produto de n inteiros. Se � realmente por a�, gostaria que voce, se puder, me enviasse com mais detalhes o problema e sua solu��o. O fato � que um professor da UFF me disse a uns seis meses atr�s que ningu�m havia provado que entre dois quadrados h� sempre um inteiro primo. Pensando sobre este problema esbarrei no c�lculo do expoente de um primo, tal que este divide o produto de n inteiros. Desde j� agrade�o por sua aten��o.
Paulo, gostaria de saber se realmente este problema est� em aberto, ou se pelo menos estava at� vc pensar nele!?!
Abra�os,
Andr� Silva (RJ)
_________________________________________________________________ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com
========================================================================= 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]> =========================================================================
