![[P13-3(1)]](cpsyn1.gif)
![[P'13-3(1)]](cpsyn2.gif)
![[CP13-3(2)]](cpsyn3.gif)
| 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 nx be the number of times element n appears in column x, and let nm 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. nm is equal to Y for all n, m from 1 to N, n not equal to m, and
2. nx is the same value for all n from 1 to N, x from 1 to X.
Familiarly, this says that:
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, (g1, g2, ...,gX-1) such that gi + gi+1 + ... + gj 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 + g1 + ... + gj-1) modulo N.The above definition is used in subsequent text. It is equivalent to the following recursive definition:
A generator G for an N-X racing chart is a vector of X-1 elements, (g1, g2, ...,gX-1) such that gi + gi+1 + ... + gj is not equal to 0 modulo N for all i, j from 1 to X-1, i <= j.
If Ci,j is the element in the generated chart section in row i, column j then
1. Ci,j = i, and
2. Ci,j+1 = Ci,j + gj 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 gi'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 (g1, ... , gX-1). Then the inverse of G, denoted -G, is the N-X racing chart generated by (-g1, ... , -gX-1), where -gi is computed modulo N.
More generally, let G be an N-X racing chart generated by Gi = (gi,1, ... , gi,X-1), for i=1 to H. Then the inverse of G is the N-X racing chart generated by -Gi = (-gi,1, ... , -gi,X-1), for i=1 to H, where -gi,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 (g1, ... , gX-1) is Perfect N-X. Then the chart -G generated by (-g1, ... , -gX-1) is also Perfect N-X.
More generally, suppose an N-X racing chart G is generated by Gi = (gi,1, ... , gi,X-1), for i=1 to H, is Perfect N-X. Then the chart -G generated by -Gi = (-gi,1, ... , -gi,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 Gi. Call the new chart sections Gi'. The element x in row j, column k of Gi' is given by:
x = ( (N + 2 - j) + gi,1 + ... + gi,k-1 ) modulo N
For chart section -Gi (not reordered), the element y in row j, column k is:
y = ( j + (-gi,1) + ... + (-gi,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, -Gi is simply a renumbering of Gi', and Gi' is simply a reordering of Gi. Since this is true for all Gi, i=1 to H, the chart generated by -Gi, 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 1
The 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 C1 and C2 be Perfect N-X racing charts. Suppose that C1 has R1 races per lane for each car, and that C2 has R2 races per lane for each car. Then C1 union C2 has R1 + R2 races per lane for each car, which satisfies the first half of Perfect N-X.
Suppose C1 has Y1 head to head races for each pair of cars, and C2 has Y2 head to head races for each pair of cars. Then C1 union C2 has Y1 + Y2 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 3
The 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 3
This 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 = (g1, ... , gX-1). Let -G = (-g1, ... , -gX-1) where -gk 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 + gu + ... + gv-1 = m modulo N
This implies that...
m - gu - ... - gv-1 = n modulo N
or...
m + (-gu) + ... + (-gv-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 1
The 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 C1 and C2 be Complementary N-X racing charts. Suppose that in the chart C1 union C2, elements n and m appear in columns u and v, respectively, in the same row, u < v. This row must belong either to C1 or C2. Without loss of generality, assume it belongs to C1. Because C1 is Complementary, a corresponding row must exist in C1 such that elements n and m appear in columns v and u, respectively. C1 union C2 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 1
Clearly, their union is also Complementary.
Suppose a Perfect N-X racing chart has generators Gi = (gi,1, ... gi,X-1), for i=1 to H. Let -Gi = (-gi,1, ... -gi,X-1) where -gi,j is computed modulo N. Then the chart whose generators are Gi union -Gi, i=1 to H, is Perfect N-X and Complementary.
Proof:
By Lemma 1, the chart generated by the union of -Gi, i=1 to H, is Perfect N-X. By Lemma 2, then, the union of Gi, i=1 to H, and -Gi, i=1 to H, is Perfect N-X.
For each i, the chart generated by Gi and -Gi 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.