WSDC 1998: Jerusalem, Israel
Draw: Technical Notes

The pairings were created by a two-step process. Step 1 was creating a pairing table; this is equivalent to creating a pairing function f: N₂₆ * N₈ -> N₂₆ such that the following restrictions hold:

1. f(p, k) = q implies that f(q, k) = p.

2. f(p, n) as n goes from 1 to 8 is a one-to-one function.

3. f(p, k) != p.

4. f(x, k) as x goes from 1 to 26 is a one-to-one (and therefore onto) function.

A further restriction was that of dividing the groups into schools on different days. This can be stated as follows:
Given z₁ = 3, z₂ = 6, z₃ = 8, there must be a division of N₂₆ into 12 = 4 * 3 distinct non-null subsets such that if p is in the (n, k) subset, and:
z_k-1 <= s <= z_k, then f(p, s) is in the same subset.

Step 1 was done by hand. Step 2 was an optimization problem: given a ranking function r from N₂₆ to R, find a permutation s of N₂₆ such that the standard deviation of the following set of values is minimized:

• r(s(f(1, 1))) + r(s(f(1, 2))) + ... + r(s(f(1, 8)))

• r(s(f(2, 1))) + r(s(f(2, 2))) + ... + r(s(f(2, 8)))

• ...

• r(s(f(26, 1))) + r(s(f(26, 2))) + ... + r(s(f(26, 8)))

This was done by computer: permutations were chosen at random and a record was kept of the minimum standard deviation. The result was then translated into real team names. With a 1-5 ranking scale, seeded by the results of the 1997 WSDC (with all new entrants being ranked equally), the standard deviation achieved - after roughly 30,000 random permutations - was approximately 1.802. The highest value was 28, for team 26; the lowest were 22 (team 7) and 23 (team 13).

I have since become interested in the more general optimization problem (any number of teams, any ranking function, picking an optimal pairing function, etc.) which seems to lie in the field of linear programming. I have already discovered at least one iterative algorithm which should be much more efficient; the source code for the original program will soon be available on this page. If you have ideas as to how to solve the general problem, drop me a note.

Haran Pitel

< 1998 Table of Contents