, 2014

Solution: Observing small cases (such as $n=3$), it is easy to conjecture that
$$a_{ij} = (-1)^{i+j},\ b_i = 1$$
satisfies the requirements of the problem. Thus what remains difficult is to prove that this indeed satisfies the requirements of the problem. Note that $z$ and $x_1x_2\cdots x_n$ also each have only the two possible values $1, -1$. We have $x_1x_2\cdots x_n = 1$ if and only if there is an even number of $-1$'s among the $x_j$; on the other hand, since $b_i = 1$, in this case $z$ is
$$z = \operatorname{sign}\left(\sum_{i=1}^{n} y_i\right) \qquad (1)$$
Hence $z = 1$ if and only if $\sum_{i=1}^n y_i \ge 0$, that is, the number of $y_i$'s equal to $1$ exceeds the number equal to $-1$ (since $y_i \in \{1,-1\}$).
Thus our goal is equivalent to proving: "the number of $y_i$'s equal to $1$ exceeds the number equal to $-1$" if and only if "there is an even number of $-1$'s among the $x_j$."
Returning to the formulas. Let $y'_i$ denote the value in the formula for $y_i$ before applying sign, i.e.
$$y'_i = \sum_{j=1}^{n} (-1)^{i+j} x_j \qquad (2)$$
and $y_i = \operatorname{sign}(y'_i)$. Adding $y'_i$ and $y'_{i+1}$ gives the identity $y'_i + y'_{i+1} = 2x_j$ (here $y_{n+1} = y_1$). If $x_j = 1$, then except for the case $y'_i = y'_{i+1} = 1$, in all other cases $y'_i, y'_{i+1}$ have opposite signs (note that $y'_i$ must be odd); conversely if $x_j = -1$, then except for the case $y'_i = y'_{i+1} = -1$, in all other cases $y'_i, y'_{i+1}$ also have opposite signs. Therefore, except for the two cases $y'_i = y'_{i+1} = x_j = 1$ or $y'_i = y'_{i+1} = x_j = -1$, the values of $y_i$ and $y_{i+1}$ are exactly one $1$ and one $-1$.
Below we consider the case where there is an even number of $-1$'s among the $x_j$. We first prove that $y'_i \ne -1$. According to
$$\begin{aligned} y'_i &= \sum_{j=1}^{n} (-1)^{i+j} x_j \\ &= \sum_{x_j=1} (-1)^{i+j} x_j + \sum_{x_j=-1} (-1)^{i+j} x_j \\ &= \sum_{x_j=1} (-1)^{i+j} + \sum_{x_j=-1} (-1)^{i+j} (1-2) \\ &= \sum_{1 \le i \le n} (-1)^{i+j} - 2 \sum_{x_j=-1} (-1)^{i+j} \\ &= 1 - \sum_{x_j=-1} 2(-1)^{i+j} \end{aligned}$$
Since regardless of the value of $i + j$, $2(-1)^{i+j} \pmod 4$ is always congruent to 2 modulo 4, we have
$$\begin{aligned} y'_i &\equiv 1 - \sum_{x_j=-1} 2(-1)^{i+j} \pmod 4 \\ &\equiv 1 - \sum_{x_j=-1} 2 \pmod 4 \\ &\equiv 1 \pmod 4 \end{aligned}$$
The last equality is exactly because there is an even number of $x_j = -1$. Thus we have proven $y'_i \neq -1$.
Next we prove that there must be some $i$ for which $y'_i = y'_{i+1} = x_j = 1$ occurs. Otherwise, if this does not happen, since $y'_i = y'_{i+1} = x_j = -1$ is also already impossible, this means that for all $i$, $y_i$ and $y_{i+1}$ are exactly one 1 and one $-1$, so
$$\sum_{i=1}^{n} y_i = \frac{1}{2} \sum_{i=1}^{n} (y_i + y_{i+1}) = 0$$
But since $n$ and $y_i$ are odd, $\sum_{i=1}^{n} y_i$ is also odd, a contradiction.
Therefore, if we let $s$ denote the sum over all $i$ of "the number of 1's among $y_i$ and $y_{i+1}$", its value must equal twice the number of 1's among $y_1, \cdots, y_n$ (since each $y_i$ is counted twice). By the two facts proven above, $y_i$ and $y_{i+1}$ must have at least one equal to 1, and there must be some $i$ such that $y_i$ and $y_{i+1}$ are both 1, so $s \ge n$, from which we deduce that the number of 1's among $y_1, \cdots, y_n$ must exceed the number of $-1$'s.
And when there is an odd number of $-1$'s among the $x_j$, through the same proof process we can obtain $y'_i \neq 1$, and that there must be some $i$ for which $y'_i = y'_{i+1} = x_j = -1$ occurs, thereby obtaining that the number of values equal to $-1$ among $y_1, \cdots, y_n$ exceeds the number of values equal to 1. This completes the proof.