Dudeney's "Puzzles and Curious Problems": 38: The Picnic

Question

This is presented (slightly abbreviated and paraphrased) as follows:

"Four married couples had $32$ bottles of lemonade between them at a picnic.

Mary had 1 bottle, Anne had 2, Jane had 3 and Elizabeth had 4 bottles.

John MacGregor had the same number of bottles as his wife;

Lloyd Jones drank twice as much as his wife;

William Smith drank three times as much as his wife;

Patrick Dolan drank four times as much as his wife.

The puzzle is to match the ladies to the surnames.

Who was married to whom?"

It boils down to finding the values of $a$, $b$, $c$ and $d$ where: $$a + 2 b + 3 c + 4 d = 22$$

and $\{a, b, c, d\} = \{1, 2, 3, 4\}$

It is straightforward but tedious to work it out by trial and error, which gets you to: $$a = 3, b = 4, c = 1, d = 2$$

thus giving us $3 \times 1 + 4 \times 3 + 1 \times 3 + 2 \times 4 = 3 + 8 + 3 + 8 = 22$, and so:

Mary was Mrs. Smith, Anne was Mrs. Doyle, Jane was Mrs. MacGregor, Elizabeth was Mrs. Jones.

But is there an algebraic / number-theoretical way of solving this?

Something tickling the back of my mind makes me think of Newton-Girard formulas, but I haven't worked out how they can help.

EDIT:

This puzzle is reprised as 51: Sharing the Apples where in this case it is four brother-sister pairs sharing 32 apples between them.

Answer 1

Starting from:

$$a+2b+3c+4d=22$$

we can infer that $a+3c=22-2b-4d$ is even. Hence $a,c$ must be both odd or both even. If both even, then either $a=2$ and $c=4$ or vice versa, but in either case:

$$a+3c\equiv2 \pmod4$$

while, since $b$ will be odd:

$$a+3c=22-2b-4d\equiv0 \pmod4$$

Thus we have a contradiction, so $a,c$ must be both odd and therefore $b,d$ must be both even.

$d$ cannot be $4$ since any assignment of $(1,2,3)$ to $(a,b,c)$ yields:

$$a+2b+3c>22-(4\times4)=6$$

So we must have $d=2$ and $b=4$ implying:

$$a+3c=22-(2\times4)-(4\times2)=6$$

from which it is readily seen that $a=3$ and $c=1$.

Answer 2

Let us consider linear diophantian equation:

$$a + 2 b + 3 c + 4 d = 22 \tag{1}$$

and its "homogeneous" version:

$$a + 2 b + 3 c + 4 d = 0 \tag{2}$$

The general solution to (1) can be given (among others) by the following parametric representation:

$$\underbrace{\begin{pmatrix}a\\b\\c\\d\end{pmatrix}}_{PS (1)}=\begin{pmatrix}0\\0\\2\\4\end{pmatrix}+\underbrace{\alpha \begin{pmatrix}2\\-1\\0\\0\end{pmatrix}+\beta \begin{pmatrix}3\\0\\-1\\0\end{pmatrix}+\gamma\begin{pmatrix}4\\0\\0\\-1\end{pmatrix}}_{GS (2)}\tag{3}$$

(where parameters $\alpha, \beta, \gamma$ can take any values in $\mathbb{Z}$)

(3) is - classically - the sum of a particular solution of (1) (represented by the first vector) and a general solution of (2), the latter being a linear combination of $3$ particular solutions of (2). Why this number $3$ ? Because it is one less than the number of unknowns $a,b,c,d$ (see this reference).

Now, one can make a systematic search by attempting to solve (3) (i.e., find integer solution $\alpha, \beta,\gamma$ with the $4!=24$ cases: $$\begin{pmatrix}a\\b\\c\\d\end{pmatrix}=\begin{pmatrix}1\\2\\3\\4\end{pmatrix} \ \ \text{or} \ \ \begin{pmatrix}1\\2\\4\\3\end{pmatrix}, \ \ \text{etc.} \ \ $$

Surprisingly, it looks that the solution you have found is the single solution:

$$\begin{pmatrix}a\\b\\c\\d\end{pmatrix}=\begin{pmatrix}3\\4\\1\\2\end{pmatrix} \ \ \text{for} \ \ \alpha=-4, \ \ \beta=1, \ \ \gamma=2.\tag{4}$$