[obm-l] Re: [obm-l] Sequência 1, 3, 2, 6, 8, 4, 11, 5, 14

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Acho que consegui resolver este problema... Algum voluntário pra verificar
se a demonstração está correta? (espero que as imagens saiam legíveis)





Seja a sequência X: N --> N (N = conjunto dos inteiros positivos),
definida por:
X(1) = 1, e, para n > 1, X(n) = menor inteiro positivo tal que:
(i) X(n) não pertence a { X(1) , X(2) , ... , X(n-1) }, e
(ii) o conjunto { X(1), ..., X(n) } tem média aritmética inteira.
Prove que X é uma bijeção (ou seja, cada inteiro positivo aparece na
sequência exatamente uma vez).



Sejam e

É fácil ver que, para n > 1, S(n) = S(n - 1) + X(n) = m(n-1).(n-1) + X(n)

Donde verificamos que:

S(n) = m(n-1).n + X(n) - m(n-1) º 0 (mod n)

Þ X(n) º m(n-1) (mod n) Þ X(n) = m(n-1) + k.n para algum k inteiro

Essa linha também nos diz que M(i) = {m(1), m(2), ... m(i)} Ì {X(1), X(2),
..., X(i+1)} pois o valor m(n-1) é o menor que satisfaz o critério de média
aritmética inteira.

Neste ponto estou sendo ligeiramente desleixado na notação pois há valores
repetidos para as médias o que faz com que o conjunto M(i) não tenha
necessariamente i elementos.





Vamos tentar provar por indução que m(n) = m(n-1) + k, sendo que k Î {0, 1}
para todo n.



m(2) = m(1) + 1, logo para o caso inicial temos que a afirmação é
verdadeira.

Suponha que, para todo 2 <= i < n. m(i) = m(i-1) + k, com k Î {0, 1}

Com essa hipótese temos:

m(1) <= m(2) <= ... <= m(n-1) <= n-1 ....... (1)



Também sabemos que X(i+1) º m(i) (mod i + 1)

Se para todo j, 1<= j <= i, X(j) ¹ m(i), assuma X(i+1) = m(i) e temos:

m(i+1) = m(i) + 0.

Se existe um valor para j em que X(j) = m(i), tome X(i+1) = m(i) + i + 1 e
vamos verificar que não existe nenhum inteiro u, 2 <= u <= i tal que X(u) =
X(i+1):

A partir de (2), temos X(u) <= m(u-1) + u

De (1) temos X(u) <= m(i) + u < m(i) + i + 1, pois u <= i. Verificar que
X(1) ¹ X(i+1) é trivial.

Sendo assim m(i+1) = m(i) + 1.



Está provado então, pelo PIF que m(n) = m(n-1) + k, com k Î {0, 1} para todo
n >= 2.



Se provarmos que não existe um valor u tal que, para todo v > u, m(v) = m(u)
teremos provado que, para todo inteiro a, existe um inteiro w tal que m(w) =
a e, como {m(1), m(2), ... m(w)} Ì {X(1), X(2), ..., X(w+1)}, a também
pertence a seqüência X e logo teremos provado que X é sobrejetora.



Se m(v) = m(u) para todo v > u, temos

S(v) = m(u).v

S(v+1) = m(u).(v+1)

S(v+1) = S(v) + X(v+1) Þ X(v+1) = m(u)

S(v+2) = m(u).(v+2) = S(v+1) + X(v+2) Þ X(v+2) = m(u),



mas aí X(v + 2) Î {X(1)... X(v+1)}, o que contraria a definição da
seqüência!

X é injetora e sobrejetora, logo é bijetora.

[ ]'s