Did you know that recreational mathematics is responsible for crystal
clear communications over noisy channels? What would G. H. 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
(played at Playsite.com) 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.
| * | | | a | b | c |
|---|
| --- | | | --- | --- | --- |
|---|
| a | | | a | c | b |
|---|
| b | | | c | b | a |
|---|
| c | | | b | a | c |
|---|
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 60o 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
60o 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.
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 60o 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
60o 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 60o 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(60o), sin(60o)) be the unit vector
obtained by rotating u counterclockwise 60o. 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 60o 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 60o 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 60o 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. 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 * qq *
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.
| * | | | H | H + (1, 1) | H + (2, 2) |
|---|
| ---------------- | | | ---------------- | ---------------- | ---------------- |
|---|
| | | H | H + (2, 2) | H + (1, 1) |
|---|
| H + (1, 1) | | | H + (2, 2) | H + (1, 1) | H |
|---|
| H + (2, 2) | | | H + (1, 1) | H | H + (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.
| * | | | 1 | 2 | 3 | 4 |
|---|
| --- | | | -- | --- | --- | --- |
|---|
| 1 | | | 1 | 3 | 4 | 2 |
|---|
| 2 | | | 4 | 2 | 1 | 3 |
|---|
| 3 | | | 2 | 4 | 3 | 1 |
|---|
| 4 | | | 3 | 1 | 2 | 4 |
|---|
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
60o 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 60o
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.)
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 3
w 2 3 1 |
| {1, 2, 4} | | b 2 1 4
w 1 4 2 |
| {1, 3, 5} | | b 1 3 5
w 3 5 1 |
| {1, 4, 6} | | b 4 1 6
w 1 6 4 |
| {1, 5, 6} | | b 1 5 6
w 5 6 1 |
| {2, 3, 6} | | b 3 2 6
w 2 6 3 |
| {2, 4, 5} | | b 2 4 5
w 4 5 2 |
| {2, 5, 6} | | b 2 6 6
w 5 5 2 |
| {3, 4, 5} | | b 3 5 5
w 4 4 3 |
| {3, 4, 6} | | b 4 3 4
w 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
- Th. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press, Cambridge, vols 1 and 2, 1999.
- W. D. Wallis, Combinatorial Designs, Monographs and Textbooks in Pure and Applied Mathematics, 118, (1988)
Freaky Links
Prof. McWorter is a doddering old mathematician, retired from Ohio State University, who occasionally trips over a theorem when he is not hacking away at uncooperative golf balls.
Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in
Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com
Copyright © 1996-2001 Alexander Bogomolny
|
