The "sphinx" polyiamond reptile. Four copies of the sphinx can be put together as shown to make a larger sphinx.

In the geometry of tessellations, a shape that can be dissected into smaller copies of the same shape is called a reptile or rep-tile. Solomon W. Golombcoined the term for self-replicating tilings. The shape is labelled as rep-n if the dissection uses n copies. Such a shape necessarily forms the prototile for a tiling of the plane, in many cases an aperiodic tiling.

A selection of reptiles, including the sphinx, the fish, and the 5-triangle

A shape that tiles itself using different sizes is called an irregular rep-tile or irreptile. If the tiling uses n copies, the shape is said to be irrep-n. If all these sub-tiles are of different sizes then the tiling is additionally described as perfect. A shape that is rep-n or irrep-n is trivially also irrep-(kn − k + n) for anyk > 1, by replacing the smallest tile in the rep-n dissection by n even smaller tiles. The order of a shape, whether using rep-tiles or irrep-tiles is the smallest possible number of tiles which will suffice.

[edit]Examples

Defining an aperiodic tiling (the pinwheel tiling) by repeatedly dissecting and inflating a rep-tile.

Every square, rectangle, parallelogram, rhombus, or triangle is rep-4. The "sphinx" hexiamond (illustrated) is also rep-4 and is the only known self-replicating pentagon. The Gosper island is rep-7. The Koch snowflake is irrep-7: six small snowflakes of the same size, together with another snowflake with three times the area of the smaller ones, can combine to form a single larger snowflake.

A right triangle with side lengths in the ratio 1:2 is rep-5, and its rep-5 dissection forms the basis of the aperiodic pinwheel tiling. By Pythagoras' theorem, the hypotenuse, or sloping side of the rep-5 triangle, has a length of √5.

The international standard ISO 216 defines sizes of paper sheets using the Lichtenberg ratio, in which the long side of a rectangular sheet of paper is the square root of two times the short side of the paper. Rectangles in this shape are rep-2. A rectangle is rep-n if its aspect ratio is √n:1. Anisosceles right triangle is also rep-2.

[edit]Rep-tiles as Fractals

Rep-tiles can be used to create fractals, or shapes that are self-similar at smaller and smaller scales. Rep-tiles that are fully subdivided create simple fractals: for example, an equilateral triangle fully divided into four copies of itself, each of which is fully divided into four copies, and so on. However, more complex fractals can be created by discarding sub-copies at each stage of the subdivision.

An equilateral triangle dividing into three copies at smaller and smaller scales to create a Sierpinski carpet.

Displaying a 7 × 7 Latin square, thisstained glass window honors Ronald Fisher, whose Design of Experiments discussed Latin squares. Fisher's student, A. W. F. Edwards, designed this window for Caius College, Cambridge.

In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Here is an example:

The name "Latin square" was inspired by mathematical papers by Leonhard Euler, who used Latin characters as symbols.^{[citation needed]} Other symbols can be used instead of Latin letters: in the above example, the alphabetic sequence A, B, C can be replaced by the integer sequence 1, 2, 3.

[edit]Reduced form

A Latin square is said to be reduced (also, normalized or in standard form) if both its first row and its first column are in their natural order. For example, the above Latin square is not reduced because its first column is A, C, B rather than A, B, C.

We can make any Latin square reduced by permuting (reordering) the rows and columns. Here switching the above matrix's second and third rows yields

which is reduced: Both its first row and its first column are alphabetically ordered A, B, C.

[edit]Properties

[edit]Orthogonal array representation

If each entry of an n × n Latin square is written as a triple (r,c,s), where r is the row, c is the column, and s is the symbol, we obtain a set of n² triples called the orthogonal array representation of the square. For example, the orthogonal array representation of the first Latin square displayed above is:

{ (1,1,1),(1,2,2),(1,3,3),(2,1,2),(2,2,3),(2,3,1),(3,1,3),(3,2,1),(3,3,2) },

where for example the triple (2,3,1) means that in row 2 and column 3 there is the symbol 1. The definition of a Latin square can be written in terms of orthogonal arrays:

• A Latin square is the set of all triples (r,c,s), where 1 ≤ r, c, s ≤ n, such that all ordered pairs (r,c) are distinct, all ordered pairs (r,s) are distinct, and all ordered pairs (c,s) are distinct.

For any Latin square, there are n² triples since choosing any two uniquely determines the third. (Otherwise, an ordered pair would appear more than once in the Latin square.)

The orthogonal array representation shows that rows, columns and symbols play rather similar roles, as will be made clear below.

[edit]Equivalence classes of Latin squares

Many operations on a Latin square produce another Latin square (for example, turning it upside down).

If we permute the rows, permute the columns, and permute the names of the symbols of a Latin square, we obtain a new Latin square said to be isotopic to the first. Isotopism is an equivalence relation, so the set of all Latin squares is divided into subsets, called isotopy classes, such that two squares in the same class are isotopic and two squares in different classes are not isotopic.

Another type of operation is easiest to explain using the orthogonal array representation of the Latin square. If we systematically and consistently reorder the three items in each triple, another orthogonal array (and, thus, another Latin square) is obtained. For example, we can replace each triple (r,c,s) by (c,r,s) which corresponds to transposing the square (reflecting about its main diagonal), or we could replace each triple (r,c,s) by (c,s,r), which is a more complicated operation. Altogether there are 6 possibilities including "do nothing", giving us 6 Latin squares called the conjugates (also parastrophes) of the original square.

Finally, we can combine these two equivalence operations: two Latin squares are said to be paratopic, also main class isotopic, if one of them is isotopic to a conjugate of the other. This is again an equivalence relation, with the equivalence classes called main classes, species, or paratopy classes. Each main class contains up to 6 isotopy classes.

[edit]Number

There is no known easily computable formula for the number L(n) of n × n Latin squares with symbols 1,2,...,n. The most accurate upper and lower bounds known for large n are far apart. One classic result is

(this given by van Lint and Wilson).

Here we will give all the known exact values. It can be seen that the numbers grow exceedingly quickly. For each n, the number of Latin squares altogether (sequence A002860 in OEIS) is n! (n-1)! times the number of reduced Latin squares (sequence A000315 in OEIS).

For each n, each isotopy class (sequence A040082 in OEIS) contains up to (n!)³ Latin squares (the exact number varies), while each main class (sequence A003090 in OEIS) contains either 1, 2, 3 or 6 isotopy classes.

[edit]Examples

We give one example of a Latin square from each main class up to order 5.

They present, respectively, the multiplication tables of the following groups:

The thirty-six officers problem is a mathematical puzzle proposed by Leonhard Euler in 1782.^[1][2]

The problem asks if it is possible to arrange 6 regiments consisting of 6 officers each of different ranks in a 6 × 6 square so that no rank or regiment will be repeated in any row or column. Such an arrangement would form a Graeco-Latin square. Euler correctly conjectured there was no solution to this problem, and Gaston Tarry proved this in 1901;^[3][4] but the problem has led to important work in combinatorics.^[5]

Besides the 6 by 6 case the only other case where the equivalent problem has no solution is the 2 by 2 case, i.e. when there are 4 officers.

[edit]References

Victor Klee in 1980

Victor L. Klee, Jr. (1925, San Francisco – August 17, 2007, Lakewood, Ohio) was a mathematician specialising in convex sets, functional analysis,analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of Washington in Seattle.

Born in San Francisco, Vic Klee earned his B.A. degree in 1945 with high honors from Pomona College, majoring in mathematics and chemistry. He did his graduate studies, including a thesis on Convex Sets in Linear Spaces, and received his PhD in mathematics from the University of Virginia in 1949. After teaching several years at the University of Virginia, he moved in 1953 to the University of Washington in Seattle, Washington, where he was a faculty member for 54 years.^[1] Klee wrote more than 240 research papers. He proposed Klee's measure problem and the Art gallery theorem, and Kleetopes are also named after him. Klee served as president of the Mathematical Association of America from 1971 to 1973.^[1]

[edit]Notes

[edit]Further reading

• Grünbaum, Branko; Robert R. Phelps, Peter L. Renz, Kenneth A. Ross (November 2007). "Remembering Vic Klee" (PDF). Maa Focus (Washington, DC: Mathematical Association of America) 27 (8): 20–22. ISSN 0731-2040. Retrieved 2009-05-22. Short biography, and reminiscences of colleagues.
• Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved. Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin). New York-London: Academic Press. pp. 159–175. MR 332165.

The Reuleaux triangle is a constant width curve based on an equilateral triangle. All points on a side are equidistant from the opposite vertex.

A Reuleaux triangle is the simplest and best known Reuleaux polygon. It is a curve of constant width, meaning that the separation of two parallel lines tangent to the curve is independent of their orientation. Because all diameters are the same, the Reuleaux triangle is one answer to the question "Other than a circle, what shape can a manhole cover be made so that it cannot fall down through the hole?" The term derives from Franz Reuleaux, a 19th-century German engineer who did pioneering work on ways that machines translate one type of motion into another, although the concept was known before his time.

[edit]Construction

To construct a Reuleaux triangle

With a compass, sweep an arc sufficient to enclose the desired figure. With radius unchanged, sweep a sufficient arc centred at a point on the first arc to intersect that arc. With the same radius and the centre at that intersection sweep a third arc to intersect the other arcs. The result is a curve of constant width.

Equivalently, given an equilateral triangle T of side length s, take the boundary of the intersection of the disks with radius s centered at the vertices of T.

By the Blaschke–Lebesgue theorem, the Reuleaux triangle has the least area of any curve of given constant width. This area is , where s is the constant width. The existence of Reuleaux polygons shows that diameter measurements alone cannot verify that an object has a circular cross-section.

The area of Reuleaux triangle is smaller than that of the disk of the same width (i.e. diameter); the area of such a disk is .

[edit]Reuleaux polygons

Reuleaux polygons

The Reuleaux triangle can be generalized to regular polygons with an odd number of sides, yielding a Reuleaux polygon. The most commonly used of these is the Reuleaux heptagon, which is the shape of several coins:

• Botswana pula coins in the denominations of 2 pula, 1 pula, 25 thebe and 5 thebe.
• Cypriot 50-cent coin, from 1991 until Cyprus joined the Euro in 2008.
• Jordanian quarter-dinar and half-dinar coins.
• Mauritian 10-rupee coin.
• British 20-pence and 50-pence coins.
• Canadian Loonie dollar coin. (eleven sides)

The constant width of such coins allows their use in coin-operated machines.

[edit]Other uses

The Reuleaux triangle rotating inside a square

• The rotor of the Wankel engine is easily mistaken for a Reuleaux triangle but its curved sides are somewhat flatter than those of a Reuleaux triangle and so it does not have constant width.^[1]
• The Watts Brothers Tool Works square drill bit has the shape of a Reuleaux triangle and can, if mounted in a special chuck which allows for the bit not having a fixed centre of rotation, drill a hole that is nearly square;^[2] the corners of the square are slightly rounded, as can be seen by tracing any vertex in this figure, and the drill bit covers 0.9877... of the area of the square.^[3] The Harry Watt square is often used inmortising^[4][5] Other Reuleaux polygons are used to drill pentagonal, hexagonal, and octagonal holes.
• A Reuleaux triangle (along with all other curves of constant width) can roll but makes a poor wheel because it does not roll about a fixed center of rotation. An object on top of rollers with cross-sections that were Reuleaux triangles would roll smoothly and flatly, but an axle attached to Reuleaux triangle wheels would bounce up and down three times per revolution. This concept was used in a science fiction short story by Poul Anderson titled "The Three-Cornered Wheel."^[6]
• Several pencils are manufactured in this shape, rather than the more traditional round or hexagonal barrels.^[7] They are usually promoted as being more comfortable or encouraging proper grip, as well as being less likely to roll off tables (since the center of gravity moves up and down more than a rolling hexagon).
• The shape is used for signage for the National Trails System administered by the United States National Park Service,^[8] as well as the logo ofColorado School of Mines and the Connecticut Collegiate Mathematics Competition.
• Valve covers used in the Mission Bay Project of San Francisco to differentiate reclaimed water from potable water are in the shape of a Reuleaux triangle.^[9]

An equidiagonal kite that maximizes the ratio of perimeter to diameter, inscribed in a Reuleaux triangle

• Among all quadrilaterals, the shape that has the greatest ratio of its perimeter to its diameter is an equidiagonal kite that can be inscribed into a Reuleaux triangle.^[10]
• Many guitar picks employ the Reuleaux triangle, as its unique shape combines a sharp point to provide strong articulation, with a wide tip to produce a warm timbre. Many players find the shape ergonomic, since it naturally tends to point in the proper direction. Its three equal tips also prevent wear and extend lifespan, as compared to the single tip of a pick shaped like an isosceles triangle. ^[11]

[edit]Three-dimensional version

The intersection of four spheres of radius s centered at the vertices of a regular tetrahedron with side length s is called the Reuleaux tetrahedron, but is not a surface of constant width.^[12] It can, however, be made into a surface of constant width, called Meissner's tetrahedron, by replacing its edge arcs by curved surface patches. Alternatively, the surface of revolution of a Reuleaux triangle through one of its symmetry axes forms a surface of constant width, with minimum volume among all known surfaces of revolution of given constant width (Campi, Colesanti & Gronchi (1996)).

[edit]See also