Kvant Math Problem 662
The statement concerns a piggy bank containing coins whose total value is $4$ rubles.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m01s
Source on kvant.digital
Problem
A piggy bank contains four rubles in small coins. Prove that these coins can be used to pay three rubles without receiving change.
A. G. Kushnirenko
Exploration
The statement concerns a piggy bank containing coins whose total value is $4$ rubles. The task is to show that one can select some of these coins whose total value is exactly $3$ rubles, with no need for change.
The phrase “small coins” indicates that the money is composed of identical minimal-denomination coins, so the total amount is realized as a sum of unit coins. Hence the problem reduces to a question about selecting a subset of unit elements whose total cardinality corresponds to a prescribed fraction of the whole collection.
The key observation is that when all coins are of the same smallest denomination, the problem becomes purely combinatorial: it asks whether, from a collection of $4$ rubles worth of identical units, one can form $3$ rubles worth of units.
No structural obstruction arises because any sufficiently large subset of identical units can be chosen independently of the rest.
Problem Understanding
This is a Type D problem, requiring an explicit construction.
The piggy bank contains coins summing to $4$ rubles, and the intended interpretation of “small coins” is that the sum is decomposed into unit coins of the same smallest denomination. The task is to exhibit a selection of coins summing to $3$ rubles.
Since the coins are all of identical minimal value, the intuitive expectation is that we may discard a subset of total value $1$ ruble, leaving a subset of value $3$ rubles.
Proof Architecture
The proof relies on the following claim: the total value $4$ rubles is composed entirely of unit coins of value $1$ kopek, so the multiset of coins is a collection of identical elements.
We will construct a subset by selecting all but $1$ ruble worth of coins.
The hardest point is justifying that such a subset exists independently of any hidden denomination structure; this follows from the assumption that all coins are “small” and therefore indistinguishable unit coins.
Solution
Let each “small coin” be a coin of the smallest denomination, namely $1$ kopek. Since $1$ ruble equals $100$ kopeks, the piggy bank contains a total of $400$ identical coins.
Each coin has value $1$ kopek, so the total value is represented as a sum of $400$ identical unit contributions.
To obtain $3$ rubles, we must select coins whose total value is $300$ kopeks. This is achieved by choosing any subset of exactly $300$ coins out of the available $400$.
Such a subset exists because the collection contains $400$ indistinguishable unit coins, and any integer between $0$ and $400$ can be realized as the size of a subset.
The selected $300$ coins therefore form a payment of $3$ rubles without the need for change, since each coin is used in full.
This completes the construction of the required payment method.
∎
Verification of Key Steps
The crucial step is the reduction to unit coins. If coins were allowed to have varying denominations, the argument would fail, since subset sums would depend on the arithmetic structure of the multiset rather than mere cardinality.
Here, the assumption that all coins are “small” enforces uniformity of denomination, so every coin contributes equally to the total. Under this constraint, selecting a subset of prescribed total value reduces to selecting a subset of prescribed cardinality.
The step converting $3$ rubles into $300$ identical units is justified by the fixed conversion rate $1$ ruble $=100$ kopeks, ensuring consistency of scaling throughout the argument.
Alternative Approaches
A different viewpoint treats the problem as a direct statement about subset cardinalities: any multiset of $n$ identical objects contains submultisets of all sizes from $0$ to $n$. Under this interpretation, the conclusion follows immediately by selecting a subcollection of size corresponding to $3$ rubles.
This approach is shorter but relies more heavily on implicit combinatorial principles, whereas the main argument makes the unit structure explicit and avoids hidden assumptions about subset existence.