PRIZE PUZZLE FOR FEBRUARY 2007

The ALL-Play-ALL Puzzle and Program

Imagine that you are an organiser of a chess club that has ten players who have entered an all-play-all tournament. There are nine rounds in which every player plays all other players once. Each round must be played so that all players are playing their games at the same time -- a player is not allowed to play more than one game in a round. There will be five games taking place in each round. (Instead of chess, consider the competitors are football teams in a league; the problem is the same provided its an all-play-all competition and all the teams must play each round on the same day against one of their opponent teams.)

If you can work out a set of rounds that satisfies these conditions then you have nearly solved the problem. The problem, however, is set in a different way that may be of interest. Let us designate the players or teams with the letters A,B,C,D,E,F,G,H,I,J. This diagram is a ten by ten matrix with the zeros fixed down the main diagonal. An equivalent problem to the all-play-all problem is to fill in this matrix with the numbers 1 to 9 in each column and each row, keeping the matrix symmetric.

The numbers 1 to 9 are the round numbers. So the finished matrix enables the games organiser to say who plays whom in each round by finding the round number and looking up the column and row letter for that round. As an example, the diagram shows player C playing F in round 5. The matrix must remain symmetrical because if competitor C plays F then it followed logically that F must be playing C which mirrors the C plays F entry. The zeros in the diagonal are not used because they would otherwise represent each player playing him/her self.

A computer program accompanies this problem which makes sure you stick to the rules. It is a small program that can be downloaded and deleted when you have finished with it. It is run either at the Run command (after pressing Start in Windows) or at a DOS prompt in Windows. When you have completed all the entries a secret code word is revealed to show you have done it.

Click this link ALL-ALL.EXE to download the program. The program has been checked for viruses. It is run either with the Windows Run command or at a DOS prompt. It does not require any installation procedure and may be deleted afterwards. If you prefer, you can fill in the matrix manually (using a printout of this page) without downloading the program but it will be much easier to use the computer program I have written.

 

 

 

ANSWER

There are many answers to this problem. Although there is a pattern to the answer shown, it is not obvious exactly how to allocate a number to each square which is why I thought it would make a problem, though not too difficult. And yet, this is a problem that must arise in practice in various sports and games. If you try to allocate players with random opponents in the first few rounds you will often find that there are no possible pairings for the last round: it has to be done systematically.

Congratulations to Clem Robertson and John Stafford who did the puzzle.

[home] [back]