Enigmatic Code

Programming Enigma Puzzles

Enigma 1686: Squaring the circle

From New Scientist #2853, 25th February 2012 [link]

A builder was contracted to pave a circular courtyard with square paving slabs having sides of length 1 metre. The radius of the courtyard was an exact number of metres. The slabs had to be laid in a rectangular grid with no gaps, and with four slabs meeting at the centre of the circle. The slabs at the edge obviously had to be cut, but the builder had to cut as few slabs as possible.

When he was finished, the builder found he had cut exactly a third of the slabs (he didn’t re-use any of the discarded pieces).

How many slabs were used, and what was the radius of the courtyard?

[enigma1686]

Advertisements

4 responses to “Enigma 1686: Squaring the circle

  1. Jim Randell 22 February 2012 at 9:39 pm

    The following Python program runs in 32ms.

    It considers the points in the quadrant and checks to see if a tile is cut (if the circle passes between the BL corner and the TR corner of the tile), or if it is uncut (the circle is further out than the TR corner).

    from itertools import count
    from fractions import Fraction
    from enigma import printf
    
    # consider a quadrant of the circle of radius r
    # then consider the points (x, y) for x, y in [0, r]
    
    for r in count(1):
      # count the cut and uncut slabs
      r2 = pow(r, 2)
      (c, u) = (0, 0)
      for y in range(r):
        for x in range(r):
          (p0, p1) = (x*x + y*y, (x+1)*(x+1) + (y+1)*(y+1))
          if p0 < r2 < p1: c += 1
          if not(r2 < p1): u += 1
      # total number of slabs used
      t = c + u
      printf("r={r} c={c} u={u} t={t} c/t={f}", f=Fraction(c, t))
      if 3 * c == t:
        printf("radius={r} slabs={s}", s=4*t)
        break
    

    Solution: 132 slabs were used. The courtyard has a radius of 6m.

  2. dave randell 3 March 2012 at 4:20 pm

    It struck me that this a good demo of calculus.

    As the squares get infinitely small, the number to cut tends to the circumference (2*pi*r), and the total number to the area (pi * r * r)

    Therefore if the ratio cut is 1/3,
    2 pi r / pi r*r = 1/3
    gives r = 6.
    I then checked by drawing.

    • Jim Randell 3 March 2012 at 10:11 pm

      I agree that your technique gives good starting point, but I don’t think it gives an accurate answer. If the question had involved cutting one seventh of the slabs your analysis would yield:

      2𝜋r / 𝜋r² = 1/7 ⇒ r = 14.

      But for r=14 there are 27 cut slabs from a total of 166 (in a quadrant). Whereas for r=15 we have 27 cut slabs from a total of 189 and 27/189 = 1/7.

      And besides, if the slabs were infinitely small you wouldn’t have to cut any of them!

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: