Find the number of drinking people (problem from 1544)

Question

Reading about GCD and LCM I came around this problem (apparently dated from around 16th century):

A group of 20 person which are men, women and children drink in a tavern. Together they spend 18 Thaler. The men drin for 3 Thaler a person, the women for 2 Thaler, and the children for half a Thaler. How many men, women and children were in the drinking party?

My approach:
If $x=men$, $y = women$ and $z = children$ then we have the following equations:

$x + y + z = 20$
$3x + 2y + \frac{1}{2}z = 18 \equiv 6x + 4y + z = 36$

So we have $2$ Diophantine equations that I guess an approach to solve the problem is to do some trial and error on a table of values till we reach a combination that satisfies both constraints. But I didn't want to do that approach so I did the following:

$x + y + z = 20 \equiv z = 20 -x - y$
So:
$6x + 4y + z = 6x + 4z + 20 -x - y = 36 \equiv 5x + 3y = 16$

We ended up with the Diophantine equation $5x + 3y = 16$ The solutions to this equations are of the form:
$x = -16 + 3\cdot n$ and $y = 32 - 5\cdot n$

Since the values can only be positive the only acceptable solution is when $n = 6$ where we end up with $(x,y) = (2,2)$

Plugging back to the equation for $z$ we have: $z = 20 - x - y = 20 - 2 - 2 = 16$

So the solution is: $(x, y, z) = (2, 2, 16)$ for $2$ men, $2$ women and $16$ children.
This satisfies both equations since:
$2 + 2 + 16 = 20$ and $12 + 8 + 16 = 36$

Now when I was looking online for solutions I found an article mentioning the triple $(1, 5, 14)$

This problem is of the following form, the specific example given here being derived from Adam Riese (1544):

A group of 20 persons, men, women and virgins, drink in a tavern, together they spend 18 Thaler. The men drink for 3 Thaler a person, the women for 2 Thaler and the virgins for half a Thaler. How many men, women and virgins were in the drinking party?

In modern terms, this type of problem leads to two linear equations to be solved in integers, but involving three unknowns.8 The problem, if fractional and negative solutions are excluded, can have a finite number of solutions, an infinite number of solutions, or no solutions. After deriving equations in one parameter (say t) from the problem (either in words or in symbolic form), most books describe a trial-and-error process. Setting t to 1, 2, 3, etc. and checking whether the sum of the unknowns becomes equal to a number n (in the example 20) leads in a limited number of steps to a solution. In the example given above, the triple $(1, 5, 14)$ satisfying the problem is found.

Now I am confused. Did I misunderstand something? The triple mentioned in the article does not satisfy both constraints and actually my approach to find the Diophantine solutions can not find it.

Can someone help me understand this?

Also is my approach efficient? Is there a "smarter" way to tackle with problems such as this?

Answer 1

I thought that your approach was fine. However, I would have taken an alternative (somewhat informal) approach. Since the problem has been posed, it is reasonable to suspect, without knowing for sure, that the solution is unique.

With that rattling around in my head, the first thing that I do is to pretend that all 20 people are children. This leads to an expenditure of $(10)$.

This expenditure must increased by $(8)$ to $(18)$.
Each conversion of a child to a man increases the expenditure by $(2.5)$. Each conversion of a child to a woman increases the expenditure by $(1.5)$. Clearly, the number of children converted must be an even number.

The candidate solution of converting two children to men and an additional two children to women immediately presents itself.

I used the phrase candidate solution to emphasize that at this point in my analysis, while the candidate solution works mathematically, I have not yet concluded that the solution is unique.

I know that converting more than two children to men would make the expenditure greater than $(18)$. Suppose that instead of converting two children to men and two children to women, I convert four children to women. This takes the expenditure to $(16)$. At this point, there is no way to increase the expenditure from $(16)$ to $(18)$.

Therefore, the candidate solution is in fact unique.

Answer 2

Your method for tackling this particular problem is good, and I don't think there's much more you could have done to improve it. There is, however, a generalisation of it that can be used to solve any set of linear Diophantine equations. Such a general set of linear Diophantine equations can be written in the form $$ b=Ax\ , $$ where $\ b\ $ is an $\ m\times1\ $ column vector with integer entries, $\ A\ $ an $\ m\times n\ $ matrix with integer entries, and $\ x\ $ an $\ n\times1\ $ column vector of unknown quantities whose integer values have to be determined. One general method for solving such a problem is to perform a restricted set of row and column operations on the matrix $\ A\ $ to find an $\ m\times m\ $ totally unimodular matrix $\ U\ $ and an $\ n\times n\ $ totally unimodular matrix $\ V\ $ such that $$ UAV=S_A=\begin{bmatrix} d_1&0&0&\dots&0&\dots&0&0&\dots&0\\ 0&d_2&0&\dots&0&\dots&0&0&\dots&0\\ 0&0&d_3&\dots&0&\dots&0&0&\dots&0\\ \vdots&\vdots&0&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ \vdots&\vdots&\vdots&\vdots&d_i&\vdots&\vdots&\vdots&\vdots&\vdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\ 0&0&0&\dots\dots&0\dots&\dots&d_m&0&\dots&0 \end{bmatrix}\ , $$ the so-called Smith normal form of $\ A\ $, in which $\ d_1,d_2,\dots,d_m\ $ are all integers, and $\ d_{i+1}\ $ is an integer multiple of $\ d_i\ $ for all $\ i\ $. The crucial property of totally unimodular matrices is that they have inverses with integer entries, so if we multiply both sides of the set of linear Diophantine equations above by $\ U\ $, we get \begin{align} c&=Ub=UAVV^{-1}x\\ &=A_Sy\ , \end{align} where $\ c=Ub\ $ has integer entries, and $\ y=V^{-1}x\ $ has integer entries if and only if $\ x\ $ does. This equation has solutions for a $\ y\ $ with integer entries if and only if $\ c_i\ $ is an integer multiple of $\ d_i\ $ for all $\ i\ $, and if this is the case, the general solution for $\ y\ $ is $$ y_i=\cases{\displaystyle\frac{c_i}{d_i}&if $\ i\le m\ $ and $\ d_i\ne0\ $\\ \text{arbitrary integer}&if $\ i>m\ $ or $\ d_i=0\ $.} $$ The general solution for $\ x\ $ is then given by $$ x=Vy\ . $$ For your problem, with only two equations in three unknowns, using the above method would be overkill, and you're better off solving it in exactly the way you did. However, by way of illustration, the matrix $\ A\ $ for your problem is $$ A=\begin{bmatrix} 1&1&1\\ 6&4&1 \end{bmatrix}\ , $$ the column vector $\ b\ $ is $$ b=\begin{bmatrix} 20\\ 36 \end{bmatrix}\ , $$ the Smith normal form of $\ A\ $ is $$ S_A=\begin{bmatrix} 1&0&0\\ 0&1&0 \end{bmatrix}\ , $$ and two totally unimodular matrices (they are not unique) that will reduce $\ A\ $ to this form are \begin{align} U&=\begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}\\ V&=\begin{bmatrix} 1&-1&3\\ -2&2&-5\\ 2&-1&2 \end{bmatrix}\ . \end{align} The general solution of $$ S_Ay=Ub=b $$ is \begin{align} y_1&=20\\ y_2&=36\\ y_3&=\text{arbitrary integer}\ , \end{align} and multiplying this by $\ V\ $ gives the general solution for $\ x,y,z\ $: $$ \begin{bmatrix} x\\y\\z \end{bmatrix}=\begin{bmatrix} 1&-1&3\\ -2&2&-5\\ 2&-1&2 \end{bmatrix}\begin{bmatrix} 20\\36\\y_3 \end{bmatrix}=\begin{bmatrix} 3y_3-16\\32-5y_3\\2y_3+4 \end{bmatrix}\ . $$ But because you want all of $\ x,y,z\ $ to be non negative you have to choose $\ y_3\ $ to satisfy \begin{align} y_3&\ge\Big\lceil\frac{16}{3}\Big\rceil=6\\ y_3&\le\Big\lfloor\frac{32}{5}\Big\rfloor=6\\ y_3&\ge-2\ , \end{align} giving $\ y_3=6\ $, $\ x=2, y=2, z=16\ $ as the only non-negative integer solution for $\ x,y,\ $ and $\ z\ $, just as you've already found.