 # Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

William A. McWorter Jr.

February 2001 Did you know that recreational mathematics is responsible for crystal clear communications over noisy channels? What would W. Hardy say if he had lived to see his harmless love, number theory, the subject of heated debate over providing modern encryption technology to foreign countries?

It is continuously fascinating how mathematics impinges on itself and the sciences in unexpected and bizarre ways. This page is a small illustration of this phenomenon.

Take a look at the triangular grid T. The plane can be tiled with copies of an equilateral triangle. The vertices of these triangles form the triangular grid. Chinese checkers and a strategy game called Hex are played on these points on boards which are finite portions of the triangular grid.

Fairly familiar stuff. But did you know that the triangular grid is also a quasigroup? That the triangular grid is a block design? And with just a little more effort, that T can produce infinitely many quasigroups and infinitely many block designs?

A quasigroup is a set Q, together with a binary operation *, such that the equations p * x = q and y * p = q have unique solutions x and y in Q, for all p and q in Q.

Examples of quasigroups are, the integers Z with operation + and the nonzero real numbers R with operation · (real multiplication). These two examples have associative operations, and are called groups. A non associative example of a quasigroup is exhibited by the table below, a child of the triangular grid, as we shall see later.

* | abc
--- | ---------
a | acb
b | cba
c | bac

The table means a * a = a, a * b = c, b * c = a, etc. For this quasigroup Q = {a, b, c} the operation * is not associative; e.g., a * (b * c) = a * a = a, but (a * b) * c = c * c = c.

The definition of a quasigroup Q forces its operation table to have the property that every element of Q appears exactly once in every row and column of the operation table. Such a table is known as a latin square.

Latin squares were first investigated by Leonhard Euler as "un nouveau espèce de carré magique", a kind of magic square. Thus latin squares began as a part of recreational mathematics, but now are an integral part of a fundamental branch of mathematics called combinatorics.

Quasigroup, latin square? How can the triangular grid produce such a thing?

A block design is a family of sets, called blocks, satisfying certain conditions. All blocks have the same number of elements, every element occurs in the same number of blocks, and every pair of elements occurs in the same number of blocks. A block design with finitely many elements is called a balanced incomplete block design. It is a set of v elements and a family of b subsets of the v elements, called blocks, such that every block has k elements, every element occurs in r blocks, and every pair of elements occurs in λ blocks. The numbers v, b, r, k, and λ are called the parameters of the design. Here is an example of a balanced incomplete block design with parameters v = 6, b = 10, r = 5, k = 3, and λ = 2.

{1,2,3}, {1,2,4}, {1,3,5}, {1,4,6}, {1,5,6}, {2,3,6}, {2,4,5}, {2,5,6}, {3,4,5}, {3,4,6}.

Balanced incomplete block designs also began as a recreational pursuit when T. P. Kirkman posed his famous Schoolgirl Problem. Now, like latin squares, balanced incomplete block designs are a basic subject of combinatorics (see britannica.com for more on latin squares, block designs, Kirkman's Schoolgirl problem, and combinatorics in general).

A family of sets? In what way can the triangular grid yield a family of sets?

Glad you asked. Consider any two points p and q on the triangular grid T. A clockwise rotation of T through 60° about the point p maps T onto itself. Thus q is mapped onto a point r of T. The triangle pqr is equilateral. Similarly, rotating 60° clockwise about q maps p onto a point s of T so that pqs is an equilateral triangle. Thus any two points p and q of T are vertices of exactly two equilateral triangles whose vertices are points of the triangular grid T. This regularity of pairs of points in T is what enables the interpretation of T as a quasigroup and a block design.

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

The points of the triangular grid T form an infinite block design whose blocks are all triples of grid points which are vertices of equilateral triangles. Every block has k = 3 elements and every pair of elements occurs in exactly λ = 2 blocks.

We can also use the pair regularity of T to turn it into quasigroup. For each pair p and q of points of T, define a binary operation * on T by, p * q equals the image of q under a 60° clockwise rotation of T about the point p. Under this operation *, T becomes a quasigroup. Given points p and q in T, there is a unique point x such that p * x = q, namely, that unique point x in T where p would go in a 60° clockwise rotation about q. Also, there is a unique point y in T such that y * p = q, namely, that unique point y in T where q would go in the 60° clockwise rotation about p.

So far T has provided us with one block design and one quasigroup. To squeeze more designs and quasigroups from T, we invoke the notion of factor group from group theory. Let u be the unit vector (1, 0) in R2 (the 2-dimensional vector space over the real numbers) and let v = (cos(60°), sin(60°)) be the unit vector obtained by rotating u counterclockwise 60°. Then, we may consider the triangular grid as all integer linear combinations of u and v. For convenience we will sometimes indicate a point of T by the ordered pair (x, y), indicating the point xu + yv of T. The triangular grid T now becomes an abelian group under vector addition.

Let f be the 60° clockwise rotation about the origin (0, 0). This map is a linear transformation of R2. Since f(u) = u - v and f(v) = u, f maps T onto itself. We can now define the quasigroup operation in terms of f. A clockwise rotation of a point q of T of 60° about a point p of T is given by p + f(q - p). We gather together some useful properties of f.

f(sp) = sf(p), for all integers s and points p of T, f(p + q) = f(p) + f(q), for all points p and q of T, because f is a linear transformation, and f(f(p) - f(p) + p = (0, 0), for all points p of T, because, for p = xu + yv, we have

 f(f(xu + yv)) - f(p) + p = f(xf(u) + yf(v)) - f(p) + p = f(x(u - v) + yu) - f(p) + p = x(f(u) - f(v)) + yf(u) - f(p) + p = x(u - v - u) + y(u - v) - f(p) + p = -xv + yu - yv - f(xu + yv) + xu + yv = x(u - v) + yu - xf(u) - yf(v) = x(u - v) + yu - x(u - v) - yu = (0, 0).

Let's look at some of the properties of the quasigroup operation *. The rotation f fixes the origin O = (0, 0), so

p * p = p + f(p - p) = p + f(O) = p + O = p.

A quasigroup Q is idempotent if every element x in Q satisfies x * x = x. Hence the triangular grid T under the operation * is idempotent.

Also, for any points p and q in T, the points p, q, and p * q form an equilateral triangle (possibly degenerated to a single point). Hence rotating p * q 60° clockwise about q should carry it to p. Thus q * (p * q) = p, for all p and q in T (this identity can be verified directly using the above formula for p * q). Similarly, (q * p) * q = p, for all p and q in T, but not because of associativity; for quasigroups are not generally associative. In particular, T is not. It is a quick exercise to show that the identity (q * p) * q = p can be deduced from the identity q * (p * q) = p without reference to the definition of *.

Remarkably, even though T under * is not associative, left multiplication by an element of T induces an automorphism of T as a quasigroup. A function F on a quasigroup Q is an automorphism if F is a 1-1 map from Q onto Q such that F(p) * F(q) = F(p * q), for all p and q in Q. The reason left multiplication of T by an element of T is an automorphism of T follows from the fact that, by the definition of *, left multiplication of T by an element p of T is a clockwise rotation of T about the point p, an automorphism of T as a group under vector addition, provided p is chosen to be 0 of that group. Since the origin could be associated with any node of the grid, rotation through 60° around any node is an automorphism of the quasigroup T. So, we have a further identity for T as a quasigroup under the operation *, (p * x) * (p * y) = p * (x * y), for all p, x, and y in T. (The reader may enjoy showing that right multiplication by p is also an automorphism of T, a direct consequence of the identity (p * x) * (p * y) = p * (x * y); i.e., this identity implies (x * p) * (y * p) = (x * y) * p, for all p, x, and y in T.)

The triangular grid T under the operation * is also anticommutative; i.e., whenever p≠q, then p * q≠q * p. This fact, together with the identities p * p = p and q * (p * q) = p enable the construction of a block design with k = 3 and λ = 2. Just define the blocks by the distinct sets of the form {p, q, p * q}, for all distinct p and q in T. (Although it is allowed for some blocks of a block design to be identical, all blocks of this design are distinct.) Ok. Now let's look at what the triangular grid has to say about finite quasigroups and finite block designs. Our construction is due to our host, Alexander Bogomolny. The author's original construction is a limited special case of Bogomolny's idea. (A note from A.B.: The insight for my contribution has originated with a flash recollection of the plane tessellation induced by Napoleon's theorem.)

Let a and b be integers, not both zero. Select vectors (a, b) = au + bv and (-b, a + b) = -bu + (a + b)v. These two vectors are nonzero and belong to T. Moreover, the points (0, 0), (a, b), and (-b, a + b) are the vertices of an equilateral triangle because f rotates (-b, a + b) onto (a, b):

f(-b, a + b) = -bf(u) + (a + b)f(v) = -b(u - v) + (a + b)u = au + bv = (a, b).

Let H be the subgroup of T generated by these two vectors. The factor group T/H, consisting of the cosets of H, is a finite group of order a2 + ab + b2. This number is the ratio of the area of the triangle with vertices (0, 0), (a, b), and (-b, a + b) to the area of the triangle with vertices (0, 0), (1, 0), and (0, 1). It is also the number of points r(a, b) + s(-b, a + b) in T, where r and s are nonnegative rational numbers less than 1.

The factor group T/H is also a quasigroup under the operation * defined on the cosets of H by

(H + p) * (H + q) = H + p * q.

Before proving that * is well-defined and other needed properties, let's look at some small examples.

Let a = b = 1. Then a2 + ab + b2 = 3 and the cosets of T/H are H, H + (1, 1), and H + (2, 2). The multiplication table for T/H under * is displayed below.

* | HH + (1, 1)H + (2, 2)
---------------- | ------------------------------------------------
| HH + (2, 2)H + (1, 1)
H + (1, 1) | H + (2, 2)H + (1, 1)H
H + (2, 2) | H + (1, 1)HH + (2, 2)

We can form this table by using the formal definition of * on T/H, or we can perform the calculation geometrically. Just do * in T and replace the elements obtained by the cosets of H containing them. We do this with our next example, with the help of a handy applet.

Let a = 2 and b = 0. Then the corresponding subgroup H of T has 4 cosets, H, abbreviated 4, H + (1, 0), abbreviated 1, H + (0, 1), abbreviated 2, and H + (1, 1), abbreviated 3. The multiplication table for T/H is given below.

* | 1234
--- | -----------
1 | 1342
2 | 4213
3 | 2431
4 | 3124

We can see how this table is obtained by considering the portion of the triangular grid below, with its points labelled by the coset of H that contains the point. To compute a product, we compute as we would with the points of T, except that we label the result by the coset of H containing the result of the computation. For example, look at the first 4 and 1 in the last row of the display above. By the definition of * on T, 1 * 4 should be the first 2 in row 3, the 60° clockwise rotation of 4 about 1. Similarly, looking at the first 1 in the second row and the second 2 in the first row, the product 1 * 2 should be the last 3 in row 3, the 60° clockwise rotation of 2 about 1. The applet below allows you to see the product of two points for various values of a and b. (Clicking on two circles determines the vector (a,b) and, consequently, (-b,a+b) as well. The red and blank circles are the elements of H and the circles of one color are the elements of a single coset of H.)

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

The block design associated with this quasigroup has parameters v = b = 4, r = k = 3, and λ = 2. Its blocks are

{1, 2, 1 * 2) = {1, 2, 3}, {1, 3, 1 * 3} = {1, 3, 4}, {1, 4, 1 * 4} = {1, 4, 2}, {2 , 4 , 2 * 4} = {2, 4, 3}.

This design is not new. In fact, it is trivial. It is all 3-element subsets of a 4-element set. For other choices for a and b we get non-trivial block designs, as long as a - b is not divisible by 3 (we get quasigroups for all a and b, not both zero, but anticommutative ones only for a - b not divisible by 3). The parameters of these designs are v = a2 + ab + b2, b = v(v - 1)/3, r = v - 1, k = 3, and λ = 2, for all integers a and b, a - b not divisible by 3. These designs include designs with v = 4, 7, 13, 16, 19, 25, 31, and so on.

Block designs for k = 3 and λ = 2 are known for all feasible parameters v, b, and r. So none of the block designs constructed here settle any unknown cases. Nor do these designs cover all feasible parameters. The example of a design shown first in this article has v = 6, a parameter never produced by T. However, the designs constructed here have special properties, which we want to examine next, and apply them to the following scheduling problem.

Suppose we wish to schedule a round robin chess tournament among 6 players so that every player plays every other player exactly once with the black pieces. That's 30 games altogether. To spread things out somewhat, we'd like there to be three games a day for three players. A partial solution without regard to who plays who with what pieces is provided by the block design given at the beginning of this page. It turns out that this block design permits choosing who plays who each day so that each player plays every other player exactly once with the black pieces. A complete solution is displayed below.

Blocks Games {1, 2, 3} b 1 2 3w 2 3 1 {1, 2, 4} b 2 1 4w 1 4 2 {1, 3, 5} b 1 3 5w 3 5 1 {1, 4, 6} b 4 1 6w 1 6 4 {1, 5, 6} b 1 5 6w 5 6 1 {2, 3, 6} b 3 2 6w 2 6 3 {2, 4, 5} b 2 4 5w 4 5 2 {2, 5, 6} b 2 6 6w 5 5 2 {3, 4, 5} b 3 5 5w 4 4 3 {3, 4, 6} b 4 3 4w 3 6 6

For example, the day players 1, 2, and 3 play, 1 plays 2 with the black pieces, 2 plays 3 with the black pieces, and 3 plays 1 with the black pieces. Each player plays two games that day with one rest break.

Conveniently, all of the designs derived from the triangular grid allow the construction of round robin chess tournament schedules. In fact, all these designs are what are known as Mendelsohn triple systems, block designs with block size 3 and λ = 2 in which the elements of each block can be ordered cyclically so that every ordered pair of elements occurs in exactly one block. This is easy to see. For, every equilateral triangle in T can have its vertices ordered clockwise (or counterclockwise). The blocks of T/H can be given the same ordering. Let's look at one more example.

Let a = 2 and b = 1. Then the corresponding subgroup H has a2 + ab + b2 = 7 cosets in T. The quasigroup and associated block design are displayed below. {1, 2, 7}, {2, 1, 5}, {1, 3, 6}, {3, 1, 7}, {2, 5, 6}, {5, 1, 4}, {2, 3, 4}, {3, 2, 6}, {7, 2, 4}, {4, 6, 7}, {4, 3, 5}, {5, 3, 7}, {7, 6, 5}, {6, 4, 1}.

The elements of the blocks above are listed in such a way that, if you order the elements of each block cyclically from left to right, you get a schedule for a round robin tournament for 7 players, with each player playing every other player exactly once with the black pieces.

### Reference

1. Th. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press, Cambridge, vols 1 and 2, 1999.
2. W. D. Wallis, Combinatorial Designs, Monographs and Textbooks in Pure and Applied Mathematics, 118, (1988)  