Enigmatic Code

Programming Enigma Puzzles

Enigma 1097: Chessboard triangles

From New Scientist #2253, 26th August 2000 [link]

Take a square sheet of paper of side 1 kilometre and divide it into small squares of side 1 centimetre. Colour the small squares so as to give a chessboard pattern of black and white squares.

When we refer to a triangle, we mean a triangle OAB, where O is the bottom left corner of the square of paper, A is on the bottom edge of the paper and B is on the left hand edge of the paper.

Whenever we draw a triangle then we can measure how much of its area is black and how much is white. The score of our triangle is the difference between the black and white areas, in square centimetres. For example if OA = 3 cm and OB = 2 cm then we find the score of the triangle is 1/6 cm².

Question 1. What is the score of the triangle with OA = 87,654 cm and OB = 45,678 cm?

Question 2. What is the score of the triangle with OA = 97,531 cm and OB = 13,579 cm?

Question 3. Is it possible to draw a triangle on the paper with a score greater than 16,666 cm²?

[enigma1097]

3 responses to “Enigma 1097: Chessboard triangles

  1. Jim Randell 18 September 2017 at 12:09 pm

    A bit of analysis gives us some more general results that can be used to solve the puzzle.

    Consider integer values for A and B.

    We start with a right angled triangle with vertices (0, 0), (A, 0), (0, B).

    By adding a vertex at (A, B) we can make a rectangle, and the diagonal from (A, 0) to (0, B) divides this rectangle into the original triangle and a rotation of the triangle.

    If both A and B are even, then the midpoint of the hypotenuse is at an intersection of the grid (see Enigma 1308, Enigma 1110), and so the triangle and its rotation will be identical. So twice the score of the original triangle will be the same as the score of the entire rectangle.

    The rectangle has sides that are an even number of squares, so overall it has the same number of black squares and white squares, so it’s score is 0. Hence:

    score(A, B) = 0, if both A and B are even

    Solution: Question 1: The score of the first triangle is 0 cm².

    If both A and B are odd, then the midpoint of the hypotenuse is in the centre of a grid square, and again, the triangle and its rotation are identical. So the rectangle has twice the score of the original triangle.

    The rectangle has sides that are both an odd number of squares, so overall it has one more square of one colour than of the other, so its score is 1. Hence:

    score(A, B) = 1/2, if both A and B are odd

    Solution: Question 2: The score of the second triangle is 1/2 cm².

    Now consider a triangle where A = B and A is odd. The hypotenuse cuts through A squares of the same colour (for the sake of argument let’s say they are black), and the score for the triangle is 1/2 (as both A and B are odd).

    The area of the triangle is A²/2 and the score of the triangle is 1/2.

    If we now consider the triangle where B = A + 1, then we have a new triangle which contains the old triangle. The overall area of this new triangle is A(A + 1)/2, i.e. its area is A/2 more than the original triangle, and the extra white area is composed of a series of A smaller versions of the new triangle that are completely white.

    The dimensions of these triangles is as follows (from largest to smallest):

    height = 1, base = A / (A + 1), area = A² / 2A(A + 1)
    height = (A – 1) / A, base = (A – 1) / (A + 1), area = (A – 1)² / 2A(A + 1)
    height = (A – 2) / A, base = (A – 2) / (A + 1), area = (A – 2)² / 2A(A + 1)

    height = 1 / A, base = 1 / (A + 1), area = 1² / 2A(A + 1)

    Summing the areas we get the following extra white area:

    (1 / 2A(A + 1))(A² + (A – 1)² + (A – 2)² + … + 1²)

    The sum of the squares is:

    (A² + (A – 1)² + (A – 2)² + … + 1²) = A(A + 1)(2A + 1)/6

    so overall the extra white area is:

    (2A + 1) / 12

    and the extra black area is:

    (A/2) – (2A + 1)/12 = (4A – 1)/12

    So the difference between the black area and the white area in the new triangle is:

    1/2 + (4A – 1)/12 – (2A + 1)/12 = (A + 2) / 6

    Hence:

    score(A, A + 1) = (A + 2) / 6, if A is odd

    A 1km × 1km grid of centimetre squares is 100,000 × 100,000 squares. So we can draw a triangle with sides 99,999 cm and 100,000 cm and this has a score of:

    score(99999, 100000) = 100001/6 = 16666 + 5/6 cm²

    Solution: Question 3: Yes, it is possible to draw a triangle with a score that exceeds 16,666 cm².

    • Jim Randell 20 September 2017 at 3:52 pm

      We note that although A = 99,9999, B = 100,000 is the largest triangle with a score that exceeds 16,666, it is not the only one.

      We also have:

      score(99997, 99998) = 99999/6 = 16666 + 1/2
      score(99995, 99996) = 99997/6 = 16666 + 1/6

      And the following result:

      score(A, A + 1) = (A – 1) / 6, if A is even

      gives us another triangle:

      score(99998, 99999) = 99997/6 = 16666 + 1/6

      My original program to produce a constructive solution was a bit slow, but here’s a version that can solve the problem constructively in 1.74s. In the incarnation below I have included the results from the above analysis to give a program that solves the problem in 46ms.

      Run: [ @repl.it ]

      #from fractions import Fraction as F
      from gmpy2 import mpq as F
      from enigma import divc, gcd, arg, irange, cached, printf
      
      # calculate the score (where A >= B) by construction
      @cached
      def _score(A, B):
        (x1, y1, m, r, d) = (0, B, +1, 0, F(B, A))
        while x1 < A:
          (x2, y2) = (x1 + 1, y1 - d)
          # calculate where the hypotenuse cuts a y line
          y = divc(y2, 1)
          x = F((B - y) * A, B)
          # areas of the triangles above y and below y
          if x1 < x:
            above = F((x - x1) * (y1 - y), 2)
            below = (1 - F((x2 - x) * (y - y2), 2) if y > 0 else 0)
          else:
            above = 0
            below = F(y1 + y2, 2) - y + 1
          # add in the measure for this column
          if y % 2 == 0:
            r += m * (above - below + (y > 1))
          else:
            r += m * (below - above)
          # move to the next column
          (x1, y1, m) = (x2, y2, -m)
        return r
      
      
      # calculate the score
      def score(A, B):
        if B > A: (A, B) = (B, A)
        
        # if A and B are the same parity
        (pA, pB) = (A % 2, B % 2)
        if pA == pB:
          return (F(1, 2) if pA else 0)
      
        # if A = B + 1
        if A == B + 1:
          return (F(B + 2, 6) if pB else F(B - 1, 6))
      
        # reducible grids
        g = gcd(A, B)
        if g > 1:
          (A, B) = (A // g, B // g)
      
        # compute the value
        return abs(_score(A, B))
      
      
      # tests to run
      args = arg('X123', 0)
      
      if 'X' in args:
        # check the example
        (A, B) = (3, 2)
        r = score(A, B)
        printf("example: score({A}, {B}) = {r}")
      
      if '1' in args:
        # question 1
        (A, B) = (87654, 45678)
        r = score(A, B)
        printf("question 1: score({A}, {B}) = {r}")
      
      if '2' in args:
        # question 2
        (A, B) = (97531, 13579)
        r = score(A, B)
        printf("question 2: score({A}, {B}) = {r}")
      
      if '3' in args:
        # question 3
        # start with the largest triangle and work downwards
        M = 100000
        for t in irange(2 * M - 1, 2, step=-1):
          for A in irange(min(M, t - 1), divc(t, 2), step=-1):
            B = t - A
            r = score(A, B)
            delta = r - 16666
            if delta > 0:
              printf("question 3: score({A}, {B}) = {r}, delta = {delta}")
              exit()
      

      I used the [[ gmpy2.mpq() ]] class to represent rationals, but if you don’t have that available you can use [[ fractions.Fraction() ]] by removing line 2 and uncommenting line 1.

      To run the program without using any analysis, remove lines 35-47 from the [[ score() ]] function.

      Removing the [[ exit() ]] statement at line 85 will allow the program to continue and produce the additional triangles given above for question 3 (although this will take longer).

  2. Brian Gladman 19 September 2017 at 12:57 pm
    from fractions import Fraction as RF
    
    def areas(X, Y):
      # <bk> and <wh> accumulate the areas for black (bottom left) and
      # white squares; <rv> is 0 or 1 depending on whether the first
      # square in the current row is black or white
      bk, wh, rv = 0, 0, 1
      # the starting x value on the line below the row being considered
      xlo = X
      for y in range(Y):
        # set rv for this row
        rv = 1 - rv
        # callculate the x values on the lines above and below the row
        xlo, xhi = xlo - RF(X, Y), xlo
        # find the integer and fractional parts of these values
        xl, fl = divmod(xlo, 1)
        xr, fr = divmod(xhi, 1)
        # add the full squares in the row to the black and white sums
        if rv:
          wh += (xl + 1) // 2
          bk += xl // 2
        else:
          bk += (xl + 1) // 2
          wh += xl // 2
        # now consider all partial squares
        rvv = 1 - rv if xl & 1 else rv
        # if the line divides a square vertically
        if xl == xr:
          if rvv:
            wh += (fl + fr) / 2
          else:
            bk += (fl + fr) / 2
        else:
          # consder all squares crossed by the line
          yr = RF(Y * (X - xl), X) - y
          for xx in range(xl, xr + 1):
            # calculate the fractional y values on the 
            # lines left and right of the square
            yl, yr = yr, yr - RF(Y, X)
            if xx == xl:
              # the line crosses the top and right sides of the square
              t = 1 - (1 - fl) * (1 - yr) / 2
            elif xx == xr:
              # the line crosses the left and bottom sides of the square
              t = fr * yl / 2
            else:
              # the line crosses the left and right sides of the square
              t = (yl + yr) / 2
            # add the result to the appropriate black or white sum
            if rvv:
              wh += t
            else:
              bk += t
            # move on to the next square horizontally
            rvv = 1 - rvv
      return (wh, bk) if rv else (bk, wh)
    
    # Question 1
    x, y = 87654, 45678
    bk, wh = sorted(areas(x, y))
    print(f'Score({x}, {y}) = {wh - bk} cm^2')
    
    # Question 2
    x, y = 97531, 13579
    bk, wh = sorted(areas(x, y))
    print(f'Score({x}, {y}) = {wh - bk} cm^2')
    
    # Question 3
    x, y = 100000, 99999
    bk, wh = sorted(areas(x, y))
    i, f = divmod(wh - bk, 1)
    print(f'Score({x}, {y}) = {i} + {f} cm^2')
    

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: