, 2021

Solution:

The maximum number is $n-1$. We first prove the upper bound. For simplicity, color all negative numbers red, and all non-negative numbers blue. Let $X$ be the number of color changes among adjacent elements (i.e. pairs of adjacent elements with different colors). It is clear that the following two statements are true:
(1) When $a_{1}$ changes sign, $X$ decreases by 1. If $a_{1}$ changes from negative (red) to non-negative (blue), $a_{2}$ must have been non-negative (blue), so the first two colors changed from $R B$ to $B B$. The same applies when $a_{1}$ changes from non-negative to negative.
(2) $X$ cannot increase after a move. Suppose Alice picks $a_{i}$ for her move where $1 \leq i \leq n$. If $a_{i}$ does not change sign, then $X$ clearly remains the same. Else, if $a_{i}$ changes sign and $i=1$ or $n$, then $X$ decreases by 1 (from (1)). Finally, if $a_{i}$ changes sign and $i \neq 1, n$, we have two cases:

Case 1: $a_{i-1}, a_{i+1}$ are of the same color. If they are both negative (red), then if $a_{i}$ changes color, it must be from non-negative to negative (blue to red). Thus, the colors change from $R B R$ to $R R R$ and $X$ decreases by 2. The same holds if both $a_{i-1}, a_{i+1}$ are non-negative.

Case 2: $a_{i-1}, a_{i+1}$ are of different colors. No matter what the color of $a_{i}$ is, there is exactly one color change among the three numbers, so $X$ will remain the same.

Now, since the initial value of $X$ is at most $n-1$, it can decrease by 1 at most $n-1$ times. Hence, $a_{1}$ can change signs at most $n-1$ times.

Now we prove the lower bound by constructing such a sequence inductively. Specifically, we induct on the following statement:
For every $n \geq 2$, there exists a sequence $a_{1}, a_{2}, \cdots, a_{n}$ such that by picking
$$a_{1}, a_{2}, a_{1}, a_{3}, a_{2}, a_{1}, \cdots, a_{n-1}, a_{n-2}, \cdots, a_{2}, a_{1}$$
in that order, $a_{1}$ changes sign $n-1$ times.

When $n=2$, we can let $a_{1}$ change sign once by starting with the sequence $(1,-3)$, and picking $a_{1}$ to obtain $(-1,-3)$, which satisfies the conditions in our statement.

Suppose we have proven the statement for $n-1$. For $n$, let $a_{1}, a_{2}, \cdots, a_{n-1}$ be as defined in our construction for $n-1$ (we shall fix the value of $a_{n}$ later). After executing the steps $a_{1}, a_{2}, a_{1}, a_{3}, a_{2}, a_{1}, \cdots, a_{n-2}, a_{n-3}, \cdots, a_{2}, a_{1}$, $a_{1}$ would have changed sign $n-2$ times.

It now remains to pick $a_{n-1}, a_{n-2}, \cdots, a_{2}, a_{1}$ in order so that $a_{1}$ changes sign one more time. This is always possible as long as $a_{n}$ is sufficiently large in magnitude and of the opposite sign as $a_{1}$. Since the value of $a_{n}$ has remained unchanged since the start (as we have not picked $a_{n}$ at all), it suffices to let $a_{n}$ be a number satisfying the above conditions at the start.

This completes our induction, and we conclude that the maximum number of times that $a_{1}$ can change sign is $n-1$.