Feladat: 16.13.
Függönyt szeretnénk felcsipeszelni. Akkor
könny? egyenletesen elosztani a csipeszeket, ha
először felcsiptetjük a két szélét, majd a
közte levő részt felezzük, aztán a csipeszek
közötti részeket tovább felezzük és
így tovább.
Hány csipesz legyen a karnison, hogy ez a módszer
m?ködjön?
Megoldás: 16.13
Kevés csipesz esetén pl. a 3 nyilván jó megoldás.
Viszont ha
k jó megoldás, akkor 2
k-1 is az, hiszen a
középső csipesz mindkét oldalán ugyanaz az algoritmus
m?ködik, viszont a középső csipeszt csak egyszer kell
számolni. Ezért a szükséges csipeszek száma
2n
-1.