Kvant Math Problem 129

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

Problem

1. A bucket contains 12 L of milk. Using only 5 L and 7 L containers, how can you divide the milk into two equal parts?
2. Solve the general problem: for which $a$ and $b$ is it possible to divide $(a+b)$ L of milk in half using only $a$ L, $b$ L, and $(a+b)$ L containers?

V. V. Ushakov

Exploration

For the concrete problem with capacities $5$, $7$, and $12$, the target state is two portions of $6$ liters each. Since the only containers available have capacities $5$ and $7$, one natural idea is to obtain $1$ liter somewhere, because then the remaining $11$ liters split naturally as $5+6$ or $1+5+6$. Trying actual transfers quickly reveals a workable chain.

Fill the $5$ liter container from the bucket. Pour it into the $7$ liter container. Repeat. After the second transfer, the $7$ liter container already contains $5$ liters, so only $2$ more liters fit. Thus the second pouring leaves $3$ liters in the $5$ liter container. Pour these $3$ liters into the empty $7$ liter container. Then fill the $5$ liter container again and pour from it into the $7$ liter container, which already contains $3$ liters, so only $4$ liters fit. This leaves exactly $1$ liter in the $5$ liter container.

At that moment the total amount in the bucket is

$12-7-1=4.$

Pour out the $7$ liter container into the bucket. The bucket then contains $11$ liters. Pour the $1$ liter into the bucket as well. The bucket now contains $12$ liters again, but the important point is that we have learned how to isolate $1$ liter. From there it is straightforward to isolate $6$ liters.

A shorter route appears after isolating $1$ liter. If the $5$ liter container contains $1$ liter and the $7$ liter container is empty, fill the $7$ liter container from the bucket. The bucket now contains $4$ liters. Pour from the $7$ liter container into the $5$ liter container until the latter becomes full. Since it already contains $1$ liter, only $4$ liters are added. Thus the $7$ liter container is left with $3$ liters, while the bucket still contains $4$ liters. Empty the $5$ liter container into the bucket, giving $9$ liters there, and pour the $3$ liters into the $5$ liter container. Finally fill the $7$ liter container from the bucket, leaving exactly $2$ liters in the bucket, and pour $2$ liters from the $7$ liter container into the $5$ liter container, which already contains $3$ liters. Then the $5$ liter container becomes full and the $7$ liter container contains exactly $5$ liters. The bucket contains $2$ liters. This does not yet give halves, but it shows how flexible the process becomes once $1$ liter is obtainable.

The general problem suggests a number theoretic invariant. Every amount obtainable by repeated pouring should be an integer combination of $a$ and $b$. Since the target amount is $(a+b)/2$, divisibility conditions should appear. Testing examples clarifies the pattern.

Take $(a,b)=(2,4)$. Then the total is $6$, and we seek $3$. The greatest common divisor is $2$, which does not divide $3$. Direct experimentation fails.

Take $(a,b)=(2,6)$. Then the total is $8$, and we seek $4$. This is immediate, since the $a+b$ container can simply be split into two equal portions using the $6$ liter container and the bucket.

Take $(a,b)=(3,5)$. Then the total is $8$, and we seek $4$. Since $\gcd(3,5)=1$, this should be possible.

The likely criterion is

$\gcd(a,b)\mid \frac{a+b}{2}.$

Since $\gcd(a,b)$ always divides $a+b$, this condition fails only when both $a/d$ and $b/d$ are odd, where $d=\gcd(a,b)$. Equivalently,

$v_2(a)\ne v_2(b),$

where $v_2$ denotes the exponent of $2$ in the prime factorization.

The delicate point is sufficiency. One must prove not merely that the divisibility condition is necessary, but that every multiple of $\gcd(a,b)$ up to $a+b$ can actually be produced by pouring operations.

Problem Understanding

We are given three containers of capacities $a$, $b$, and $a+b$. Initially the largest container is full of milk and the other two are empty. By repeatedly pouring milk from one container to another until either the source is empty or the destination is full, we must determine when it is possible to divide the total amount into two equal portions.

This is a Type A problem. We must determine exactly for which pairs $(a,b)$ such a division is possible, and prove both necessity and sufficiency.

The core difficulty is to identify the correct invariant governing all attainable quantities, and then to prove that the invariant is also sufficient. The expected answer is that division into halves is possible precisely when

$\gcd(a,b)\mid \frac{a+b}{2}.$

Intuitively this should be correct because every transfer preserves the property that all quantities are multiples of $\gcd(a,b)$, while the Euclidean algorithm allows one to manufacture any multiple of $\gcd(a,b)$.

Proof Architecture

The first lemma states that throughout every pouring process, the amount of milk in each container is divisible by $d=\gcd(a,b)$; this follows because all capacities are divisible by $d$, and every transfer changes quantities by multiples of $d$.

The second lemma states that if the milk can be divided into two equal parts, then $(a+b)/2$ must be divisible by $d$; this is immediate from the first lemma.

The third lemma states that if $d=\gcd(a,b)$, then one can obtain exactly $d$ liters in one of the smaller containers; this is the standard Euclidean algorithm realized by successive pourings.

The fourth lemma states that once $d$ liters can be isolated, every multiple of $d$ between $0$ and $a+b$ can be produced by repeating the same procedure and accumulating amounts.

The hardest direction is sufficiency. The most fragile point is the claim that the Euclidean algorithm can actually be implemented by physical pourings without violating container capacities.

Solution

Let

$d=\gcd(a,b).$

Initially the $(a+b)$ liter container is full, and the $a$ and $b$ liter containers are empty.

We first prove a necessary condition.

Suppose a pouring operation transfers milk from one container to another. The amount transferred is either the remaining capacity of the destination container or the current amount in the source container. Since every container capacity is divisible by $d$, and initially the amounts are

$0,\quad 0,\quad a+b,$

all of which are divisible by $d$, every transfer changes the quantities by a multiple of $d$.

We prove by induction on the number of pouring operations that after every step, the amount of milk in each container is divisible by $d$.

For the initial state this has already been verified.

Assume it is true before some pouring operation. Let $x$ liters be transferred. The transfer stops only when either the source becomes empty or the destination becomes full. Hence

$$$$

or

$$$$

By the inductive hypothesis, the current amounts are divisible by $d$, and every capacity is divisible by $d$, so $x$ is divisible by $d$. Subtracting $x$ from one container and adding $x$ to another preserves divisibility by $d$.

Thus every attainable quantity is divisible by $d$.

If the milk is divided into two equal parts, then some collection of containers contains exactly

$$$$

liters. Hence $(a+b)/2$ must be divisible by $d$. Therefore

$$$$

We now prove that this condition is sufficient.

Assume

$$$$

Write

$$$$

where $\gcd(a_1,b_1)=1$.

We show that one can isolate exactly $d$ liters. Since $\gcd(a_1,b_1)=1$, the Euclidean algorithm yields integers $u,v$ such that

$$$$

The standard pouring procedure between the $a$ and $b$ containers realizes repeated subtraction:

$$$$

Indeed, if one repeatedly fills one container and pours into the other until the latter becomes full, the remainder after division appears in the first container. Repeating this process reproduces the Euclidean algorithm step by step, eventually producing a container holding exactly $d$ liters.

We justify this explicitly. Assume $a<b$. Fill the $a$ liter container and pour it into the $b$ liter container repeatedly. After $q=\lfloor b/a\rfloor$ transfers, the $b$ liter container contains $qa$ liters, and the next transfer leaves

$$$$

liters of free space. Pouring once more leaves exactly

$$$$

liters in the $a$ liter container. This is precisely the remainder when $(q+1)a$ is divided by $b$. Repeating the same operation replaces the pair $(a,b)$ by $(b,r)$, where $r$ is the remainder upon division of $b$ by $a$. Continuing finitely many times produces the greatest common divisor $d$.

Hence exactly $d$ liters can be isolated.

Since every multiple of $d$ is a sum of several copies of $d$, repeating the same construction allows us to isolate successively

$$$$

Therefore every multiple of $d$ not exceeding $a+b$ can be produced.

Because

$$$$

the target quantity $(a+b)/2$ is such a multiple. Hence we can produce exactly $(a+b)/2$ liters, which divides the milk into two equal parts.

For the concrete case $a=5$, $b=7$, we have

$$$$

so division is possible.

One explicit sequence is the following.

Initially the bucket contains $12$ liters.

Fill the $5$ liter container and pour it into the $7$ liter container. Repeat once more. The second pouring fills the $7$ liter container and leaves $3$ liters in the $5$ liter container.

Empty the $7$ liter container back into the bucket. Pour the $3$ liters into the $7$ liter container. Fill the $5$ liter container from the bucket and pour into the $7$ liter container until it is full. Since the $7$ liter container already contains $3$ liters, only $4$ liters are transferred, leaving exactly $1$ liter in the $5$ liter container.

Empty the $7$ liter container. Pour the $1$ liter into it. Refill the $5$ liter container and pour into the $7$ liter container. The $7$ liter container now contains $6$ liters. The remaining milk in the bucket is also $6$ liters.

Thus the milk has been divided into two equal parts.

Therefore the general problem is solvable exactly for those pairs $(a,b)$ satisfying

$$$$

Equivalently, writing

$$$$

with $m,n$ odd, the condition is

$$$$

Hence

$\boxed{\text{Division is possible exactly when }\gcd(a,b)\mid \frac{a+b}{2}.}$

Verification of Key Steps

The first delicate point is the divisibility invariant. A careless argument might say that every quantity is a linear combination of $a$ and $b$, but this does not immediately imply that every intermediate amount is divisible by $d$. The inductive proof resolves the issue because each transfer amount is itself forced to be divisible by $d$. For example, with capacities $6$ and $10$, every intermediate quantity must remain even. Direct experimentation confirms this: starting from $(0,0,16)$, every reachable state has only even entries.

The second delicate point is the realization of the Euclidean algorithm. One must check that the remainder really appears physically in a container. Take $(a,b)=(5,7)$. Fill the $5$ liter container and pour into the $7$ liter container twice. The second pouring fills the $7$ liter container after receiving only $2$ liters, leaving $3$ liters behind. This is exactly the remainder of $10$ upon division by $7$. Repeating the process with $3$ and $5$ produces $2$, then with $2$ and $3$ produces $1$.

The third delicate point is the equivalence with the parity formulation. Let

$$$$

with $m,n$ odd. Then

$$$$

If $\alpha=\beta$, then

$$$$

contains one fewer factor of $2$ than $d$, because $m+n$ is even but not divisible by $4$. Hence divisibility fails. If $\alpha\ne\beta$, then $(a+b)/2$ retains at least $\min(\alpha,\beta)$ powers of $2$, so divisibility holds.

Alternative Approaches

One may model the process graph-theoretically. Each state is a triple

$$$$

where

$$$$

subject to

$$$$

Edges correspond to legal pourings. The reachable states form exactly the states whose coordinates are multiples of $\gcd(a,b)$. The target state exists precisely when $(a+b)/2$ satisfies the same divisibility condition.

Another approach uses modular arithmetic directly. Measuring operations with containers of capacities $a$ and $b$ produce exactly the subgroup

$$$$

inside $\mathbb Z$, where $d=\gcd(a,b)$. The target amount is attainable exactly when it belongs to this subgroup. This proof is shorter but hides the constructive aspect of the Euclidean algorithm, while the main solution explains explicitly how the required amount is produced.