Enigmatic Code

Programming Enigma Puzzles

Enigma 1739: Dodecagarden

From New Scientist #2907, 9th March 2013 [link]

In our local park the “Dodecagarden” is fenced in by 12 straight fences: the shortest is 1 metre long and the longest is less than 100 metres long.

The 12 corners of the garden all lie on a circle whose radius is a whole number of metres, and the 12 angles made at the corners by the fences are all equal.

Some of the fences have been reclaimed from an earlier use. Three shortest fences once enclosed a triangular garden and three longest fences once enclosed another triangular garden. The area of the larger triangle was a whole number times the area of the smaller one.

How many times?

Enigma 1528 is also about cyclic polygons.

[enigma1739]

Advertisements

12 responses to “Enigma 1739: Dodecagarden

  1. Jim Randell 6 March 2013 at 10:11 pm

    I’ll add a diagram later to explain the details. This Python program runs in 35ms.

    from itertools import count
    from enigma import is_square, sqrt, printf
    
    # in order for r to be an integer, x must be an integer multiple of sqrt(3)
    for n in count(1):
      x2 = 3 * n ** 2
      if not(x2 < 10000): break
      r = is_square(x2 + 3 * n + 1)
      if r is None: continue
      # the ratio of the triangles is x^2
      printf("R={x2} [n={n} r={r} x={x}]", x=sqrt(x2))
    

    Solution: The area of the larger triangle was 147 times the area of the smaller triangle.

    • Jim Randell 7 March 2013 at 10:15 am

      Here’s my derivation of the equations used in the above program:

      A cyclic 12-gon with the same angles at the corners is either regular (all edges are the same length) or the edges alternate between two different lengths, which is the situation here. We are told there is a “longest” length and a “shortest” length (which is 1).

      So let the longer sides have length x, then the solution is the ratio of the areas of two equilateral triangles, one with sides of length x and one with sides of length 1. Hence the required ratio R is x²/1², which is just x².

      So consider one quadrant of the 12-gon (shown in blue):

      Enigma 1739

      The triangle shown in red has a hypotenuse of r (the radius of the circle), a height of ½ (half the length of the shortest side), and a width of x + √3/2.

      So:

      r² = ¼ + [x + √3/2]² = x² + x√3 + 1

      And if r is an integer, then so is r², so it follows that x is some multiple of √3.

      So let: x = n√3

      Then:

      r² = x² + 3n + 1 = 3n² + 3n + 1

      The program considers increasing n, until x² (= 3n²) exceeds 10000 (and so x exceeds 100), looking for values of n where 3n² + 3n + 1 is a perfect square.

      Once this is found the required solution is the ratio of the areas of the equilateral triangles, which is x².

      • Jim Randell 7 March 2013 at 1:47 pm

        A more direct way to derive the relationship between r and x is to consider two adjacent sides of the 12-gon. (And it’s a much simpler diagram to draw).

        Enigma 1739b

        The angle AOC is 60° and the sides OA, OC are length r, hence AC = r.

        We then apply the cosine rule to the triangle ABC to get:

        r² = 1² + x² – 2x cos(150°) = x² + x√3 + 1

        The rest of the solution follows as above.

      • tonysmith 8 March 2013 at 9:29 am

        If you solve the first quadratic above for x you can see that it does not follow that x is a multiple of root three

        • Jim Randell 8 March 2013 at 10:04 am

          If r² = x² + x√3 + 1, and and (and 1) are integers, then x√3 is also an integer, so let x√3 = m (for some integer m). Then:

          x = m/√3, so: x² = m²/3.

          But is an integer, so 3 divides m, so let m = 3n (for some integer n). Hence:

          x = m/√3 = 3n/√3 = n√3.

          QED.

        • tonysmith 8 March 2013 at 5:14 pm

          Please ignore my previous hasty comment.
          In fact your method leads quickly to the underlying Pell equation (which I reached by a messier route) which can be solved easily.

  2. Brian Gladman 7 March 2013 at 9:03 am

    Here is a solution using Pell’s equation:

    # For equal corner angles there can be only two different (alternating)
    # side lengths (angles subtended at the circle centre of x and 60 - x). 
    # These two  lengths give a ratio for the areas of the two triangles as
    # s^2 with:
    #
    #   2.r.sin(x/2) = 1
    #
    #   s = 2.r.sin(30 - x/2) = r.cos(x/2) - 3^(1/2)/2
    #
    # If s is an integer it must be a multiple of 3**(1/2) so that:
    #
    #   s = r.cos(x/2) - (1/2) * 3**(1/2) = k * 3**(1/2)
    #
    # This can be reduced to Pell's equation:
    #
    #   (2.r)**2 - 3 * (2 * k + 1)**2 = 1
    #   
    # which has the infinite sequence of solutions:
    #
    #   (2.r) + 3 ** (1/2) * (2 * k + 1) = {2 + 3**(1/2)} ** n
    #
    # for n = 0, 1, 2, ...  With u = 2 * r and v = 2 * k + 1, these
    # solutions satisfy the recurrence relations:
    #
    #   u[n + 1] = 2 * u[n] + 3 * v[n]
    #   v[n + 1] = 1 * u[n] + 2 * v[n]
    
    u, v = 2, 1
    while True:
      # generate the next solution
      u, v = 2 * u + 3 * v, u + 2 * v
      # we need u to be even (2 * r) and v to be odd (2 * k + 1)
      if v & 1:
        mult = 3 * (v // 2) ** 2
        if mult > 10000:
          break
        print('multiple = {:d}, radius = {:d}'.format(mult, u // 2))
    
    • Jim Randell 8 March 2013 at 7:36 pm

      I read up on Pell’s equation, and then realised that I wrote a solver for them (based on continued fraction convergents for square roots) for Project Euler Problem 66. My take on this approach is…

      Starting from the equation r² = 3n² + 3n + 1 (derived above) and substituting a = 2r, b = 2n + 1 gives the Pell’s equation: a² – 3b² = 1. So any solution of the Pell’s equation with an even value for a and an odd value for b also gives a solution for the original equation.

      We only need to consider the first four solutions generated by the solver (due to the upper limit on fence size), and only two of those are even/odd combinations required to solve the original equation.

      For comparison my original code checks 57 candidates for n, and if the upper limit for fence length was a much larger number than 100 it would be far more efficient to use the Pell’s equation solver than considering consecutive values of n.

  3. ahmet cetinbudaklar 7 March 2013 at 11:23 am

    There are 12 triangles whose top corners are located in the circle of r m radius and carry fences of 1 m and x m alternately where r is an integer number.

    If A represents the equal angle of the dodecagarden we can deduce that
    A=(12(180)-360)/12=150

    Then the rotating fences create Isosceles triangles with angles of B and (150-B) which are CosB=0.5/r and Cos(150-B)=x/(2r)

    The smallest 3 fences make up a triangle with an area of S(1)=SQRT(3)/4 and the largest 3 fences make up a triangle with an area of S(x)=(x^2)(SQRT(3))/4 , giving us S(x)/S(1)=x^2 which can take us to the solution.

  4. ahmet saracoğlu 9 March 2013 at 11:51 am

    #For python 2.7

    def FindResult():
    	for A in range(1,100):
    		term1=(A**2)/3.0
    		term2=A+1+term1
    		r=term2**0.5
    		if round(r)==r:
    			print term1 
    			print r,A
    FindResult()
    

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: