Existence of $j$ with strange sequence. I define a sequence $(a_n)$
$$a_n=
\begin{cases}
0 &\text{if $\cos{\left ( \dfrac{2^n\pi}{q}\right )}<-\dfrac12$} \\\\
1 &\text{if $\cos{\left ( \dfrac{2^n\pi}{q}\right )}>-\dfrac12$}
\end{cases}$$
where any two prime number $p$, $q$ such that $p\geq 5$, $q=2p+1$. Show that there exist $j$ such that $$a_1a_{p-j+1}+a_2a_{p-j+2}+\cdots+a_ja_p+a_{j+1}a_1+a_{j+2}a_2+\cdots+a_pa_{p-j}
$$ is an even number with $0\leq j \leq p-1$.
This problem is from POSTECH(POHANG UNIVERSITY OF SCIENCE AND TECHNOLOGY) mathematical contest for high school students in 2010. I tried long time but can't solve it. Please solve this problem. Thanks in advance.
 A: A partial solution that covers half the cases. I need the extra assumption that $p\equiv1\pmod4$.
From Little Fermat we get that $2^p\equiv\pm1\pmod q$, so $2^p=kq\pm1$ for some integer $k$. Write $\omega=2\pi/q$, so $kq\omega$ is a multiple of $2\pi$. We have
$$
\cos(2^{n-1+p}\omega)=\cos(2^{n-1}\cdot2^p\omega)=\cos(2^{n-1}(kq\pm1)\omega)=\cos(2^{n-1}\omega),
$$
because cosine is an even function. This implies that $a_{n+p}=a_n$ for all $n$, i.e. the sequence is periodic with period $p$. 
This allows us to rewrite the sums as
$$
\theta(j)=\sum_{i=1}^pa_ia_{i+j},
$$
and the task is to show that $\theta(j)$ is even for some $j$.
Let us study the number
$$
S=\theta(0)=\sum_{i=1}^pa_i^2=\sum_{i=1}^pa_i
$$
that counts the number of ones within a period. Next I claim that we have $S=(2p-1)/3$. This needs a few facts about the structure of $\mathbb{Z}_q^*$. This group is cyclic of order $q-1=2p$, and it is easy to see that the order of $2$ is either $p$ or $2p$ according to whether $2$ is a quadratic residue modulo $q$ or not. As $-1$ is not a quadratic residue, this means that the cosines
$$
\cos(2^k\omega),\quad k=0,1,\ldots p-1,
$$
are all distinct, and thus the same set of numbers as $\cos \ell\omega, \ell=1,2,\ldots,p.$ I could not ascertain the level of the competition. It should be possible to translate this step into a high school level argument, if so desired.
Anyway, $\cos\ell\omega>-1/2, 0<\ell\le p,$ if and only if $\ell\omega<2\pi/3$. This holds, iff $\ell<q/3$, so we get that the number of ones within a period is
$$
S=\left[\frac q3\right].
$$
For $p>3$ and $2p+1$ to both be primes, it is necessary that $p$ and $q$ are both $\equiv-1\pmod3$. Therefore $q-2$ is divisible by three, and thus
$$
S=\left[\frac q3\right]=\frac{q-2}3=\frac{2p-1}3
$$
as claimed. Observe that as we have $p\equiv -1\pmod6$, $S$ is an odd integer. This is bad news in a sense, as otherwise we could pick $j=0$, but we can still use this bit of information.
Periodicity of the sequence implies that $\theta(j)=\theta(p-j)$ for all $j$.
Thus the values of $\theta(j), p\nmid j,$ come in pairs. Let us combine this with the observation that
$$
\sum_{j=0}^{p-1}\theta(j)=\sum_{i,j}a_ia_{i+j}=S^2
$$
that follows from the observation that in the double sum we have all the entries $a_i$ multiplied by all the entries $a_{i+j}$, both indices ranging over a full period.
Assume contrariwise that $\theta(j)$ is an odd integer for all $j$. This implies
that
$$
S^2=\sum_{j=0}^{p-1}\theta(j)=\theta(0)+2\sum_{j=}^{(p-1)/2}\theta(j)
\equiv\theta(0)+\sum_{j=1}^{(p-1)/2}2=S+(p-1)\pmod4,
$$
as any odd number multiplied by two gives a result $\equiv2\pmod4.$
As $S$ is known to be odd, $S^2\equiv1\pmod4$. On the other hand
$$
S+(p-1)=\frac{5p-4}3.
$$
If $p\equiv1\pmod4$, then also $5p-4\equiv 1\pmod4$ and $(5p-4)/3\equiv3\pmod4$.
This is a contradiction, and we can deduce that if $p\equiv1\pmod4$, then $\theta(j)$ must be even for some $j$.
Unfortunately in the other case $p\equiv3\pmod4$ the above argument only shows that the number of even integers among $\theta(j),j=1,2,\ldots,(p-1)/2$ is even, and we cannot deduce, unlike in the treated case, that there would be any.
