Enigmatic Code

Programming Enigma Puzzles

Tantalizer 400: Loaves and fishes

From New Scientist #950, 22nd May 1975 [link]

A Trappist fête has its drawbacks and its triumphs too. You will see what I mean from an incident at one I attended last week. There was a sea-food stall, selling small items on sticks, where you could buy (in ascending order of price) a whelk, a mussel, a fishcake, a slice of eel and an oyster. While I watched, a party of five monks approached and gave a sign meaning that each of them wanted a different item. (I hasten to add that this was the only untoward sign they made throughout).

Each then placed the same amount of money of the counter. The stall-holder reflected a moment, and then handed each monk the exact item he had wanted. A total of 50 pence then passed across the counter, followed by the return of a total of 16 pence in change. No “tanners” (2½p pieces) were involved.

Assuming that everyone used his loaf and not any extraneous knowledge, what was the price of a fishcake?

[tantalizer400]

One response to “Tantalizer 400: Loaves and fishes

  1. Jim Randell 3 June 2020 at 9:14 am

    Initially I didn’t understand this puzzle. But was able to make sense of it like this:

    Each monk puts down 10p (using some denomination of coins). The denominations in circulation at the time were: ½p, 1p, 2p, 5p, 10p.

    If a customer were to pay with 20× ½p coins, they must be paying for a 10p item (as any smaller amount would not require tendering all the coins).

    If they paid with 10× 1p coins, they could be paying for a 10p item, or a 9½p item.

    If they paid with 5× 2p coins, they could be paying for an item costing any of: 8½p, 9p, 9½p, 10p.

    And so on.

    So if we assume the monks all tender 10p out of necessity, rather than for artistic purposes, we can limit the possible items that each monk could be paying for, if we know the actual coins tendered.

    In the described scenario the stall-holder is able to work out, from the amounts tendered, and only knowing that each monk wants a different item, who wants what (and, of course, he knows the prices of the items).

    The following Python 3 program works in half-pennies. It looks for possible ways to tender 10p, and for what prices there is no lower amount that could be tendered using the same coins. It then examines possible sets of 5 prices (that would require 16p of change to be given), that have a situation where the stall-holder would be able to work out what each monk wants. It runs in 305ms.

    Run: [ @repl.it ]

    from enigma import irange, express, multiset, subsets, peek, printf
    
    # denominations (in half-pence units)
    ds = [ 1, 2, 4, 10, 20 ]
    
    # possible amounts (in half-pence units)
    amounts = set(irange(1, 20))
    
    # consider possible ways to make 10p (= 20 half pences)
    ts = list()
    for s in express(20, ds):
      s = multiset.from_pairs(zip(ds, s))
      # identify amounts that this could be tendered for
      vs = set(x for x in amounts if x > 20 - min(s.keys()))
      ts.append((s, vs))
    
    # can we deduce what everyone wants with this set of values?
    def solve(vs, ss=[]):
      # are we done?
      if not vs:
        yield ss
      else:
        # look for amounts that correspond to a unique value in vs
        for (s, xs) in ts:
          us = xs.intersection(vs)
          if len(us) == 1:
            # solve for the remaining values
            yield from solve(vs.difference(us), ss + [(s, peek(us))])
    
    # choose a set of 5 amounts ...
    for vs in subsets(amounts, size=5):
      # ... that require 32 half pence change from 100 half pence tendered
      if sum(vs) != 68: continue
      # can we deduce what everyone wants?
      for ss in solve(set(vs)):
        printf("{vs} -> {ss}")
        break # we only need one validation
    

    Solution: The price of a fishcake is 8½p.

    There is only one possible set of prices that leads to this situation:

    Whelk = ½p
    Mussel = 5½p
    Fishcake = 8½p
    Eel = 9½p
    Oyster = 10p

    The monks tendered 10p each, there are many ways this could be done, but here is one way:

    Monk 1: 20× ½p
    Monk 2: 10× 1p
    Monk 3: 5× 2p
    Monk 4: 2× 5p
    Monk 5: 1× 10p

    Monk 1 could have tendered: ½p (if he had wanted a whelk), 5½p (if he had wanted a mussel), 9p (if he had wanted a fishcake), 9½p (if he had wanted an eel), so he can only want an oyster. He is served and receives no change.

    Monk 2 could have tendered: 1p (if he had wanted a whelk), 6p (if he had wanted a mussel), 9p (if he had wanted a fishcake), and he can’t want an oyster, as each monk wants a different item. So he can only want an eel. He is served and receives ½p change.

    Monk 3 could have tendered: 2p (if he wanted a whelk), 6p (if he wanted a mussel), so he can only want a fishcake. He is served and receives 1½p change.

    Monk 4 could have tendered 5p (if he wanted a whelk), so he can only want a mussel. He is served and receives 4½p change.

    Monk 5 can only want a whelk. He is served and receives 9½p change.

    So everyone has received a different item, 50p was tendered, and 16p of change was returned.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: