Problema 400
27 Octombrie 2012
Jocul arborelui lui Fibonacci
Un arbore Fibonacci e un arbore binar definit recursiv în felul următor:
- T(0) e arborele vid.
- T(1) e arborele binar cu un singur nod.
- T(k) constă dintr-un nod rădăcină care are nodurile T(k-1) și T(k-2) drept fii.
Pe un astfel de arbore, 2 jucători joacă un joc de preluare. În fiecare rundă, un jucător alege un nod și îl îndepărtează împreună cu subarborele care are rădăcina în acel nod.
Jucătorul care e forțat să îndepărteze rădăcina întregului arbore pierde.
Aici sunt mutările primului jucător în prima runda pentru T(k) unde k ia valori de la 1 la 6.
De exemplu, f(5) = 1 și f(10) = 17.
Află f(10000). Introdu ultimele 18 cifre ca răspuns.