Problem 1011

Let's define the numbers $a_{ij}(1 \leq i \leq 24, 1 \leq j \leq 25)$ as follows: $a_{ij}$ is 1 if the $i$-th student solved the $j$-th problem, and 0 otherwise. We need to prove that there exist integers $x_{j}(1 \leq j \leq 25)$, not all zero, such that

$$\begin{aligned} & a_{1,1} x_{1} + a_{1,2} x_{2} + \ldots + a_{1,25} x_{25} = 0 \\ & a_{2,1} x_{1} + a_{2,2} x_{2} + \ldots + a_{2,25} x_{25} = 0 \\ & \quad \ldots \\ & a_{24,1} x_{1} + a_{24,2} x_{2} + \ldots + a_{24,25} x_{25} = 0 \end{aligned}$$

From the theory of linear systems, it is known that if the number of equations is less than the number of unknowns, then the homogeneous system has a non-trivial solution. Moreover, since the coefficients of our system are rational, it has a non-trivial solution in rational numbers. If we multiply all these numbers by the least common multiple of the denominators, we will obtain a solution in integers.
a) The first method. Suppose a set of integers $x_{j}$ satisfying the system from b) has already been found. We can assume that not all $x_{j}$ are even, otherwise we divide all the numbers by 2. Replace all even numbers $x_{j}$ with 0 and all odd numbers with 1, and mark the problems corresponding to 1. Clearly, each sum $\sum_{j} a_{ij} x_{j}$ remains even (since each term is changed by an even number). Therefore, each student solved an even number of marked problems.

The second method. For each of the $2^n$ subsets of the set of problems, assign the digit 1 to those students who solved an odd number of problems and 0 to those who solved an even number of problems from this subset. Thus, each subset $A$ corresponds to a column of height $m$ consisting of zeros and ones. There are a total of $2^m < 2^n$ different columns of height $m$. Therefore, there will be two different subsets $A$ and $B$ that correspond to the same column. Now, mark the problems that belong to exactly one of the sets $A$ and $B$, i.e., the problems in the set

$A \Delta B$.

Since each student solved an odd number of problems from $A$ and $B$ with the same parity, the number of problems solved in $A \Delta B$ is even (it is equal to the sum of the number of problems solved from $A$ and $B$ minus twice the number of problems solved from $A \cap B$).