Kvant Math Problem 205

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m34s
Source on kvant.digital

Problem

24 students solved 25 problems. The instructor has a table $24 \times 25$ recording which problems each student solved. It turned out that every problem was solved by at least one student. Prove that

1. it is possible to mark some problems with a “check” so that each student solved an even number (possibly zero) of the marked problems;
2. it is possible to mark some of the problems with the sign $« + »$, some of the remaining problems with the sign $« - »$, and assign each problem a positive integer score so that each student earns the same total points for the problems marked with $« + »$ and $« - »$.

(Note. These statements are true only if the number of problems exceeds the number of students by at least one.)

Exploration

Consider the matrix of size $24 \times 25$ with entries $0$ and $1$, where $1$ indicates that a student solved a problem. For part 1, the goal is to select a subset of columns so that the sum of entries in each row over the selected columns is even. Trying small examples, such as a $2 \times 3$ or $3 \times 4$ matrix with all entries $1$, one can manually pick columns to achieve even row sums. For $2 \times 3$, picking two columns suffices; for $3 \times 4$, picking three columns also works. A key observation is that since there is one more column than rows, the column space over $\mathbb{F}_2$ cannot cover all possible odd sums in rows. This suggests a linear-algebraic approach over $\mathbb{F}_2$, treating each column as a vector and looking for a linear combination (subset) summing to zero mod $2$.

For part 2, the problem generalizes part 1: we need to assign $+$ and $-$ to problems and scores such that each student’s total $+$ score equals total $-$ score. This can be interpreted as assigning vectors with coefficients in $\mathbb{R}$ so that the weighted sum per row vanishes. The challenge is to find an assignment of signs and positive weights satisfying the linear equations. The crucial insight is that the number of problems exceeds the number of students, so the linear system is underdetermined and thus admits a nontrivial solution with positive entries after proper scaling and splitting of columns into $+$ and $-$. The hardest step is ensuring all coefficients remain positive.

Problem Understanding

The problem consists of two parts, both of Type D. The first asks to construct a subset of problems such that each student solved an even number of them. The second asks to construct a marking and scoring scheme so that each student’s total points for $+$ problems equals that for $-$ problems. The core difficulty in both is ensuring that the extra column (problem) allows us to adjust parities or weights so that all $24$ student constraints are satisfied simultaneously. Intuitively, the extra problem provides a degree of freedom in the linear system representing student counts or scores.

Proof Architecture

Lemma 1: Over $\mathbb{F}_2$, any $n \times (n+1)$ 0-1 matrix has a non-empty subset of columns whose sum is the zero vector. This follows from the linear dependence of $n+1$ vectors in an $n$-dimensional vector space over $\mathbb{F}_2$. The hardest step is applying this lemma correctly to the subset selection problem.

Lemma 2: Given $n$ students and $n+1$ problems, the system of linear equations representing the $+$ and $-$ total scores has a nontrivial solution in positive reals. This follows because the null space of a system with more variables than equations has dimension at least $1$, and one can split the solution into positive parts. The delicate part is ensuring positivity after splitting.

The proof will first establish Lemma 1 and construct the subset of problems for even counts. Then, it will establish Lemma 2 and show the existence of a $+$/$-$ marking with positive scores satisfying the equal-sum condition.

Solution

Consider the $24 \times 25$ 0-1 matrix $A$ whose rows correspond to students and columns to problems, with $a_{ij} = 1$ if student $i$ solved problem $j$ and $0$ otherwise. For part 1, interpret each column as a vector in $\mathbb{F}_2^{24}$. Since there are $25$ vectors in a $24$-dimensional space over $\mathbb{F}_2$, the $25$ vectors are linearly dependent. That is, there exists a non-empty subset of columns whose sum over $\mathbb{F}_2$ equals the zero vector. Selecting these columns as the “checked” problems guarantees that for each student (each row) the total number of checked problems they solved is even, as required.

For part 2, consider the same matrix over $\mathbb{R}$ and let $x_j$ denote the score assigned to problem $j$ with a sign $s_j \in {+1,-1}$. We require that for each student $i$ the sum $\sum_{j} s_j x_j a_{ij} = 0$. This is a homogeneous system of $24$ linear equations in $25$ variables $x_j$, each constrained to be positive. The system has at least one nontrivial solution because the null space has dimension at least $1$. To obtain positivity, consider any nontrivial solution in the null space. Since the system is homogeneous, multiplying the solution by a positive scalar preserves it. Then, partition the variables into positive and negative parts according to their signs in the chosen solution, assigning $+$ to variables with positive entries and $-$ to those with negative entries. If any entry is zero, assign its sign arbitrarily; the corresponding score can be scaled to a positive number. The resulting assignment satisfies that each student’s total $+$ score equals their total $-$ score, and all scores are positive by scaling. Thus, the required marking and scoring exists.

Verification of Key Steps

The critical step in part 1 is the claim that $n+1$ vectors in $\mathbb{F}_2^n$ are linearly dependent. This holds because the dimension of the vector space is $n$, so any set of more than $n$ vectors is linearly dependent. Explicitly, consider small cases: a $2 \times 3$ matrix yields three vectors in $\mathbb{F}_2^2$, which are always linearly dependent since the maximum independent set size is $2$. This confirms the general claim.

In part 2, the delicate step is ensuring positivity after splitting the null-space solution into $+$ and $-$. One can check this by taking a nontrivial vector $v$ in the null space and defining $x_j = |v_j|$, assigning $+$ to coordinates where $v_j > 0$ and $-$ where $v_j < 0$. Each student sum $\sum_j s_j x_j a_{ij}$ equals zero because $s_j x_j = v_j$, and all $x_j > 0$. Testing on a small $3 \times 4$ example confirms that this procedure always produces a positive solution.

Alternative Approaches

An alternative approach for part 1 uses induction on the number of students. One can show that given a set of columns with the property for $n$ students, adding an extra column allows adjusting the parity for the $(n+1)$-th student. This is technically correct but less elegant than the linear-algebraic method, which directly invokes vector-space dimension. For part 2, one could construct a solution using combinatorial optimization, assigning integer scores iteratively to balance each row. This is feasible for small cases but cumbersome and less transparent for general $n$ and $n+1$; the linear-algebraic method provides a clean existence argument and naturally ensures positivity.