Enigmatic Code

Programming Enigma Puzzles

Enigma 43: Scalenian squares

From New Scientist #1185, 13th December 1979 [link]

Scalenia is a country bounded by three straight frontiers – called A, B and C, of course – each of a different length but each an exact number of kilometres long. The curious thing is that the length of  A+B+C, and the lengths of A+B−C, A+C−B and B+C−A are all precisely square numbers of kilometres.

If Scalenia has the smallest perimeter consistent with this curious fact, what is the length of each of its frontiers?

[enigma43]

Advertisements

2 responses to “Enigma 43: Scalenian squares

  1. jimrandell 29 January 2012 at 9:59 pm

    The following Python program runs in 36ms.

    # consider:
    #  A + B - C = p^2
    #  A - B + C = q^2
    # -A + B + C = r^2
    #
    # then the perimeter is:
    #
    #  A + B + C = p^2 + q^2 + r^2 = n^2
    #
    # so we can minimise n.
    #
    # let's assume p < q < r, and hence, A < B < C.
    
    from itertools import count
    from enigma import irange, is_square, printf
    
    def solve():
      for s in count(1):
        for p in irange(1, s):
          p2 = p * p
          for q in irange(p, (s - p) // 2):
            q2 = q * q
            r = s - (p + q)
            r2 = r * r
            n2 = p2 + q2 + r2
            if not is_square(n2): continue
    
            t = (p2 + q2, p2 + r2, q2 + r2)
            if len(set(t)) != 3: continue
            if any(x % 2 for x in t): continue
            (A, B, C) = (x // 2 for x in t)
    
            yield (A, B, C)
    
    for (A, B, C) in solve():
      printf("A={A} B={B} C={C} A+B+C={s} A+B-C={sc} A+C-B={sb} B+C-A={sa}", s=A+B+C, sc=A+B-C, sb=A+C-B, sa=B+C-A)
      break
    

    Solution: The frontiers are 26km, 80km and 90km in length.

  2. geoffrounce 18 September 2016 at 11:14 am
    % A solution in MiniZinc
    include "globals.mzn";
    
    % three straight frontiers are called A, B and C
    var 1..1000: A; 
    var 1..1000: B; 
    var 1..1000: C;  
    var 3..3000: perim;
    
    predicate is_square(var int: c) =
       let { var 0..ceil(pow(int2float(ub(c)),(1/2.0))): z } in z * z = c ;
    
    constraint all_different([A,B,C])
    /\ A + B - C > 0 /\ A + C - B > 0 /\ B + C - A > 0;
    
    constraint is_square (A + B + C) /\ is_square (A + B - C) 
    /\ is_square (A + C - B) /\ is_square (B + C - A);
    
    constraint perim = A + B + C;
    
    solve minimize(perim);
    
    output["Frontiers lengths are ",show(A),", ",show(B)," and ",show(C)," km"];
    
    % Frontiers lengths are 90, 80 and 26 km
    % Finished in 164msec
    

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: