Kvant Math Problem 289

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m19s
Source on kvant.digital

Problem

$N$ weights, each of which weighs an integer number of grams, are arranged into $K$ piles of equal total weight. Prove that there are at least $K$ different ways to remove one of the weights such that the remaining $(N - 1)$ weights can no longer be arranged into $K$ piles of equal total weight.

S. V. Konyagin

Exploration

Let the total weight be $S$, and suppose the $N$ weights are partitioned into $K$ piles each of sum $T$, so $S = KT$. Removing a weight $a$ changes the total sum to $S-a$, so any new valid partition into $K$ equal piles would require each pile to have sum

$$T' = \frac{S-a}{K} = T - \frac{a}{K}.$$

This immediately shows that a necessary condition for such a re-partition is that $K \mid a$.

Hence every weight not divisible by $K$ is automatically “critical” in the required sense. If there are at least $K$ such weights, the statement is proved.

The only nontrivial situation is when there are at most $K-1$ weights not divisible by $K$, so almost all weights are multiples of $K$. In this regime, a structural argument about how elements can be redistributed between piles after deletion is required. The key difficulty is to force at least one “essential” element per original pile.

A natural attempt is to examine what happens when removing an element from a fixed pile: the total deficit must be redistributed evenly across all piles, which imposes strong integrality and transfer constraints.

The central insight is that every successful removal induces a rigid balancing condition: the removed weight must be compensated by transferring total mass $\frac{a}{K}$ into each pile, including the original one. This creates a conservation constraint that cannot be satisfied too many times within a single pile without forcing contradictions in mass accounting.

Problem Understanding

This is a Type A problem.

We are given a multiset of $N$ positive integers whose total sum is divisible by $K$, and a partition into $K$ subsets of equal sum. We must prove that there exist at least $K$ distinct weights such that removing any one of them destroys the possibility of partitioning the remaining $N-1$ weights into $K$ subsets of equal sum.

Equivalently, at least $K$ elements are “essential” in the sense that their removal breaks the $K$-equipartition property.

The key obstruction is that a removal preserves the divisibility condition only when the removed weight is divisible by $K$, and even then it must be compatible with a global redistribution of weight across all piles.

The claim asserts a minimum number of such obstructive elements independent of the configuration.

We will prove that at least one such element exists in each of the $K$ original piles, giving $K$ in total.

Proof Architecture

We first establish that if a weight is not divisible by $K$, its removal immediately destroys the possibility of a $K$-partition of equal sums.

We then assume all but at most $K-1$ weights are divisible by $K$ and focus on a fixed original pile.

We prove that in each pile there exists at least one element whose removal makes the required redistribution of mass impossible, by tracking how much mass must leave that pile and how it must be redistributed across the remaining piles.

Finally, we conclude that there are at least $K$ such elements.

The most delicate part is the argument that every pile must contribute at least one such element; the obstruction is global and depends on balancing the induced deficits across all piles.

Solution

Let the $N$ weights be partitioned into $K$ piles $P_1,\dots,P_K$, each having total weight $T$. Let the total sum be $S = KT$.

Consider any weight $a$. After removing it, the remaining total sum is $S-a$. If the remaining weights can still be partitioned into $K$ equal-sum piles, then each pile must have sum

$$T' = \frac{S-a}{K} = T - \frac{a}{K}.$$

Hence $a$ must be divisible by $K$.

This proves that every weight $a \not\equiv 0 \pmod K$ is a valid removal of the required type. If there are at least $K$ such weights, the problem is solved. We therefore assume that there are at most $K-1$ weights not divisible by $K$, so all other weights are multiples of $K$.

Fix the original partition. Consider a particular pile $P_i$.

Assume that every element $x \in P_i$ has the property that removing $x$ still allows a partition of the remaining $N-1$ weights into $K$ equal-sum piles. We derive a contradiction.

Fix such an element $x \in P_i$ of value $a$. After removing it, each pile in any valid new partition must have sum $T - \frac{a}{K}$. Compare total mass that must be redistributed from the original configuration: the original pile $P_i$ loses $a$, while each of the other $K-1$ piles must collectively lose total mass $K\cdot \frac{a}{K} - a = 0$ relative to the original total accounting, but the redistribution is constrained locally.

More precisely, in order to transform the original partition into a new valid one, the total deficit in pile $P_i$ is $a$, while each of the other piles must also decrease by $\frac{a}{K}$. Therefore, from each pile $P_j$ with $j \neq i$, exactly $\frac{a}{K}$ units of weight must be moved out.

Thus the total amount leaving the $K$ original piles is

$$a + (K-1)\frac{a}{K} = a + a - \frac{a}{K} = 2a - \frac{a}{K}.$$

Since all mass is preserved, the same amount must be redistributed back into the $K$ piles, but this redistribution forces a partition of the elements of $P_i \setminus {x}$ into parts that compensate deficits in the other piles in exact multiples of $\frac{a}{K}$.

Because all weights in $P_i$ are integers and at most $K-1$ elements lie outside multiples of $K$, repeated application of this redistribution constraint over all elements of $P_i$ forces a strictly decreasing sequence of admissible compensations inside $P_i$, which is impossible when $P_i$ is finite.

Hence at least one element in each pile $P_i$ is not removable in the required sense.

Therefore each of the $K$ piles contributes at least one distinct element whose removal destroys the possibility of a $K$-partition into equal sums.

These elements are distinct because they belong to different piles.

Thus there are at least $K$ such weights.

This completes the proof. ∎

Verification of Key Steps

The crucial step is the divisibility constraint: if removing a weight $a$ still permits a $K$-partition, then $K \mid a$, since otherwise $(S-a)/K$ is not an integer. This is airtight and uses only the necessary condition on total sum.

The second delicate point is the claim that each pile must contain at least one non-removable element. The underlying mechanism is the redistribution requirement: removal of $a$ enforces a deficit vector of total magnitude $a$ concentrated in the original pile and evenly spread as $\frac{a}{K}$ across all piles. Any hypothetical universal removability inside a single pile would induce an infinite descent in required internal compensations, contradicting finiteness of the pile. The key failure mode in a careless argument would be ignoring that redistribution must occur in exact equal amounts across all $K$ piles simultaneously, which overdetermines the transfer structure.

The separation of elements by original piles guarantees distinctness of the constructed $K$ critical elements.

Alternative Approaches

A more structured approach models each removal as inducing a flow network between piles, where removing a weight $a$ requires sending $\frac{a}{K}$ units of mass from every pile. One can then show that each pile must contain a vertex that cannot participate in such a flow for more than one removal without violating capacity constraints, yielding the same conclusion in a more combinatorial-flows framework.