|The Games and Puzzles Journal Issue 29, September-October 2003|
The questions discussed here were originally intended to form part of the Puzzle issue, but expanded into a separate study. The problem that set it off was to find a true 'circular chess board' of 64 square cells. A solution to this problem is given towards the end, [UPDATE: Octavian Laiu (Romania) has found a better solution!] but we start with some definitions and a survey of simpler cases.
|(51) Circling the Squares: Introduction and Problems||é|
By a circular polygon I mean the outline of the shape formed by the whole unit cells within a circle drawn on a lattice of squares. Sometimes it is possible to contract the circle until it touches the outer corners of three or more cells. Then, since it cannot be contracted further, it is of the minimal size to contain the polygon. However in other cases, such as the case of three squares, there is no minimum or maximum. So, to give a unique solution where there is no minimum radius I suggest that we select a centre whose coordinates are rational and in which the denominators are the smallest, in this case 3.
For N = 3 the three cells must form the L-shaped tromino and the centre can be taken anywhere on the half-diagonal from the inner corner (0, 0) to the centre (1/2, 1/2) of the middle square of the three (and also at various other points). So that the radius can take any value between Ö2 and Ö10/2. A circle of radius Ö2 centred at (0, 0) encloses 4 squares and one of radius Ö10/2 centred at (1/2, 1/2) encloses 5. If we take the centre at (1/3, 1/3) the radius is Ö20/3 @ 1.491 and at centre (1/4,1/4) the radius is Ö34/4 @ 1.458.
It is easy to enclose a square formed of 1 or 4 or 9 or 16 squares within a circle without including any further cells. However a circle through the corners of a 25-cell square also encloses four extra squares at the middles of the sides. The minimal circle here touches twelve outer corners of the unit squares. This is because in the radius Ö50/2 the number under the square root can be expressed in two ways as a sum of two squares; 50 = 5² + 5² = 1² + 7².
Also it may be noted that 16 cells can be fitted within a slightly smaller circle than the 4 by 4 array, in the form of a 4 by 5 array with corner cells omitted. The radii of the two minimal enclosing circles are Ö8 = Ö32/2 @ 2.83 and Ö29/2 @ 2.69. (The above diagrams are not drawn to this accuracy.)
The solutions to these five problems are presented in the following sections. Problem 1 in section (52), Problems 2 and 3 in section (53), Problems 4 and 5 in section (54). So you may wish to try solving the problems yourself before moving on to the later sections. Section (55) is an independent study.
PROBLEM 1: Squared Circle with Integral Centre. A circle centred at the corner of a cell, i.e. at a grid point, which we can take to be (0, 0), will contain 4n whole cells. Construct the next circle centred on (0, 0) that encloses a circular polygon with a square number of cells greater than 16. Within this circle find one circle that touches the outer corners of 12 unit cells and two that touch 16.
PROBLEM 2: A Clock-Face Design. I have designed a clock face with the following properties which you are required to reconstruct. The design is based on a grid of unit squares the grid lines being drawn vertically and horizontally. The twelve clock numbers 1 to 12 are placed in the centres of twelve of the unit squares. A circle can be drawn so as to touch the outer corners of these 12 unit square cells, which are arranged as regularly as possible round the circle (i.e. at approximately 30 degree intervals).
Also incorporated in the design are four concentric circular polygons [as defined above], each containing a square number of cells. Also: round the outside of the clockface there are five circles each touching the outer corners of 12 or 16 unit square cells. The circular polygon border of the clockface has 16 of its outward pointing corners on the outermost circle, 16 intermediate points on a second circle and 12 of its inward pointing corners on a third circle. The other two crcles, come between this outer triplet and the clock numbers. (Another 16-point circle could be drawn inside the circle of clock numbers but is omitted, since it would intersect the numbers.)
PROBLEM 3: Circular Polygons and Round Numbers. It is possible to construct three concentric circular polygons containing respectively exactly 100, 200 and 300 complete unit square cells. How can this be done? In the case of the 300-cell board the containing circle touches it at 12 points. There is one other smaller circle that also touches twelve outer corners of unit cells.
PROBLEM 4: Circular Boards with Higher Fractional Centres. The centres used in Problems 1, 2 and 3 provide circular boards with an infinite set of different numbers of cells, but still do not solve all cases. In particular they do not solve any cases with 4n + 3 cells. There are also many other cases of 4n, 4n + 1 and 4n + 2 cells still to be solved. I have found solutions to all cases less than 40 cells. In particular the preceding problems show circular polygons with all the smaller square numbers except 25 and 36.
PROBLEM 5: Larger Circular Boards. Is it always possible to find a circle to enclose exactly N whole unit cells for any number N? It looks as though this may be the case, but I have not yet proved so to my satisfaction. It may be that there is a large number N for which there is no enclosing circle (or at least none with rational centre).
I offer for solution the next unsolved square number 64. The resulting board does not of course have to have octonary symmetry, or indeed any symmetry at all. However the coordinates of the centre point should be rational fractions with smallest possible denominators (a whole number counts as having having denominator 1), and the radius of the enclosing circle should preferably be as small as possible.
In similar fashion to the 25-cell case discussed in the introduction a circle drawn to enclose a normal 64-cell chessboard of unit squares, passing through its four corners, has a diameter of 8Ö2 @ 11.314 and leaves enough space to include four further cells at the middle of each edge, giving a board of 80 cells. Reducing the circle to one of diameter Ö(10² + 2²) = Ö104 @ 10.198, still centred at a point where four cells meet, will enclose a board of 68 cells with octonary symmetry. This is the Troitzky Board, derived from the standard board by removing the four corner cells and inserting two cells in the middle of each edge. [See Variant Chess 3(25) p.93, (1997) and 3(28) p.169, (1998) for games and knight's tours on this board.]
There is also the related question of determining the maximum and minimum number of unit square cells that a circle of given radius can enclose. Here is one case I have solved: Draw a circle of radius 5 units on a lattice of unit square cells to contain the maximum number of whole unit cells.
|(52) Circles Centred at Grid Points||é|
PROBLEM 1: A Squared Circle.
Here is a table of radii and numbers of cells for circles centred at (0,0).
The diagram shows the answer to the question. The bold lines mark the circular polygons with a square number of cells. After cases 4 and 16, no circles centred at (0.0) will enclose exactly 36, 64, 100, 144 or 196 cells, and the next case possible is the surprisingly large 256 = 16². The dots mark the outer corners where the circles meet the unit squares. In the case where 12 cells are added four of the added cells are on the diagonals.
|(53) Circles Centred at Half-Fraction Grid Points||é|
PROBLEM 2: A Clock-Face Design.
Here is a table of radii and numbers of cells enclosed for centre at the centre of a cell, that is typically (1/2, 1/2).
[Note that Ö5/2 means Ö(5)/2 not Ö(5/2).]
Here is the clock face design.
The circles mentioned in the design that touch 12 and 16 cells are those of radii Ö130/2, Ö170/2, Ö250/2, Ö290/2, Ö338/2, Ö370/2, Ö410/2. The four circular polygons enclose 1, 9, 49 and 121 cells and are of radii Ö2/2, Ö18/2, Ö82/2,Ö178/2 (this last is just slightly larger than the circle that meets the 12 clock number cells). The angle between the lines from the centre to the middle of the cells numbered 12 and 1 is arctan 3/5 which is about 30.96 degrees.
PROBLEM 3: Circular Polygons and Round Numbers.
A circle centred at the mid-edge of a cell, say at (0, 1/2) will contain either 4n or 4n+2 cells. Here is a table of all the circular boards that can be produced in this way, up to about radius 10, together with their radii.
Table of results for Centre (0, 1/2)
Here is the solution to the problem.
In the diagram, the heavy lines mark the 100, 200 and 300-cell boards of radii Ö153/2, Ö293/2 and Ö425/2. The circles mark the cases Ö325/2 and Ö425/2 where the number of cells increases by 10 and 12 respectively (though each touches twelve outer corners of unit cells).
|(54) Higher Fractional Centres and Larger Boards||é|
PROBLEM 4: Circular Boards with Higher Fractional Centres.
The sizes that are missing from the three cases with centres at (0, 0), (1/2, 1/2) and (0, 1/2) are:
(a) all numbers of the form 4n + 3, that is: 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103, 107, 111, 115, 119, 123, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179, 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239, 243, 247, 251, 255, 259, ...
(b) the following numbers of form 4n+1: 17, 25, 33, 41, 53, 65, 77, 81, 85, 93, 105, 109, 117, 125, 133, 141, 153, 165, 169, 173, 181, 189, 193, 201, 209, 217, 225, 229, 237, 249, 253, 257, ...
(c) the following even numbers: 10, 14, 20, 28, 36, 38, 42, 46, 48, 50, 54, 58, 64, 72, 78, 84, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126, 134, 136, 142, 144, 152, 160, 170, 174, 176, 178, 182, 186, 190, 194, 198, 202, 204, 206, 210, 214, 218, 220, 222, 228, 232, 236, 244, 246, 252, 260, ....
So it is natural next to try to construct circles enclosing these numbers of unit squares.
The following table summarises the best solutions for the small cases of less than 40 cells, that I happen to have found. There is no guarantee that they are the best, since I have only looked at cases with denominators 2, 3, 4 and 8.
PROBLEM 5. Larger Square Boards.
A 64-cell circular board can be achieved by taking the centre on the edge of a square and between 1/4 and 1/2 along the edge. If we take it at 3/8 then the distances from the centre to the points A, B, C, D in the first diagram below (which is only an approximate drawing) are: A: Ö[3² + 4.375²] @ 5.305, B: Ö[4² + 3.375²] @ 5.234, C: Ö[5² + 1.375²] @ 5.186, D: Ö[5² + 1.625²] @ 5.257, E: Ö[4² + 3.625²] @ 5.398, F: Ö[2² + 4.625²] @ 5.039. So if we take OC as radius then F is inside the circle and A, B, D, E are outside. The required diameter is thus @ 10.372. Note that this is paradoxically greater than the diameter for the 68-cell Troitzky board.
The number of cells enclosed by a circle of diameter 10 units is 61 when its centre is at the centre of a cell and 60 when its centre is at the corner or mid-edge of a cell, but 62 can be achieved if its centre is shifted slightly off the centre of a cell, along a diagonal, as in the second diagram above.
The square numbers 144, 169, 225 remain unsolved so far.
UPDATE: I received the following email 13 February 2013 from Octavian Laiu of Romania. Dear Mr. Jelliss, I was interested in finding a circular polygon made by the 64 cells of the chessboard which has the circumscribed circle with the shortest diameter. I found your page "Circling the Square" in 'The On-line Journal for Mathematical Recreations', Issue 29, Dec. 2003, very interesting and useful. The best result mentioned there was a 64-cell circular board derived from the 68-cell Troitzky board (D=10.198). I have tried different arrangements and the best 'packing' I found is the one in the image attached (D=10.119). I'd be grateful if you could let me know if you are aware of other works in this area or of better results. Warm regards, Octavian Laiu (Tavi L.)
I replied on 17 February 2013: Just to confirm that I have now checked your result and found it correct. If the contact point at the bottom left is taken to be (1,1) then the centre is at (263/58, 268/58). Will you be publishing it anywhere?
O.L. replied on 18 February 2013: I am working on a book (in Romanian) about puzzles on the chessboard (both chess and not-chess related). I plan to include this result there.
|(55) Circles Among the Lattice Points (Some Infinitist Nonsense)||é|
We now look at some general theory of circles among lattice points. The lattice points in a Euclidean plane are those with whole number coordinates (m, n) where m and n can be positive, negative or zero. On this plane we draw a circle with centre (x, y) and radius r, where the numbers x, y, r may be any real numbers (i.e. zero, rational or irrational).
THEOREM. The condition for points (m, n) and (r, s) to be equidistant from (x, y) is 2(n s)y + 2(m r)x = [(m r)(m + r) + (n s)(n + s)]. Proof: By the theorem of Pythagoras the distance from (x, y) to a grid point (m, n) is Ö[(m x)² + (n y)²] = Ö[x² + y² + m² + n² 2mx 2ny]. The distance to another grid point (r, s) is similarly expressed. For these two distances to be equal we require m² + n² 2mx 2ny = r² + s² 2rx 2sy. This equality can be rearranged to give the condition stated.
THEOREM. If there are two grid points equidistant from (x, y) then we must have hx + ky = j where h, k, j are integers. Proof: Consider the condition given in the previous theorem for the distances from (x, y) to (m, n) and (r, s) to be equal. If n = s this equation reduces to 2x = (m + r). Similarly if m = r the equation reduces to 2y = (n + s). If n ¹ s and m ¹ r the equation takes the form hx + ky = j where h, k, j are integers, h and k not zero.
DEFINITION. Let us call pairs of numbers (x, y) with the property hx + ky = j, where h, k, j are integers, compatible. All pairs of rational numbers are compatible. Any rational number is compatible with any irrational number (taking the coefficient of the irrational to be 0). Geometrically this means that a line can be drawn through (x, y) to meet the x and y axes at points whose coordinates are rational numbers (0, j/k) and (j/h, 0), except when h or k are 0 in which case the line is parallel to the x or y axis. Any irrational number x is compatible with irrational numbers of the form a + bx where a and b are rational. For a pair of numbers to be incompatible they must both be irrational.
THEOREM. If x and y are incompatible numbers then no two lattice points are at the same distance from (x, y). Proof: This is simply a restatement of part of the previous theorem using the definition just given.
DEFINITION: An enumeration of a set S is a one-to-one correspondence between its elements and the positive whole numbers. In other words we number the elements 1, 2, 3, ...
THEOREM. Each pair of incompatible numbers (x, y) determines an enumeration of the lattice points. Proof: If x and y are incompatible irrational numbers then all the lattice points are at different distances from (x, y). We can therefore list the lattice points in order of their distances from (x, y): 1 being the nearest, 2 the next nearest and so on.
THEOREM. We can always adjust the coordinate system of the lattice points so that the centre of the circle is within or on the triangle (0, 0), (0, 1/2), (1/2, 1/2). Proof: The point (X, Y) always lies in or on one of the unit squares of the grid, since any real number is either an integer or the sum of an integer and a fraction between 0 and 1, these fractions (x, y) are the new cordinates of the centre. The unit square can be divided into eight congruent triangles by its diagonals and medians, and any of these can be superimposed with another by rotation or reflection of the square upon itself. This may require the transposition of the coordinates so that we have x £ y.
THEOREM. If x and y are incompatible and we take (x, y) within the triangle O = (0,0), E = (0, 1/2), C = (1/2, 1/2) then in the enumeration determined by (x, y) the first grid point is (0,0), the second is (0,1), the third is (1,0), but the fourth is either (1,1) or (1,0). Proof: d(0,0) = Ö[x² + y²], d(0,1) = Ö[x² + y² + 1 2y], d(1,0) = Ö[x² + y² + 1 2x]. These are in the required order since 0 < x < y < 1. Whether (1,1) or (1,0) is next depends on whether (x, y) is above or below the perpendicular at (0, 1/2) to the line joining (1,1) and (1,0). These lines are shown bold in the diagram.
THEOREM. If x and y are incompatible then the enumeration of the grid points determined by (x, y) is unique. Proof: Suppose centres X = (x, y) and U = (u, v), within the triangle (0, 0), (0, 1), (1/2, 1/2), determine the same enumeration. Then we know X and U cannot be on the same line through O = (0,0), so the two lines OX, OU form a diverging wedge from O. Likewise the lines through O perpendicular to OX, OU form two oppositely directed diverging wedges. No matter how small the angle between these two lines they must eventually diverge far enough apart, i.e. two units, to include a grid point R = (r, s). [In the diagram below we show R as (2, 1).] By symmetry the opposite wedge must include the grid point S = (r, s). The line RS is entirely within the wedges. Therefore the perpendicular to RS at (0,0) must be within the wedge OX, OU. This line passes between X and U. We must therefore have XR > XS and UR < US, since equality occurs only for points on the perpendicular to RS. That is, in the enumeration determined by X we have S preceding R but in the enumeration determined by U we have R preceding S. They must therefore be different enumerations.
NOTE: The reason I've subtitled this 'Some Infinitist Nonsense' is that while it is fun it is not useful geometry bearing any applicability to the real space of physics. The rarefied points whose coordinates are incompatible irrationals have no existence in practical geometry, since there all coordinates are rational numbers determined to within a certain margin of indefiniteness. For further recent discussions on 'Infinity: Reality or Fantasy' resulting from a discussion of Infinity on the BBC Radio-4 programme 'In Our Time' see the Mathematical Recreations Discussion Group. [This closed down. I hope to provide an alternative link in due course.]