Egy csiga mászik fel egy fán. Minden nappalon 1 métert halad felfelé, de minden éjszakán az addig megtett teljes út felével visszacsúszik. Mikor ér 1,5 méter ill 2 méter magasra?

2nap alatt 1.5

2 méterre pedig vagy 3 nap vagy 20on valamennzi

Ha rekurzív függvényként írjuk fel (olyan függvény, ami önmagára hivatkozik):

f(0):=0

f(x+1):=(f(x)/2)+1

Ugye f az x+1 helyen az előző helyen vett érték fele (éjszaka lecsúszik) +1 (amit nappal felmászik)

azaz:

f(1)=1

f(2)=1,5

f(3)=1,75

f(4)=1,875

...

A felsorolásból látszik, hogy 1,5 métert már a 2. napon eléri. 2 méterre viszont (sejtésünk szerint) soha nem jut el. Lássuk így van-e:

tegyük fel, hogy valamilyen x-re f(x+1)=2

Ekkor:

(f(x)/2)+1=2

f(x)/2=1

f(x)=2

Baj van. A levezetés szerint x+1=x=2 Bármilyen x esetében. Ez viszont azt jelenti, hogy a függvénynek visszamenőleg minden értékének 2-nek kéne lennie (mivel f(x+1) csak akkor lesz 2, ha f(x) is 2), ez viszont a kezdeti felsorolásunkból látszik, hogy nem igaz.

Tehát a csiga soha nem éri el a 2 métert.

Egy másik, "fapadosabb" megközelítés, amihez nem kell rekurzív függvényt felírni az, hogy a csiga felmászik 1 métert, majd lecsúszik féltávra: kapunk egy 1-nél kisebb számot. Ehhez 1-et hozzáadva 2-nél kisebb számot kapunk, amit felezve ismét 1-nél kisebb számot kapunk.

Ha x<1 akkor x+1<2, viszont ha x+1<2 akkor (x+1)/2<1, konkrét értékek kiszámolása nélkül is látszik, hogy mindig 2-nél illetve 1-nél kisebb számokat fogunk kapni, mert 1-nél kisebb számot 1-el növelve mindig 2-vel kisebb számot kapunk, amit felezve mindig 1-nél kisebb számot kapunk vissza, és a ciklus indul elölről. :D

2-nél*

Apró elírás :)