Vierkant van Room

Een vierkant van Room of Room-vierkant van zijde is een vierkante tabel met rijen en kolommen, waarin de inhoud van elke cel gekozen is uit een verzameling van symbolen, zodanig dat:

  1. elke cel ofwel leeg is ofwel een ongeordend paar van twee verschillende symbolen uit bevat;
  2. elk symbool uit precies eenmaal voorkomt in elke rij en in elke kolom van de tabel;
  3. elk ongeordend paar van twee verschillende symbolen uit precies eenmaal voorkomt in de tabel.

Gewoonlijk wordt als de verzameling de getallen van 0 tot en met gebruikt. Dergelijke vierkanten vinden toepassing in experimenteel ontwerpen.

Geschiedenis

bewerken

Room-vierkanten zijn genoemd naar de wiskundige Thomas Gerald Room, die ze in 1955 in een kort artikel onder de aandacht bracht. Maar ze waren echter reeds in 1897 ingevoerd door Howell, in het kader van de constructie van bridgetoernooien. Ze worden dan ook Howell-rotaties genoemd.[1] In deze context zijn er   teams die elk eenmaal tegen elk ander team spelen. In elke ronde speelt elk team een wedstrijd. Elk team speelt eenmaal op elk speelbord. De kolommen in de tabel stellen de speelborden voor en de rijen de verschillende spelrondes. De getallen in de cellen stellen de teams voor die tegen elkaar uitkomen aan een bepaald speelbord in een bepaalde spelronde.

Voorbeeld

bewerken

Dit is een voorbeeld van een 7-bij-7-Room-vierkant met als symbolen de cijfers 0 tot en met 7:

0,7 1,5 4,6 2,3
3,4 1,7 2,6 0,5
1,6 4,5 2,7 0,3
0,2 5,6 3,7 1,4
2,5 1,3 0,6 4,7
3,6 2,4 0,1 5,7
0,4 3,5 1,2 6,7

Eigenschappen

bewerken
  • Een Room-vierkant blijft een Room-vierkant onder rij- of kolompermutaties.
  • Een Room-vierkant blijft een Room-vierkant onder een permutatie van de symbolen.
  • De getransponeerde matrix van een Room-vierkant (beschouwd als een matrix) is ook een Room-vierkant.
  • Er bestaan geen Room-vierkanten met een even aantal kolommen of rijen.
  • Er bestaan ook geen Room-vierkanten met zijde 3 of 5.
  • Als   en   oneven getallen zijn, met   kleiner dan of gelijk aan   en er bestaat een Room-vierkant met zijde   dan bestaat er ook een Room-vierkant met zijde  
  • Er bestaat wel een Room-vierkant met zijde   voor elk oneven getal   groter dan 5. Dit werd in 1973 bewezen door W.D. Wallis. Wallis had in 1972 reeds aangetoond dat er een Room-vierkant met zijde   bestaat voor elke oneven   behalve 3,5 en mogelijk 257.[2] Op de 4e Southeastern Conference on Combinatorics in 1973 bracht Wallis dan het bewijs aan dat er wel degelijk een Room-vierkant van zijde 257 bestaat.[1][3]

Gestandaardiseerd Room-vierkant

bewerken

Een Room-vierkant met als symboolverzameling   is gestandaardiseerd met betrekking tot 0 wanneer de cel   het ongeordende paar   bevat. Men kan elk Room-vierkant in gestandaardiseerde vorm brengen door rijen en kolommen te verwisselen.

Aan een gestandaardiseerd Room-vierkant van zijde   kan men een vierkante matrix   koppelen van dezelfde grootte, waarbij:

  als cel   niet leeg is,
  als cel   leeg is.

Scheef Room-vierkant

bewerken

Een gestandaardiseerd Room-vierkant is scheef wanneer voor de gekoppelde matrix   geldt:

 

waarin   de getransponeerde matrix is,   de eenheidsmatrix en   de vierkante matrix gevuld met enen; beied met zijde  

Dit betekent dat een Room-vierkant scheef is wanneer de diagonale cellen in volgorde   zijn en, als   verschilt van   exact een van de cellen   en   leeg is.

Het was anno 1974 voor een eindig aantal oneven getallen, waaronder 9 en 39, nog niet bekend of er een scheef Room-vierkant met die zijde bestaat.[1] D.R. Stinson kon uiteindelijk in 1981 bewijzen dat scheve Room-vierkanten bestaan voor elke oneven zijde groter dan 5.[4]