Enigmatic Code

Programming Enigma Puzzles

Enigma 1147: Multiply and add

From New Scientist #2303, 11th August 2001 [link]

Matthew is practising his multiplication and addition. He had a board (as below) and nine cards labelled 1,2,3,…,8,9.

Enigma 1147

He shuffles the cards and deals them on to the board, one to each square. For each square, he multiplies the number on the board by the number on the card in that square. Finally he adds together the nine products he has obtained to give his final number.

When I watched Matthew play the game his final number was 545. When he had finished he then moved some of the cards. Each card he moved went one square horizontally or vertically, but not diagonally, to another square on the board. I can’t remember all the cards he moved, but I do know he moved the cards in the four corner squares. He then had a new layout with one card in each square and he repeated his multiply and add routine. When he told me his final number, I asked him how many factors it had. After a while he told me he had found 20 but had still not finished his search.

What was Matthew’s final number after he had moved the cards?

[enigma1147]

Advertisements

One response to “Enigma 1147: Multiply and add

  1. Jim Randell 3 October 2016 at 7:28 am

    The first program I wrote looked at all possible arrangements of the cards, and picked out those with a value of 545, and those with a value with more than 20 divisors, and then tried to match the two so the second was an appropriate rearrangement of the first. This does produce the solution to the puzzle, but not particularly quickly (it runs in just under 1 second (999ms to be exact)).

    My second approach was to use a bit of analysis to find out the possible rearrangements. It turns out there are only four allowable rearrangements. It also turns out there are only three arrangements of cards that give a total sum of 545. So we can apply each of the four rearrangements to these three initial arrangements of cards to give 12 candidate final arrangements. Only one of them has a total sum with more than 20 divisors.

    This Python 3 program uses a recursive routine to find the possible arrangement of cards that give a sum of 545, and then applies the 4 rearrangements to each arrangement it finds, and works out the final sum. It runs in 82ms (and the code is slightly shorter than my original program too).

    # in the arrangement:
    #
    # 0 1 2
    # 3 4 5
    # 6 7 8
    #
    #
    # if the four corner pieces (0, 2, 6, 8) are moved to an adjacent
    # square they must move to the edge positions (1, 3, 5, 7), if the
    # central piece (4) moves it must also move to an edge position, but
    # they are already occupied by all the pieces that were originally in
    # the corners, which means the central piece is not moved. so the
    # corners pieces move to the edge positions, and the edge pieces move
    # to the corner positions.
    #
    # so there are only 4 possible rearrangements where pieces move to
    # adjacent positions:
    #
    # 1 0 5    3 0 1    1 2 5    3 2 1
    # 6 4 2    6 4 2    0 4 8    0 4 8
    # 3 8 7    7 8 5    3 6 7    7 6 5
    
    from enigma import irange, tau, printf
    
    # possible rearrangements
    rs = (
      (1, 0, 5, 6, 4, 2, 3, 8, 7),
      (3, 0, 1, 6, 4, 2, 7, 8, 5),
      (1, 2, 5, 0, 4, 8, 3, 6, 7),
      (3, 2, 1, 0, 4, 8, 7, 6, 5),
    )
    
    # numbers on the card (we rotate the card through 180 degrees so we
    # deal with the larger numbers first)
    numbers = (39, 32, 26, 22, 17, 12, 9, 5, 1)
    
    # generate arrangements to a certain sum
    # ns - remaining numbers on the card
    # vs - remaining values to assign
    # t - remaining sum
    # s - values assigned so far
    def cards(ns, vs, t, s=[]):
      # are we done?
      if not ns:
        if t == 0:
          yield s
      else:
        # allocate the next value
        n = ns[0]
        for (i, v) in enumerate(vs):
          x = t - n * v
          if not(x < 0):
            yield from cards(ns[1:], vs[:i] + vs[i + 1:], x, s + [v])
    
    # find arrangements that sum 545
    for s in cards(numbers, list(irange(9, 1, step=-1)), 545):
      # consider possible rearrangements
      for r in rs:
        # determine the sum of rearranged grid
        t = sum(n * s[r[i]] for (i, n) in enumerate(numbers))
        # look for sums with more than 20 divisors
        if tau(t) > 20:
          printf("{s} * {r}, t={t}, {d} divisors", d=tau(t))
    

    Solution: Matthew’s final number is 630.

    Here are the initial and final arrangements:

    enigma-1147-solution

    The positions of the coloured pairs are swapped between the initial and final arrangements.

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: