There are $N$ sticks ($N \ge 3$) of same size kept such that they make a regular polygon. Now one of the sticks from the polygon is removed to make it an open polygon.

Alex and Bob are playing a game (starting with Alex) in which they perform the following moves. A player chooses a stick and removes it. Now we have two sets of connected sticks that were originally in contact with the removed stick. The one with the smaller length is also removed with along with the selected stick. If both of the sets are of same size any one is removed. The person who can not make a move in their turn loses.

Example for $N=6$:

One of the sticks is removed and the figure looks like this.

Now, if the chosen stick is terminal one like 1 or 5 then only that particular stick is removed. If some other stick is chosen (say stick numbered 2) then on removing there will be 2 sets of connected sticks. The set with less number of sticks gets removed too, and thus the stick with number 1 will also be removed.

You are required to find how many starting positions are there below $N = 10^{10^6}$ such that Alex loses, assuming that both Alex and Bob play optimally.

A tutorial on Game Theory