100 Bushels of Corn

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 , , and .

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 , , and are all nonnegative integers.

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 , by multiplying the first equation by and adding the two together.

this gives us:

Another way to write the last equation is

Since is even, is divisible by 5, and 200 is divisible by 5; therefore, is divisible by 5. QED

3.

To prove this, let’s eliminate .

this results in:

which gives us

Now we apply the fact that :

And since we know that must be a multiple of 5, this gives us . QED

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")

And there you have it: the seven solutions to the “100 bushels of corn” problem.