Problem

Source: 2002 Estonia National Olympiad Final Round grade 11 p5

Tags: combinatorics, octagon



Juku built a robot that moves along the border of a regular octagon, passing each side in exactly 1 minute. The robot starts in some vertex A and upon reaching each vertex can either continue in the same direction, or turn around and continue in the opposite direction. In how many different ways can the robot move so that after n minutes it will be in the vertex B opposite to A?