Enigmatic Code

Programming Enigma Puzzles

Enigma 65: Plus and minus

From New Scientist #1208, 3rd July 1980 [link]

The problem is simply to arrange as many integers as possible in a row so that the sum of any eight successive integers is positive (but as small as possible), while any 11 successive integers is negative (but as near zero as possible).

[enigma65]

5 responses to “Enigma 65: Plus and minus

  1. Jim Randell 1 March 2013 at 9:53 am

    I didn’t solve this one purely programatically, as the problem space initially seems too large to explore in a reasonable amount of time. A bit of analysis shows what the “best” solution might be, this can then be attacked manually to yield the solution, or using the SymPy symbolic maths package. This Python program uses SymPy and runs in 394ms.

    # consider a sequence of length 18: s0 ... s17
    #
    # and arrange the numbers like this:
    #
    #    s0  s1  s2  s3  s4  s5  s6  s7  ->  p0
    #    s1  s2  s3  s4  s5  s6  s7  s8  ->  p1
    #    s2  s3  s4  s5  s6  s7  s8  s9  ->  p2
    #    s3  s4  s5  s6  s7  s8  s9 s10  ->  p3
    #    s4  s5  s6  s7  s8  s9 s10 s11  ->  p4
    #    s5  s6  s7  s8  s9 s10 s11 s12  ->  p5
    #    s6  s7  s8  s9 s10 s11 s12 s13  ->  p6
    #    s7  s8  s9 s10 s11 s12 s13 s14  ->  p7
    #    s8  s9 s10 s11 s12 s13 s14 s15  ->  p8
    #    s9 s10 s11 s12 s13 s14 s15 s16  ->  p9
    #   s10 s11 s12 s13 s14 s15 s16 s17  ->  p10
    #
    #    |   |   |   |   |   |   |   |
    #    v   v   v   v   v   v   v   v
    #
    #    n0  n1  n2  n3  n4  n5  n6  n7
    #
    # the rows are consecutive subsequences of length 8,
    # and so sum to positive integers (p0 ... p10)
    # and the columns are consecutive subsequences of length 11
    # and so sum to negative integers (n0 ... n7)
    #
    # but the p0 + ... + p10 is a positive integer and is
    # the sum of all entries in the grid, but n0 + ... + n7
    # is also the sum of all entries in the grid, but is
    # a negative integer
    #
    # this contradiction shows that a sequence of length 18
    # is not possible
    #
    # but consider a sequence of length 17, there are 10
    # consecutive subsequences of length 8, and there are
    # 7 consecutive subsequences of length 11
    #
    # if we try to achieve sums as near to zero as possible
    # for each of these subsequences (i.e. the subsequences
    # of length 8 sum to 1 and the subsequences of length 11
    # sum to -1) we have 17 equations in 17 variables, which
    # can be solved by hand... or by SymPy:
    
    from sympy import symbols, Eq, solve
    from enigma import irange
    
    s = list(symbols('s' + str(i), integer=True) for i in irange(0, 16))
    
    # subsequences of length 8
    s8s = list(Eq(sum(s[i:i + 8]), 1) for i in irange(0, len(s) - 8))
    
    # subsequences of length 11
    s11s = list(Eq(sum(s[i:i + 11]), -1) for i in irange(0, len(s) - 11))
    
    # solve the system of equations
    r = solve(s8s + s11s)
    # output the sequence
    if r: print(list(r[x] for x in s))
    

    Solution: The best sequence is: –7, 12, –7, –7, 12, –7, –7, 12, –7, 12, –7, –7, 12, –7, –7, 12, –7.

  2. Brian Gladman 1 March 2013 at 3:52 pm

    Nicely done, Jim — it looks daunting at first. Your rectangular grid was an inspiration!

    • Jim Randell 2 March 2013 at 2:25 pm

      Yes. I was quite pleased with that solution (although it’s not really a programmatic one), before I hit on the grid idea I wasn’t really getting anywhere.

      Although when you see the solution it looks like you should be able to extend it further (unless you look really closely), but the next term would need to be ≥12 to make a subsequence of length 8 with a positive sum, and also ≤–7 to make a subsequence of length 11 with a negative sum, so it really is not possible to extend it further.

      • Brian Gladman 2 March 2013 at 11:33 pm

        So a sequence containing sequential sub-sequences of length P with minimum positive sums and sequential sub-sequences of length N with minimum negative sums has a maximum length of P + N – 2?

        • Jim Randell 3 March 2013 at 12:16 pm

          The grid argument can be generalised to show that a sequence of length P + N – 1 is never possible. So the maximal possible length of sequence is indeed P + N – 2, but it’s not always possible to solve the set of equations where pi = 1 and ni = –1 (although that doesn’t necessarily preclude other solutions of length P + N – 2).

          I modified my program to take P and N as command line parameters and you can generate solutions like this:

          % python enigma65c.py 8 13
          [8, -13, 8, 8, -13, 8, -13, 8, 8, -13, 8, 8, -13, 8, -13, 8, 8, -13, 8]
          % python enigma65c.py 24 5
          [-6, -6, -6, 23, -6, -6, -6, -6, 23, -6, -6, -6, -6, 23, -6, -6, -6, -6, 23, -6, -6, -6, -6, 23, -6, -6, -6]
          

          but not all P, N give solutions (e.g. P=8, N=12).

          I suspect my program is only finding solutions when P and N are co-prime.

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: