Mariusz Marszałkowski wrote:

Dobra, porachowalem to juz, ale nadal nie moge dojsc jak autorzy przeszli
nad tymi rachunkami do porzadku i od razu "widzieli" wynik.

Wybor konkretnych elementow nie ma znaczenia, to co ma znaczenie, to
odleglosc miedzy nimi L=j-i+1.

Niech P(N,L) oznacza prawd. porownania tych elementow. N rozmiar sekwencji.

Fakty:
P(N,2) = 1
P(N,L) = 2/N+1/N * ( P(N-1,L)+P(N-2,L)+P(N-3,L)+...+P(L,L) )

Ta suma wyglada paskudnie, ale policzylem na piechote wartosci dla L=3 i N 3
i 4 wynik wychodzil 2/3. Moze przypadek, ale sprawdzilem, czy faktycznie
P(N,L) nie rowna sie 2/L. Tak po prostu.

P(N,L=2) = 1 = 2/2 = 2/L
ok

zalozmy P(N,L) = 2/L

i sprawdzmy:
P(N+1,L) = 2/(N+1) + 1/(N+1) * ( P(N,L) + P(N-1,L)+...+ P(L,L) ) = 2/(N+1) +
(N-L+1)*1/(N+1)*2/L = 2/L

Koniec dowodu.

milego dnia, hej

do góry