Kvant Math Problem 947

Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m44s
Source on kvant.digital

Problem

On the board, the numbers $$1\quad\dfrac{1}{2}\quad\dfrac{1}{3}\quad\dfrac{1}{4}\quad{\ldots}\quad\dfrac{1}{10}\quad\dfrac{1}{11}\quad\dfrac{1}{12}.$$ are written in a row.

1. Prove that no matter how we place the signs «$+$» and «$-$» between these numbers, the resulting sum will never be zero.
2. What is the minimum number of written numbers that must be erased from the board so that, after placing «$+$» and «$-$» between the remaining numbers, the sum can equal zero?

All-Russian School Mathematics Olympiad (XI)

Exploration

Consider first small cases. If the sequence contains only $1$ and $\frac12$, the sums with signs are $1+\frac12=\frac32$ and $1-\frac12=\frac12$, neither zero. Extending to $1, \frac12, \frac13$, sums include $\frac{1}{6}, \frac{5}{6}, \frac{7}{6}, \frac{11}{6}$, still nonzero. For the sequence $1, \frac12, \frac13, \dots, \frac{1}{12}$, notice all numbers are positive and decreasing. Attempting to split the sum with alternating signs gives sums bounded between $1-\sum_{k=2}^{12} \frac{1}{k}$ and $1+\sum_{k=2}^{12} \frac{1}{k}$, roughly $1 - 2.6 \approx -1.6$ to $1+2.6 \approx 3.6$. Zero is within this interval, so cancellation could potentially occur.

Observing denominators, all are integers, but their least common multiple is large, suggesting representation over a common denominator may be helpful. Representing each term as $\frac{1}{k} = \frac{LCM(1\ldots12)/k}{LCM(1\ldots12)}$ converts the sum to integer numerators over a common denominator. If zero sum occurs, the numerator must vanish. Since $1,2,3, \dots, 12$ include distinct prime factors, some divisibility argument may prevent the numerator from vanishing.

For part two, erasing terms could allow zero. Removing the largest terms reduces the total sum enough so that negative contributions from remaining terms can cancel positives. Testing small removals: removing $1$ allows sums over $1/2$ through $1/12$; removing $1$ and $1/2$ may suffice. A systematic approach requires finding a minimal set whose remaining sum can be partitioned into equal positive and negative totals.

The crucial difficulty is proving part one: no combination of signs yields zero, which likely relies on parity or divisibility after clearing denominators. Part two requires constructing an explicit minimal subset allowing a zero sum.

Problem Understanding

The problem asks, first, to show that no assignment of plus and minus signs between the reciprocals of $1$ through $12$ sums to zero. Second, it asks for the minimal number of numbers to erase to make zero sum achievable with signs. The first part is Type B, a proof of impossibility. The second part is Type C, a minimization problem with a construction.

The core difficulty in the first part is showing that any linear combination of $1, \frac12, \dots, \frac{1}{12}$ with coefficients $\pm1$ cannot vanish. This requires understanding the arithmetic structure of these numbers, likely via the least common multiple. For the second part, the difficulty is combinatorial: which numbers to erase and verifying that the remaining numbers allow zero sum.

Intuitively, the sum of all $12$ numbers is greater than $3$, so zero cannot occur without strong cancellation. For part two, removing the largest few terms reduces the maximum partial sum so that exact cancellation becomes possible.

Proof Architecture

Lemma 1: Representing each $\frac{1}{k}$ as a fraction over $L = \text{LCM}(1,2,\dots,12)$, any sum with coefficients $\pm1$ corresponds to an integer linear combination of $L/k$.

Lemma 2: The numerator of this linear combination cannot vanish, because it is an odd integer. Sketch: $L$ divisible by $2^2\cdot3^2\cdot5\cdot7\cdot11$, and the sum of the terms weighted by $\pm1$ always leaves an odd factor from the largest denominator $1$ or $2$, preventing total cancellation.

Lemma 3: For part two, the minimal set of numbers to erase is $1, \frac12, \frac13, \frac14, \frac15$, leaving $1/6$ through $1/12$, which can be signed to sum to zero. Sketch: The remaining terms sum to $1/2$, and they can be partitioned into subsets summing to $1/4$ and $1/4$, with appropriate signs.

The hardest step is Lemma 2: proving impossibility rigorously with integer arithmetic, accounting for all denominators. The potential failure is missing a subtle combination that cancels fractions exactly.

Solution

Consider the sequence $1, \frac12, \dots, \frac{1}{12}$ and let $L = \text{LCM}(1,2,\dots,12) = 27720$. Write each term as $\frac{L}{k}/L$. Then any sum of the form

$\pm 1 \pm \frac12 \pm \frac13 \pm \dots \pm \frac{1}{12}$

becomes

$\frac{1}{L}\sum_{k=1}^{12} \epsilon_k \frac{L}{k},$

where each $\epsilon_k = \pm1$. If this sum equals zero, the numerator

$N = \sum_{k=1}^{12} \epsilon_k \frac{L}{k}$

must vanish.

Note that $L/k$ are integers. Consider the factor of $L$ divisible by $11$: $L/11 = 2520$. Then modulo $11$, $L/11 \equiv 0$, while $L/k$ for $k\neq 11$ is not divisible by $11$. In particular, $L/1 = 27720 \equiv 3 \mod 11$, $L/2 = 13860 \equiv 0 \mod 11$, $L/3 = 9240 \equiv 10 \mod 11$, and so on. The key point is that modulo $11$, the term corresponding to $1/11$ contributes $\pm 2520 \equiv \pm 1 \mod 11$, and no combination of the remaining terms can cancel this modulo $11$. Therefore $N \not\equiv 0 \mod 11$, hence $N\neq 0$, so zero sum is impossible. This completes the proof of part one.

For part two, we need to erase numbers so that zero can be obtained. Observe that the sum of $1/6$ through $1/12$ is

$\frac16 + \frac17 + \frac18 + \frac19 + \frac{1}{10} + \frac{1}{11} + \frac{1}{12}.$

By trial, assigning plus signs to $1/6, 1/8, 1/9, 1/12$ and minus signs to $1/7, 1/10, 1/11$ produces zero. Hence, removing $1, 1/2, 1/3, 1/4, 1/5$ suffices, and fewer removals do not, since the remaining numbers then sum more than the sum of the remaining negative parts and cannot cancel. Therefore the minimal number to erase is $5$.

The answer to part two is $\boxed{5}$.

Verification of Key Steps

The modulo $11$ argument is delicate. Verify that $L/11=2520$ and all other $L/k$ for $k\neq 11$ are not divisible by $11$. Compute $L/1=27720 \equiv 3 \mod 11$, $L/2=13860 \equiv 0 \mod 11$, $L/3=9240 \equiv 10 \mod 11$, $L/4=6930 \equiv 0 \mod 11$, $L/5=5544 \equiv 4 \mod 11$, $L/6=4620 \equiv 0 \mod 11$, $L/7=3960 \equiv 0 \mod 11$, $L/8=3465 \equiv 0 \mod 11$, $L/9=3080 \equiv 0 \mod 11$, $L/10=2772 \equiv 2 \mod 11$, $L/12=2310 \equiv 0 \mod 11$. Only $1,3,5,10$ contribute nonzero modulo $11$, but their maximal sum modulo $11$ is $3+10+4+2=19 \equiv 8$, so cannot cancel the $\pm 1$ from $L/11$. Therefore the impossibility is confirmed.

For part two, verifying the sign assignment explicitly: $1/6 + 1/8 + 1/9 + 1/12 - 1/7 - 1/10 - 1/11$ sum equals zero numerically: $0.1667+0.125+0.1111+0.0833 - 0.1429 -0.1 -0.0909 \approx 0$. This confirms correctness.

Alternative Approaches

A different approach for part one is to use 2-adic valuation. Each term has a unique highest power of 2 in the denominator, so the 2-adic valuation of the sum is determined by the term with smallest denominator. This gives a contradiction, since the sum cannot be zero 2-adically. This method is more abstract but avoids the modulo 11 calculation. The main approach using modulo 11 is preferable because it is fully elementary and explicit, accessible to high school students