Enigmatic Code

Programming Enigma Puzzles

Enigma 261: Point in square

From New Scientist #1408, 3rd May 1984 [link]

It took some hours for the ZX Spectrum I received for Christmas to produce this pretty specimen of an integral-sided square, with a point P lying inside it at integral distances from three of the square’s corners.

If you use a computer, it will probably take you just as long to find another such specimen with smaller square-side. But without a computer, it is possible to find a solution in a fraction of the time. P must be inside the square, not outside or on the edge.

What is the length of the side of the smaller square and what are the distances PAPBPC?

[enigma261]

9 responses to “Enigma 261: Point in square”

1. Jim Randell 26 February 2015 at 7:56 am

If we consider the square to be of side N, and the integer distances AP, BP, CP to be a, b, c respectively. And let’s assume that ab.

We choose integers a and b, such that aN/√2, and abN√2.

Then labelling the angle ∠ABP as θ we have (applying the cosine rule to triangle ABP):

a² = N² + b² – 2Nb cos(θ)

which gives:

cos(θ) = (N² + b² – a²) / (2Nb)

let’s say:

x = N² + b² – a²
y = 2Nb

so:

cos(θ) = x/y

Now in the triangle BCP:

c² = N² + b² – 2Nb cos(90° – θ)

and:

cos(90° – θ) = sin(θ)

so:

2Nb sin(θ) = N² + b² – c²

also:

sin²(θ) + cos²(θ) = 1

so:

sin(θ) = √(1 – cos²(θ)) = √(1 – (x/y)²)

or (remembering that y = 2Nb):

2Nb sin(θ) = √(y² – x²)

Now, c is an integer, so is also an integer, so it follows that 2Nb sin(θ) must be an integer, hence y² – x² must be a perfect square, say z², so (x, z, y) are a Pythagorean triple.

So for a given N, we can choose a and b and see if we get a valid c. This Python program checks the possibilities for N from 1 to 52. It runs in 71ms.

```from itertools import count
from enigma import irange, is_square, printf

def solve(N):
N2 = N ** 2
for a in count(1):
a2 = a ** 2
if 2 * a2 > N2: break
for b in count(max(a, N - a)):
b2 = b ** 2
if b2 > 2 * N2: break

(x, y) = (N2 + b2 - a2, 2 * N * b)
if not(x < y): continue

z = is_square(y ** 2 - x ** 2)
if z is None: continue
c = is_square(N2 + b2 - z)
if c is None: continue

printf("[N={N}] a={a} b={b} c={c}")

for N in irange(1, 52):
solve(N)
```

Solution: The smaller square has sides of 51. The distances PA, PB, PC are 25, 52, 53.

2. Jim Randell 26 February 2015 at 8:04 am

As the setter said it took some hours for a ZX Spectrum to come up with the square given in the puzzle I thought I would code my program in BBC Basic (using BeebEm3) to see how long it would take to run. This code runs in 10½ minutes (equivalent time on an actual BBC B).

```>LIST
10 start% = TIME
20 FOR n% = 1 TO 52
30   n2% = n% * n%
40   a% = 1
50   a2% = 1
60   REPEAT
70     b% = n% - a%
80     IF a% > b% THEN b% = a%
90     b2% = b% * b%
100     REPEAT
110       x% = n2% + b2% - a2%
120       y% = 2 * n% * b%
130       IF NOT(x% < y%) THEN GOTO 190
140       z% = FNissquare(y% * y% - x% * x%)
150       IF z% = -1 THEN GOTO 190
160       c% = FNissquare(n2% + b2% - z%)
170       IF c% = -1 THEN GOTO 190
180       PRINT "[n=";n%;"] a=";a%;" b=";b%;" c=";c%
190       b% = b% + 1
200       b2% = b% * b%
210     UNTIL b2% > 2 * n2%
220     a% = a% + 1
230     a2% = a% * a%
240   UNTIL 2 * a2% > n2%
250 NEXT n%
260 PRINT "elapsed time = ";(TIME - start%) / 100;"s"
270 END
280 DEF FNissquare(n%)
290   LOCAL i%
300   i% = INT(SQR(n%) + 0.5)
310   IF i% * i% = n% THEN =i% ELSE =-1

>RUN
[n=51] a=25 b=52 c=53
[n=52] a=25 b=51 c=53
elapsed time = 628.34s
```

Of course, even 10½ minutes is longer than it takes to get the answer by noticing that we can fit the triangles ABP and BCP into a 51 × 51 square by joining them along the sides of length 52.

3. Naim Uygun 26 February 2015 at 9:13 am

Analytic geometry solution without using angles.
Point in the square P(x,y), Square’s side=a

```def kare(n):
h = n & 0xF
if (h > 9) :
return 0
if h in [0,1,4,9]:
t =int(n**0.5)
return (t*t == n)
return 0

for a in range(4,100):

for x in range(1,a):
for y in range(1,a):
d12=x**2+(y-a)**2
if kare(d12) == False: continue

d22=(x-a)**2+(y-a)**2
if kare(d22)==False: continue

d32=(x-a)**2+y**2
if kare(d32)==False: continue

print("\nSquare Side=",a)
print("Three Distances=",int(d12**0.5),int(d22**0.5),int(d32**0.5))```
• Jim Randell 26 February 2015 at 9:21 am

Naim: This code doesn’t seem to find the solution for a square with side 51.

• Naim Uygun 26 February 2015 at 9:31 am

Hi Jim,
Check your figure’s side which is 52.
Here is the output:
Square Side= 52
Three Distances= 25 , 51, 53

Square Side= 52
Three Distances= 53, 51, 25

• Jim Randell 26 February 2015 at 9:40 am

The output from your program gives the square shown in the diagram in the problem statement (in two different ways).

The puzzle is to find a square with a side less than 52.

You should find there is a square of side 51, and the three distances are 25, 52 and 53.

• Naim Uygun 26 February 2015 at 11:58 am

Ok, Jim. No fraction step in ” for loop” in python except list implementation and writing a function for it. The coordinates of the point P(x,y) are approximately x=6,127 and y=24.235 for side length 51.

• Jim Randell 26 February 2015 at 12:42 pm

The horizontal and vertical displacements of P from B are given by:

(N² + b² – c²) / 2N and (N² + b² – a²) / 2N.

When N=52 these are 24 and 45.

But when N=51 they are 416/17 (≈ 24.47) and 780/17 (≈ 45.88), which is why your program didn’t find them. Although the distances PA, PB, PC are integral, the horizontal and vertical displacements of P from the corners are not necessarily integers.

• Naim Uygun 26 February 2015 at 3:35 pm

The coordinates I had indicated was for 52, not for 51,
Here are another properties for 52
Square Side= 52
Four İnteger Distances= 25 51 53 53 x= 7 y= 28

Square Side= 52
Four İnteger Distances= 53 51 25 25 x= 28 y= 7

This site uses Akismet to reduce spam. Learn how your comment data is processed.