GULF 2017 Problem 2

One country consists of islands $A_1,A_2,\cdots,A_N$ ,The ministry of transport decided to build some bridges such that anyone will can travel by car from any of the islands $A_1,A_2,\cdots,A_N$ to any another island by one or more of these bridges. For technical reasons the only bridges that can be built is between $A_i$ and $A_{i+1}$ where $i = 1,2,\cdots,N-1$ , and between $A_i$ and $A_N$ where $i<N$ .

We say that a plan to build some bridges is good if it is satisfies the above conditions , but when we remove any bridge it will not satisfy this conditions. We assume that there is $a_N$ of good plans. Observe that $a_1 = 1$ (The only good plan is to not build any bridge) , and $a_2 = 1$ (We build one bridge).

1-Prove that $a_3 = 3$ 2-Draw at least $5$ different good plans in the case that $N=4$ and the islands are the vertices of a square 3-Compute $a_4$ 4-Compute $a_6$ 5-Prove that there is a positive integer $i$ such that $1438$ divides $a_i$