### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (94)
- teaser (7)

### Site Stats

- 233,129 hits

Programming Enigma Puzzles

18 September 2017

Posted by on **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, whereOis the bottom left corner of the square of paper,Ais on the bottom edge of the paper andBis 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 andOB= 2 cm then we find the score of the triangle is 1/6 cm².

Question 1.What is the score of the triangle withOA= 87,654 cm andOB= 45,678 cm?

Question 2.What is the score of the triangle withOA= 97,531 cm andOB= 13,579 cm?

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

[enigma1097]

%d bloggers like this:

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

Consider integer values for

AandB.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

AandBare even, then the midpoint of the hypotenuse is at an intersection of the grid (seeEnigma 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:

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

AandBare 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:

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

A = BandAis odd. The hypotenuse cuts throughAsquares 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 bothAandBare odd).The area of the triangle is

A²/2and 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 isA(A + 1)/2, i.e. its area isA/2more 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):

Summing the areas we get the following extra white area:

The sum of the squares is:

so overall the extra white area is:

and the extra black area is:

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

Hence:

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:

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

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

And the following result:

gives us another triangle:

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 ]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).