Maths Olympiad Prep

Library / /5 of 6

Number theory Difficulty 6.3 National olympiad Prove it Brazil

Two thieves stole a container of 88 liters of wine. How can they divide it into two parts of 44 liters each if all they have is a 33 liter container and a 55 liter container? Consider the general case of dividing m+nm+n liters into two equal amounts, given a container of mm liters and a container of nn liters (where mm and nn are positive integers). Show that it is possible iff m+nm+n is even and m+n2\frac{m+n}{2} is divisible by gcd(m,n)\gcd(m, n).

Solution

Call the containers L8L_8, L5L_5, L3L_3. Fill L5L_5 from L8L_8, then fill L3L_3 from L5L_5, leaving 22 in L5L_5. Empty L3L_3 into L8L_8. Empty L5L_5 into L3L_3 (so now L8L_8 has 66, L5L_5 has 00, L3L_3 has 22). Fill L5L_5 from L8L_8. Fill L3L_3 from L5L_5. Empty L3L_3 into L8L_8. Now L5L_5 and L8L_8 each contain 44.

Now consider the general case. It is an easy induction that the amount in each container is always a multiple of gcd(m,n)\gcd(m, n). Use induction on the number of steps, and note that the only possible move is to replace a,ba, b by D,a+bDD, a+b-D, where DD is one of 0,m,n,m+n0, m, n, m+n. So it is certainly a necessary condition that m+n2\frac{m+n}{2} is divisible by gcd(m,n)\gcd(m, n). In particular, it must be an integer and so m+nm+n must be even. So it remains to show that if m+nm+n is even and m+n2\frac{m+n}{2} is a multiple of gcd(m,n)\gcd(m, n) then we can get m+n2\frac{m+n}{2} into LmL_m.
If m=nm = n, then that is trivial. So assume m>nm > n. Put d=mnd = m-n. Now suppose that after some moves we have got kk in the LnL_n and the rest m+nkm+n-k in the Lm+nL_{m+n}. Fill LmL_m from Lm+nL_{m+n}, then fill LnL_n from LmL_m. That gives m(nk)=k+dm-(n-k) = k+d in LmL_m. Now k+d=qn+rk+d = qn+r for some 0r<n0 \le r < n. Repeatedly (for more precisely qq times) fill LnL_n from LmL_m and empty it into Lm+nL_{m+n}, finally pour the remainder of rr from LmL_m into LnL_n. So starting with all the wine in Lm+nL_{m+n} (i.e. k=0k=0), and iterating this process we get [hd][hd] in LnL_n where [hd][hd] denotes the residue of hdhd mod nn.
Now we may put m+n2=Qn+R\frac{m+n}{2} = Qn + R, where 0R<n0 \le R < n. Since nn and m+n2\frac{m+n}{2} are multiples of gcd(m,n)\gcd(m, n), so is RR. But gcd(m,n)=gcd(d,n)\gcd(m, n) = \gcd(d, n). So RR is a multiple of gcd(d,n)\gcd(d, n). But that means we can write R=hdhnR = hd - h'n for some

(1981)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.