I was browsing the December, 1908 issue of The Strand Magazine (it’s related to a hobby of mine), when I came across an article called “The World’s Best Puzzles”, by Henry Dudeney, who seems to have been the Martin Gardner of his day. Here’s a cool puzzle from that article, which according to Dudeney was first recorded by Alcuin, Abbot of Canterbury (735-804). I assume it’s from his manuscript Propositiones ad Acutendos Juvenes (Problems to Sharpen Youths).
The Puzzle #
100 bushes of corn are distributed to 100 people such that every man receives 3 bushels, every woman 2 bushels, and every child 1/2 a bushel. How many men, women, and children are there?
There are seven solutions; Dudeney gives one: 20 men, 0 women, and 80 children. Can you find the other six?
Let’s put the puzzle into algebra, so it’s easier to discuss.
Solve for
This problem (or one very close to it), is known as a system of Diophantine equations.
Here’s a picture to look at while you try to solve it. The answer is below. Don’t peek!
The Solution #
Here’s my solution. I’ll break it into steps. From the problem
statement, we know
1. is even. #
That there is an even number of children is obvious from the fact that the total number of bushels is integral, and that the number of men, women, and children all have to be integral.
2. is a multiple of 5. #
To prove this, we take the two original equations and eliminate
this gives us:
Another way to write the last equation is
Since
3. #
To prove this, let’s eliminate
this results in:
which gives us
Now we apply the fact that
And since we know that
What are the multiples of 5 that are less than or equal to 30?
w = seq(from=0, to=30, by=5)
w
## [1] 0 5 10 15 20 25 30
That’s 7 values—exactly what we’re looking for! So we’re basically done, but we can fill in all the counts just to polish it off. I’ll do that in R, but you can do it in any language, of course.
# from Step 3
m = 20 - (3/5) * w
# from the fact that there are 100 people total
c = 100 - (m + w)
pframe = data.frame(
men = m,
women = w,
children = c,
total_pop = m+w+c,
bushels = 3*m + 2*w + 0.5*c
)
knitr::kable(pframe, caption="Allocations of men, women, and children")
men | women | children | total_pop | bushels |
---|---|---|---|---|
20 | 0 | 80 | 100 | 100 |
17 | 5 | 78 | 100 | 100 |
14 | 10 | 76 | 100 | 100 |
11 | 15 | 74 | 100 | 100 |
8 | 20 | 72 | 100 | 100 |
5 | 25 | 70 | 100 | 100 |
2 | 30 | 68 | 100 | 100 |
Allocations of men, women, and children>
And there you have it: the seven solutions to the “100 bushels of corn” problem.