Enigmatic Code

Programming Enigma Puzzles

Enigma 248: Add or multiply

From New Scientist #1395, 2nd February 1984 [link]

I gave each of the five boys a different amount of money, and said to each:

“Spend all this on goodies at the corner shop. Each goodie you buy must cost a different exact number of half-pennies. When you multiply together the prices (in pence) of all your purchases, the result must be the same as if you added them.”

When they came back, they had all done as I asked: each had bought the same number of goodies; and in one case each of the prices was an exact whole number of pence.

How much did my generosity cost me altogether?

[enigma248]

Advertisements

3 responses to “Enigma 248: Add or multiply

  1. Jim Randell 5 January 2015 at 8:19 am

    I tried to write a program that makes as few assumptions as possible about the problem, as too much analysis can leave little for the program to do. The first program I wrote required an arbitrary limit on the maximum amount that an individual goodie can cost. I don’t like arbitrary limits, so I wrote this program, which considers increasing values of goodies until it finds a solution. I’m not entirely happy with this approach either, because as it constructs larger sets of goodies to try it is repeating the testing of the smaller sets. But it finds a solution in 69ms, so I’m not going to worry about it for now. Also it stops looking when it finds the first solution (but as we shall see there is only a single solution).

    from itertools import count, combinations
    from collections import defaultdict
    from enigma import irange, multiply, diff, first, uniq, printf
    
    # goodie prices in wholes and halfs
    def generate(wp, hp):
    
      # consider possible numbers of goodies
      for n in irange(2, min(len(wp), len(hp))):
    
        # find sets of whole numbers, record by sum
        ws = defaultdict(list)
        for gs in combinations(wp, n):
          p = multiply(gs)
          s = sum(gs)
          if p == s:
            ws[s].append(gs)
        if not ws: continue
    
        # and sets of half numbers
        hs = defaultdict(list)
        k = 2 ** (n - 1)
        for gs in combinations(hp, n):
          p = multiply(gs)
          s = sum(gs)
          if p == s * k:
            hs[s].append(gs)
    
        # choose an amount for the whole number
        for w in ws.keys():
          # and choose 4 different half number amounts
          for h in combinations(diff(hs.keys(), [2 * w]), 4):
            yield (n, w, h)
    
    
    # find the first solution
    def solve():
      # consider increasing value of goodies (in half pennies)
      for m in count(1):
        wp = tuple(irange(1, m // 2))
        hp = tuple(irange(1, m))
        for (n, w, hs) in generate(wp, hp):
          # calculate the total sum
          (t, r) = divmod(2 * w + sum(hs), 2)
          printf("total={t}{r}p [n={n} whole={w} halfs={hs}]", r=(' 1/2' if r == 1 else ''))
          return
    
    solve()
    

    Solution: The total amount of money give to the boys is 48p.

    Each boy bought 3 goodies.

    One boy received 6p, and bought goodies costing 1p, 2p and 3p.

    One boy received 7½p, and bought goodies costing 1p, 1½p and 5p.

    One boy received 9p, and bought goodies costing ½p, 4p and 4½p.

    One boy received 10½p, and bought goodies costing ½p, 3p and 7p.

    One boy received 15p, and bought goodies costing ½p, 2½ p, 12p.

  2. Jim Randell 5 January 2015 at 8:33 am

    Analytically it is fairly straightforward to show that the only sets of distinct positive integers where the product is the same as the sum are singleton sets, or {1, 2, 3}.

    So this tells us straight away that each boy bought 3 goodies, and that one of the boys spent 6p on goodies costing 1p, 2p and 3p.

    So we consider the values of the equation:

    4(a + b + c) = abc, 0 < a < b < c

    where a, b, c represent the prices of the three goodies in whole numbers of half pennies.

    For a given a and b we have:

    c = 4(a + b) / (ab – 4)

    For a fixed value of a, we can consider the curves:

    4(a + x + y) = axy, x = y

    These cross at:

    x = 2(2 + √(a² + 4))/a

    this gives us an upper bound for values of b, and we already have a < b as a lower bound for b.

    For a = 1, we get:

    1 < b < 2(2 + √5) ≈ 8.47.

    which gives us the following solutions: (b, c) = (5, 24), (6, 14), (8, 9).

    For a = 2, we get:

    2 < b < (2 + 2√2) ≈ 4.83.

    which gives us the following solutions: (b, c) = (3, 10), (4, 6).

    For a = 3, we get:

    3 < b < 2(2 + √13)/3 ≈ 3.74.

    These solutions correspond to the five amounts given to the boys (in half-pennies), and each sums to a different total:

    (1, 5, 24) = ½p + 2½p + 12p = 15p
    (1, 6, 14) = ½p + 3p + 7p = 10½p
    (1, 8, 9) = ½p + 4p + 4½p = 9p
    (2, 3, 10) = 1p + 1½p + 5p = 7½p
    (2, 4, 6) = 1p + 2p + 3p = 6p

    and exactly one of them is a set of whole pennies, as required.

    Hence the total amount given to the boys is 15p + 10½p + 9p + 7½p + 6p = 48p.

  3. Hakan Kjellerstrand 6 January 2015 at 1:21 pm

    MiniZinc (Constraint Programming) approach: http://hakank.org/minizinc/enigma_248_add_or_multiply.mzn

    The number of goodies per boy (3) and some appropriate upper limit for the price was found by experimentation.

    It shows the unique solution as the above comments.

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: