Longo demais, obviamente por não terem sido podadas as partes velhas...
[]s, N.
Bem,a original era que temos n celulas e o processo para na ficha n-1 exatamente.Para quais n?
Carlos Gustavo Tamm de Araujo Moreira wrote:Bem, pela interpretacao abaixo, que parece razoavel, o problema e' achar
uma solucao de k(k+1)/2-r(r+1)/2=0 (mod n) com 1<=rk(k+1)/2-r(r+1)/2=(k-r)(k+r+1)/2. Queremos entao achar dois numeros (k-r e
k+r+1) com paridades distintas, cuja diferenca e' pelo menos 3, cujo produto
e' multiplo de 2n e cuja soma seja minima. Nesse caso seu produto sera'
igual a 2n (senao podemos cortar fatores deles para que seu produto seja 2n
fazendo a sua soma diminuir - temos so' que cuidar do caso em que ao cortar
esses fatores obtemos dois fatores com diferenca 1, e nesse caso o produto
poderia ser igual a 4n no caso otimo - por causa dessas coisas seria mais
natural comecar com k=0...), e a maior potencia de 2 que divide 2n dividira'
um deles.
Devemos escolher uma tal fatoracao de 2n (ou de 4n) de modo que os fatores
sejam os mais proximos possiveis. E' claro que a forma da solucao otima
depende de n. Se n=2^u, por exemplo, teremos k=2^u e r=2^u-1 ( esse e' o
unico caso, alem de n=3, em que k=n), e se n > 3 e' um primo impar, devemos
ter k=(n+1)/2 e r=(n-3)/2.Por outro lado, se n=(u+2)(u-1)/2 entao k=u e r=1;
esse e' o caso em que k=(sqrt(9+8n)-1)/2 e' o menor possivel comparado com n.
Abracos,
Gugu
Obs: Se n=36=8.9/2, o produto no caso otimo (16.9=144) e' 4n, e nao 2n
(nesse caso o melhor que podemos conseguir com produto igual a 2n com
diferenca pelo menos 3 entre os fatores, dado que os fatores devem ter
paridade diferente e' 24.3=72, 24+3=27 > 25=16+9). Nesse caso, portanto,
k=12 e r=3. Esses fenomenos so podem ocorrer quando n e' da forma k(k+1)/2
(e nem sempre ocorrem nesses casos-----