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]

Advertisements

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

    If the declared order had been different we could have had
    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))
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: