Problem 1566

1. Define the vectors:
Let $v_i$ be the vector representing the answers on the $i$-th day, where $v_i = (a_{i1}, a_{i2}, \ldots, a_{in})$ and $a_{ij} = 1$ if the $j$-th person answered "yes" on the $i$-th day, and $a_{ij} = -1$ if the $j$-th person answered "no".

2. Orthogonality condition:
The problem states that on any two distinct days, exactly half of the persons gave the same answer. This implies that the dot product of any two distinct vectors $v_i$ and $v_j$ is zero:
$$v_i \cdot v_j = 0 \quad \text{for} \quad i \neq j$$
This orthogonality condition means that the vectors are orthogonal in $\mathbb{R}^n$.

3. Norm of the vectors:
Each vector $v_i$ has a norm squared equal to $n$:
$$v_i^2 = \sum_{j=1}^n a_{ij}^2 = n$$
because each $a_{ij}$ is either $1$ or $-1$.

4. Sum of vectors:
Let $x_j$ be the sum of the answers of the $j$-th person over $k$ days:
$$x_j = \sum_{i=1}^k a_{ij}$$
We need to show that there are at most $n - \frac{n}{k}$ persons whose "yes" answers equal their "no" answers over $k$ days.

5. Sum of squares:
Consider the sum of the squares of $x_j$:
$$\sum_{j=1}^n x_j^2 = \sum_{j=1}^n \left( \sum_{i=1}^k a_{ij} \right)^2$$
Using the orthogonality condition, we can write:
$$\sum_{j=1}^n x_j^2 = \left| \sum_{i=1}^k v_i \right|^2 = \sum_{i=1}^k v_i^2 = kn$$

6. Contradiction:
If there are more than $n - \frac{n}{k}$ persons whose "yes" answers equal their "no" answers, then the number of such persons is greater than $n - \frac{n}{k}$. Let $m$ be the number of persons whose "yes" answers equal their "no" answers. Then:
$$m > n - \frac{n}{k}$$
For these $m$ persons, $x_j = 0$. For the remaining $n - m$ persons, $x_j \neq 0$. Therefore:
$$\sum_{j=1}^n x_j^2 \geq (n - m) \cdot 1^2 = n - m$$
Since $m > n - \frac{n}{k}$, we have:
$$n - m < \frac{n}{k}$$
Thus:
$$\sum_{j=1}^n x_j^2 < k \cdot \frac{n}{k} = n$$
This contradicts the earlier result that $\sum_{j=1}^n x_j^2 = kn$.

Therefore, the assumption that there are more than $n - \frac{n}{k}$ persons whose "yes" answers equal their "no" answers leads to a contradiction.

$\blacksquare$