Dr. Andrew Broad
Tennis
Wooden-Spoon Lists
Explanation of the Theory

A wooden-spoon list is a compact representation of a tournament draw. It takes the form of a list of the players, ordered according to who beats whom in the tournament. Obviously the champion is first in the list. I call it a `wooden-spoon' list because any draw has exactly one `wooden-spoonist', defined as the player at the end of the longest losing chain, and that player has the `ignominy' of being identified as the last player on the list.

A simple example illustrates the theory. Suppose Monica Seles, Iva Majoli, Jelena Dokic and Karina Hab�udov� are the players in a four-player knockout draw. Suppose the results are as follows:

Semi-finals:
	Monica Seles beats Jelena Dokic
	Iva Majoli beats Karina Hab�udov�

Final:
	Monica Seles beats Iva Majoli

Study the following example of an eight-player draw to cement your understanding of wooden-spoon theory:

Quarter-finals:
	Monica Seles beats Iva Majoli
	Daniela Hantuchov� beats Iroda Tulyaganova
	Jelena Dokic beats Vera Zvonar�va
	Maria Sharapova beats Karina Hab�udov�

Semi-finals:
	Monica Seles beats Daniela Hantuchov�
	Maria Sharapova beats Jelena Dokic

Final:
	Monica Seles beats Maria Sharapova

Wooden-spoon list:
	1. Monica Seles
	2. Maria Sharapova
	3. Daniela Hantuchov�
	4. Jelena Dokic
	5. Iva Majoli
	6. Karina Hab�udov�
	7. Iroda Tulyaganova
	8. Vera Zvonar�va

The wooden-spoon list has some neat properties:

• You can calculate whom a player beat or lost to in a particular round by respectively adding or subtracting a binary power (1 for final, 2 for semi-final, 4 for quarter-final, etc.). For example, given just the above wooden-spoon list, you can work out that the player whom Maria beat in the quarter-finals was Karina (because 2+4=6), or that the player Daniela lost to in the semi-finals was Monica (because 3-2=1).
• You can reverse-engineer the whole draw, given just the wooden-spoon list (strictly speaking, you can reverse-engineer a draw which is isomorphic to the actual draw, since the wooden-spoon list does not intrinsically preserve draw-order). The wooden-spoon list is thus a maximally compact representation of a draw.
• Entries in the wooden-spoon list could be tagged with extra information, such as the score by which each player (except the champion) lost the match that she lost, a Boolean flag for each entry to indicate draw-order, and of course extra information about each player such as her status in the draw (seeding, qualifier, wild card, etc.).
• You could even construct an anti-draw, by reversing the wooden-spoon list and then constructing a draw from the reverse wooden-spoon list. Effectively, it's as though the first-round losers went through to a second round to play each other, and so on - the losers playing in the next round instead of the winners. For what it's worth, the wooden-spoon list `predicts' who would lose to whom, culminating in the crowning of the anti-champion! ;-) The anti-draw for the above wooden-spoon list is as follows:

Quarter-finals:
	Iva Majoli loses to Monica Seles
	Iroda Tulyaganova loses to Daniela Hantuchov�
	Vera Zvonar�va loses to Jelena Dokic
	Karina Hab�udov� loses to Maria Sharapova

Anti-semi-finals:
	Iroda Tulyaganova loses to Iva Majoli
	Vera Zvonar�va loses to Karina Hab�udov�

Anti-final:
	Vera Zvonar�va loses to Iroda Tulyaganova

The algorithm for constructing a wooden-spoon list from a given draw is as follows. This is how you assign players in a 128-player draw to positions in the wooden-spoon list:

• 1: the champion;
• 2: the runner-up;
• 3-4: the players who lost to players 1-2 in the semi-finals;
• 5-8: the players who lost to players 1-4 in the quarter-finals;
• 9-16: the players who lost to players 1-8 in the last sixteen;
• 17-32: the players who lost to players 1-16 in the last 32;
• 33-64: the players who lost to players 1-32 in the last 64;
• 65-128: the players who lost to players 1-64 in the first round.