Re: [obm-l] olimp�adas ao redor do mundo.....

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] olimp�adas ao redor do mundo.....

on 10.06.03 21:20, DEOLIVEIRASOU@aol.com at DEOLIVEIRASOU@aol.com wrote:

> Resolvi o problema abaixo, mas gostaria de ver( se poss�vel ) a solu��o de outros da lista e poder concluir se a minha � a mais otimizada ou n�o ( ficou grande ).
>   Problema:
> Eduardo escreveu todos os produtos, todas as somas e todos os valores absolutos das diferen�as dos inteiros positivos a_1,a_2,a_3,.....,a_100 tomados dois a dois. Qual o maior n�mero de inteiros �mpares obtidos por Eduardo??
> ps-Cheguei numa fun��o f(n), que d� o maior n�mero poss�vel de inteiros �mpares obtidos por Eduardo....para conseguir esse n�mero m�ximo de �mpares � necess�rio que na sequ�ncia de cem n�meros inteiros positivos existam  66 ou 67 �mpares....Ser� que errei nos c�lculos???
>          Um abra�o,
>              Crom 

Oi, Crom:

Se voce errou, entao erramos juntos. Veja abaixo...

a, b pares ==> ab, a+b, a-b pares
a, b impares ==> ab impar, a+b, a-b pares
a par, b impar (ou vice-versa) ==> ab par, a+b, a-b impar

Suponha que haja N termos impares e 100 - N termos pares na sequencia.

Entao, teremos:
C(N,2) = N(N-1)/2 pares (nao-ordenados) {impar,impar}
C(100 - N,2) (100-N)(99-N)/2 pares {par,par}
N(100 - N) pares {impar,par}

(Total = C(100,2) = 100*99/2 = 4950 pares)

Cada um dos N(N-1)/2 pares {impar,impar} origina 1 inteiro impar e 2 pares
Cada um dos (100-N)(99-N)/2 pares {par,par} origina 3 inteiro pares
Cada um dos N(100 - N) pares {impar,par} origina 2 inteiros impares e 1 par.

Assim, o numero de inteiros impares gerados eh igual a:
1*N(N - 1)/2 + 2*N(100 - N) =
(N^2 - N + 400N - 4N^2)/2 =
(399N - 3N^2)/2

Esse numero serah maximo para N = (-399)/(2*(-3)) = 66,5 ==> 
N = 66 ou N = 67 impares ==>
em ambos os casos, o numero de impares gerados serah igual a 6633.


Um abraco,
Claudio.