Iranian Mathematical Olympiad

a) Let $a_1 = 2, a_2 = 4, \dots, a_k = 2k, a_{k+1} = 1, a_{k+2} = 3, \dots, a_{2k} = 2k-1$. We can easily check that $a_i a_{i+1} + 1$ is a perfect square for $1 \le i \le 2k$ except $i = k$, which can be repaired if $2k+1$ is a perfect square which is possible for infinitely many values of $k$.

b) Let $a_1, a_2, \dots, a_n$ be a cubic permutation. Let $2^k$ be the largest power of $2$ less than or equal to $n$. By the definition of the cubic permutation we know that $2^k u + 1 = x^3$, where $u$ is an element of the permutation. So we have $2^k u = (x-1)(x^2+x+1)$. Hence we conclude that $2^k | (x-1)$. Because of the way that $k$ is chosen, we have $n < 2^{k+1}$. So we have $2^k \le x-1 \le n^{\frac{2}{3}} < 2^{\frac{2}{3}(k+1)}$ which is a contradiction. Hence no such permutation exists.