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?

Enigma 261

[enigma261]

Advertisements

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

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: