in collaboration with

September 24, 1997

Revised November 9, 1997

The Complementary Perfect-N Concept |
||
---|---|---|

Start with an ordinary everyday Perfect-N chart, such as this P 13-3 (1). |
Form another Perfect-N chart by using the mirror image (complement) of the first. |
Combine them to form a new chart, this time a "Complementary Perfect-N" chart, such as this C-P 13-3 (2). |

Complementary Perfect N Racing charts are a high precision method for awarding top place trophies and for selecting representatives to district or council races.

An N-X racing chart is a 2-dimensional array with X columns where

1. Every element of the array is in the set {1, 2, 3, ... N}, and

2. No element appears more than once in the same row of the array.

Familiarly, an N-X racing chart is a set of lane assignments for N cars on a track with X lanes.

Here is a simple 3-2 racing chart:

Ln 1 Ln 2 ===== ===== Heat 1 1 2 Heat 2 2 3

Note that there are 2 (i.e. X) columns, that each element of the array is from 1 to 3 (i.e. 1 to N), and that no element appears more than once in each row.

This is a racing chart, but it is probably not a very good one, since it would be difficult to draw any useful conclusions from it.

For an N-X racing chart, let n_{x}be the number of times element n appears in column x, and let n_{m}be the number of times elements n and m appear in the same row.

An N-X racing chart is said be Perfect N-X (Y) if:

1. n_{m}is equal to Y for all n, m from 1 to N, n not equal to m, and

2. n_{x}is the same value for all n from 1 to N, x from 1 to X.

Familiarly, this says that:

- Every car races every other car Y times
- Every car races the same number of times in each lane

The chart above is not Perfect N, but by adding a single race it becomes so.

Ln 1 Ln 2 ===== ===== Heat 1 1 2 Heat 2 2 3 Heat 3 3 1

In this chart, N = 3, X = 2, Y = 1, so this chart is Perfect 3-2$nbsp;(1). Note that each car races 1 time in each lane.

Some conclusions about relative car speed might be drawn from racing with this chart, unless the lanes are so inequitable that "the fast lane always wins." The result with this chart, however, is that even with poor tracks, the track usually does not determine the overall winners, but ties are produced.

A generator G for an N-X racing chart is a vector of X-1 elements, (gThe above definition is used in subsequent text. It is equivalent to the following recursive definition:_{1}, g_{2}, ...,g_{X-1}) such that g_{i}+ g_{i+1}+ ... + g_{j}is not equal to 0 modulo N for all i, j from 1 to X-1, i <= j. The element in the generated chart section in row i, column 1 is i. The element in the generated chart section in row i, column j, for j > 1, is (i + g_{1}+ ... + g_{j-1}) modulo N.

A generator G for an N-X racing chart is a vector of X-1 elements, (g_{1}, g_{2}, ...,g_{X-1}) such that g_{i}+ g_{i+1}+ ... + g_{j}is not equal to 0 modulo N for all i, j from 1 to X-1, i <= j.

If C_{i,j}is the element in the generated chart section in row i, column j then

1. C_{i,j}= i, and

2. C_{i,j+1}= C_{i,j}+ g_{j}modulo N for j < X

For convenience in this definition, we will write Car 0 as "N", not "0". They are equivalent, modulo N, but most people number things beginning with "1", not "0".

A generator is used as a difference vector to generate a racing chart, or a section of a racing chart. Consider the generator (1,2) for 6 Cars on a 3 Lane track. Start with Car 1 in Lane 1 and use generator values additively to determine the Cars in Lanes 2 and 3.

This gives the following partial chart:

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 4

As an abreviated way to produce the rest of the heats, just add 1 to each Car number from the previous heat until every Car has raced in Lane 1.

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 4 Heat 2 2 3 5 Heat 3 3 4 6 Heat 4 4 5 1 Heat 5 5 6 2 Heat 6 6 1 3

The condition that no sequence of g_{i}'s add up to 0
modulo N ensures that no Car will occupy two lanes in the same race.

Note that the 6-3 racing chart generated by (1,2) is not Perfect-N. For example, Car 1 races Car 4 twice, but races each of the other Cars only once. This violates Perfect-N definition.

But use the same generator to build a 7-3 racing chart:

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 4 Heat 2 2 3 5 Heat 3 3 4 6 Heat 4 4 5 7 Heat 5 5 6 1 Heat 6 6 7 2 Heat 7 7 1 3

And you happen to get a Perfect 7-3 (1) chart.

Multiple generators can be used to generate larger racing charts. For example, here is a Perfect 13-3 (1) chart generated by (1,3) and (2,5).

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 5 Heat 2 2 3 6 Heat 3 3 4 7 Heat 4 4 5 8 Heat 5 5 6 9 Heat 6 6 7 10 Heat 7 7 8 11 Heat 8 8 9 12 Heat 9 9 10 13 Heat 10 10 11 1 Heat 11 11 12 2 Heat 12 12 13 3 Heat 13 13 1 4 Heat 14 1 3 8 Heat 15 2 4 9 Heat 16 3 5 10 Heat 17 4 6 11 Heat 18 5 7 12 Heat 19 6 8 13 Heat 20 7 9 1 Heat 21 8 10 2 Heat 22 9 11 3 Heat 23 10 12 4 Heat 24 11 13 5 Heat 25 12 1 6 Heat 26 13 2 7

Let G be an N-X racing chart generated by (g_{1}, ... , g_{X-1}). Then the inverse of G, denoted -G, is the N-X racing chart generated by (-g_{1}, ... , -g_{X-1}), where -g_{i}is computed modulo N.

More generally, let G be an N-X racing chart generated by G_{i}= (g_{i,1}, ... , g_{i,X-1}), for i=1 to H. Then the inverse of G is the N-X racing chart generated by -G_{i}= (-g_{i,1}, ... , -g_{i,X-1}), for i=1 to H, where -g_{i,k}is computed modulo N.

The inverse of the 6-3 racing chart generated earlier by (1,2) is the chart generated by (-1, -2) = (5,4), which is as follows:

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 6 4 Heat 2 2 1 5 Heat 3 3 2 6 Heat 4 4 3 1 Heat 5 5 4 2 Heat 6 6 5 3

Suppose an N-X racing chart G generated by (g_{1}, ... , g_{X-1}) is Perfect N-X. Then the chart -G generated by (-g_{1}, ... , -g_{X-1}) is also Perfect N-X.

More generally, suppose an N-X racing chart G is generated by G_{i}= (g_{i,1}, ... , g_{i,X-1}), for i=1 to H, is Perfect N-X. Then the chart -G generated by -G_{i}= (-g_{i,1}, ... , -g_{i,X-1}), for i=1 to H, is also Perfect N-X.

Proof:

Note that renumbering the elements of a Perfect N-X chart results in a Perfect N-X chart. Note also that reordering the rows of a Perfect N-X chart results in Perfect N-X chart.

Use the one-to-one correspondence f(n) = (N + 2 - n) modulo N to reorder the rows of each chart section G_{i}. Call the new chart sections G_{i}^{'}. The element x in row j, column k of G_{i}^{'}is given by:

x = ( (N + 2 - j) + g_{i,1}+ ... + g_{i,k-1}) modulo N

For chart section -G_{i}(not reordered), the element y in row j, column k is:

y = ( j + (-g_{i,1}) + ... + (-g_{i,k-1}) ) modulo N

Adding the two equations gives...

x + y = (N + 2) modulo N

which implies that...

y = (N + 2 - x) modulo N

In other words, -G_{i}is simply a renumbering of G_{i}^{'}, and G_{i}^{'}is simply a reordering of G_{i}. Since this is true for all G_{i}, i=1 to H, the chart generated by -G_{i}, i=1 to H, must also be Perfect N-X.

As an example, consider the Perfect 3-3 chart generated by (1,1).

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 3 Heat 2 2 3 1 Heat 3 3 1 2

Now, reorder the rows using the function f(x) = N + 2 - x.

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 3 Heat 2 3 1 2 Heat 3 2 3 1

Finally, renumber the elements using the same function.

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 3 2 Heat 2 2 1 3 Heat 3 3 2 1The result is the chart generated by (-1,-1) = (2,2). Clearly, this inverse chart is also Perfect 3-3.

A union of Perfect N-X racing charts is Perfect N-X.

Proof:

Let C_{1}and C_{2}be Perfect N-X racing charts. Suppose that C_{1}has R_{1}races per lane for each car, and that C_{2}has R_{2}races per lane for each car. Then C_{1}union C_{2}has R_{1}+ R_{2}races per lane for each car, which satisfies the first half of Perfect N-X.

Suppose C_{1}has Y_{1}head to head races for each pair of cars, and C_{2}has Y_{2}head to head races for each pair of cars. Then C_{1}union C_{2}has Y_{1}+ Y_{2}head to head races for each pair of cars, which satisfies the second half of Perfect N-X.

As an example, consider the Perfect 4-3 chart generated by (1,1), and the Perfect 4-3 chart generated by (1,2).

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 3 Heat 2 2 3 4 Heat 3 3 4 1 Heat 4 4 1 2 Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 4 Heat 2 2 3 1 Heat 3 3 4 2 Heat 4 4 1 3The union is this chart:

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 3 Heat 2 2 3 4 Heat 3 3 4 1 Heat 4 4 1 2 Heat 5 1 2 4 Heat 6 2 3 1 Heat 7 3 4 2 Heat 8 4 1 3This chart is also Perfect 4-3.

An N-X racing chart is said be Complementary if the number of times elements n and m appear in the same row in columns x and y, respectively, equals the number of times elements n and m appear in the same row in columns y and x, respectively, for all n, m from 1 to N and x, y from 1 to X.

Familiarly, this says that if two cars are in the same race, there must be a corresponding race in the racing chart where the two cars reverse lanes.

Suppose an N-X racing chart is generated by G = (g_{1}, ... , g_{X-1}). Let -G = (-g_{1}, ... , -g_{X-1}) where -g_{k}is computed modulo N. Then the chart generated by G and -G is Complementary.

Proof:

Suppose that in the chart generated by G, elements n and m appear in columns u and v, respectively, in the same row, u < v. Then...Consider the 9-3 chart generated by (1,2).

n + g_{u}+ ... + g_{v-1}= m modulo N

This implies that...

m - g_{u}- ... - g_{v-1}= n modulo N

or...

m + (-g_{u}) + ... + (-g_{v-1}) = n modulo N

That is, in the chart generated by -G, elements m and n appear in columns u and v, respectively, in the same row.

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 4 Heat 2 2 3 5 Heat 3 3 4 6 Heat 4 4 5 7 Heat 5 5 6 8 Heat 6 6 7 9 Heat 7 7 8 1 Heat 8 8 9 2 Heat 9 9 1 3

Its inverse is this chart:

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 9 2 Heat 2 2 1 3 Heat 3 3 2 4 Heat 4 4 3 5 Heat 5 5 4 6 Heat 6 6 5 7 Heat 7 7 6 8 Heat 8 8 7 9 Heat 9 9 8 1The union of the two charts meets the lane-reversal criteria, that is, the union is Complementary.

A union of Complementary N-X racing charts is Complementary.

Proof:

Let C_{1}and C_{2}be Complementary N-X racing charts. Suppose that in the chart C_{1}union C_{2}, elements n and m appear in columns u and v, respectively, in the same row, u < v. This row must belong either to C_{1}or C_{2}. Without loss of generality, assume it belongs to C_{1}. Because C_{1}is Complementary, a corresponding row must exist in C_{1}such that elements n and m appear in columns v and u, respectively. C_{1}union C_{2}also contains this row and therefore is Complementary.

Here are two 4-3 charts, each of which is itself Complementary.

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 4 Heat 2 3 4 2 Heat 3 2 1 3 Heat 4 4 3 1

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 3 Heat 2 4 3 2 Heat 3 2 1 4 Heat 4 3 4 1Clearly, their union is also Complementary.

Suppose a Perfect N-X racing chart has generators G_{i}= (g_{i,1}, ... g_{i,X-1}), for i=1 to H. Let -G_{i}= (-g_{i,1}, ... -g_{i,X-1}) where -g_{i,j}is computed modulo N. Then the chart whose generators are G_{i}union -G_{i}, i=1 to H, is Perfect N-X and Complementary.

Proof:

By Lemma 1, the chart generated by the union of -G_{i}, i=1 to H, is Perfect N-X. By Lemma 2, then, the union of G_{i}, i=1 to H, and -G_{i}, i=1 to H, is Perfect N-X.

For each i, the chart generated by G_{i}and -G_{i}is Complementary by Lemma 3. The union of these for all i is therefore Complementary by Lemma 4.

Perfect N-X racing charts are very accurate at identifying the fastest cars. However, if a pair of cars races an odd number times, or if they race an even number of times without satisfying the lane-reversal criteria, it can contribute to a loss of accuracy, because one of the cars may have an edge in lane assignments.

This theorem provides a method for transforming a Perfect N-X racing chart into a Complementary Perfect N-X racing chart, that is, one that satisfies the lane-reversal criteria. The cost of the transformation is that the number of heats is doubled.

Suppose there exist N, X, and Y for which:

1. There exists a Perfect N-X (Y) racing chart,and

2. Y is even.

Then there exists a racing chart which is Perfect N-X (Y) and Complementary.

This conjecture stems from examples such as the following Perfect 4-3 (2) chart:

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 3 Heat 2 2 3 4 Heat 3 3 4 1 Heat 4 4 1 2

This chart has is generated by (1,1). It is Perfect N-X (Y) with Y even. But it is not Complementary.

This chart, on the other hand, is Perfect 4-3 (2) and Complementary.

Ln 1 Ln 2 Ln 3 ===== ===== ===== Heat 1 1 2 4 Heat 2 3 4 2 Heat 3 2 1 3 Heat 4 4 3 1

However, it is not generate-able in the usual manner.

Back to "Mathematics of Perfect-N

Last changed 11/12/97

Technical Changes for HTML 3.2 Conformance 12/26/97

Table Formatting: 12/13/98

Copyright 1997 © by Stan Pope, Cory Young. All rights reserved.