# Enigmatic Code

Programming Enigma Puzzles

## Enigma 378: A sleeper awakes

From New Scientist #1527, 25th September 1986 [link]

I fell asleep during a lecture and dreamed that I was out in the country. In my dream I saw a field and in this field some four-legged cows being milked by at least one two-legged milkmaid who had the use of a number of three-legged stools. There were more stools than would suffice for one per milkmaid, and more cows than would suffice for one per milking stool.

Given this information, and the number of legs in the collection, I realised that one could work out unambiguously the number of cows, stools and milkmaids in the field. Furthermore, the number of legs in the field was the largest it could have been, consistent with these facts.

I awoke with quite a start when the lecturer addressed a question to me. Unfortunately, the answer I gave to his question was the number of cows, milking stools and milkmaids that I had dreamed of. Of course, everyone laughed, but I bet they wouldn’t be able to solve that in their sleep!

How many milkmaids were there in my dream, and how many milking stools and cows?

[enigma378]

### 3 responses to “Enigma 378: A sleeper awakes”

1. Jim Randell 6 January 2017 at 6:59 am

This Python program runs in 54ms.

```from itertools import count
from enigma import irange, first, printf

# C > S > M > 0
#
# the number of legs is given by:
#
# L(C, S, M) = 4C + 3S + 2M
#
# if the number of legs, n, can be made in multiple ways then by
# adding 1 to C we can make n + 4 in multiple ways.
#
# so once we have 4 consecutive values for n that can be expressed in
# multiple ways, all higher values will also be expressible in
# multiple ways

# generate (C, S, M) values for L
def values(L):
for C in irange(L // 4, 3, step=-1):
for S in irange((L - 4 * C) // 3, 2, step=-1):
(M, r) = divmod(L - 4 * C - 3 * S, 2)
if r == 0 and C > S > M > 0:
yield (C, S, M)

# record the number of ways each value can be expressed
single = None
multiple = list()
# consider increasing values for L
# the lowest value is L(3, 2, 1) = 20
for L in count(20):
vs = list(values(L))
n = len(vs)
printf("L={L}: {n} {vs}")
if n == 1:
single = L
elif n > 1:
multiple.append(L)
# have we seen 4 consecutive multiple values?
if len(multiple) > 3 and multiple[-4] + 3 == L:
break

# output the solution
printf("L={single} (C, S, M)={v}", v=first(values(single))[0])
```

Solution: There was 1 milkmaid, 3 stools and 7 cows.

So, the largest unique value for the number of legs is 39.

2. Hugh Casement 6 January 2017 at 9:40 am

1 cow, 2 stools, 7 maids (24 legs)
2 stools, 3 cows, 6 maids (30 legs)
1 cow, 4 maids, 7 stools (33 legs)
1 maid, 4 cows, 7 stools (39 legs again)
2 stools, 4 maids, 7 cows (42 legs).
I admit that those don’t make very good farming practice.
Such is the stuff as dreams are made on.

3. Brian Gladman 6 January 2017 at 6:14 pm

This is a variation on a problem known as the Frobenius problem (see here), for which I have a solver in my Number Theory Library.

```from itertools import count
from number_theory import frobenius_solve

# We are looking for integer solutions of the equation
#
#    l = 2 * m + 3 * s + 4 * c
#
# where l, m, s and c are the numbers of legs, milkmaids,
# stools and cows respectively (with 0 < m < s < c). This
# is a variation on the Frobenius number problem in which
# we want the largest unique solution. Once there is more
# than one solution for four consecutive numbers of legs,
# a multiple solution for any higher number of legs is
# given by adding an appropriate number of cows to one of
# these.

multiple, solution = 0, 0
# consider increasing total numbers of legs
for l in count(12):
# find Frobenius solutions for this number of legs
# with 0 < m < s < c
sols = []
for m, s, c in frobenius_solve((2, 3, 4), l):
if 0 < m < s < c:
sols.append((m, s, c, l))
# count consecutive multiple solutions
multiple = 0 if len(sols) < 2 else multiple + 1
# save unique solutions
if sols and not multiple:
solution = sols[0]
if multiple == 4:
break
m, s, c, l = solution
ss = '' if m == 1 else 's'
fs = '{} milkmaid{}, {} stools and {} cows (with {} legs).'
print(fs.format(m, ss, s, c, l))
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.