Carré de Room

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Un carré de Room, nommé d'après Thomas Gerald Room, est un tableau carré de n lignes et colonnes sur n + 1 symboles vérifiant les conditions suivantes :

  1. Chaque cellule du tableau est vide ou contient une paire non ordonnée de symboles
  2. Chaque symbole apparaît exactement une fois dans chaque ligne et colonne du tableau
  3. Chaque paire non ordonnée apparaît dans exactement une cellule du tableau.

L'entier n est l'ordre du carré. Voici un exemple de carré de Room d'ordre 7 sur l'ensemble des 8 entiers de 0 à 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

On sait que des carrés de Room existent si et seulement si n est impair, sauf pour 3 et 5.

Histoire[modifier | modifier le code]

Un carré de Room d'ordre 7 a été utilisé par Robert Richard Anstice pour fournir d'autres solutions au problème des écolières de Kirkman au milieu du XIXe siècle, et Robert Anstice a également construit une famille infinie de carrés de Room, mais ses constructions n'ont pas été remarquées[1].

Thomas Gerald Room (en) a réinventé les carrés de Room dans une note publiée en 1955[2], et ils ont été nommés d'après lui. Dans son article original sur le sujet, Room observe que n doit être impair et différent de 3 et 5, mais il n'a pas été démontré que ces conditions sont à la fois nécessaires et suffisantes avant travail de W. D. Wallis en 1974[3],[4].

Applications[modifier | modifier le code]

Salle de tournoi par paires à la fin d'une compétition

Dès avant l'article de Room, les carrés de Room ont été utilisés par les organisateurs de tournois de bridge par paires dans la construction des tournois. Dans cette utilisation, ils sont appelés mouvements de type Howell. Les colonnes du carré représentent des tables, chacune contenant un jeu de cartes qui est joué par chaque paire d'équipes qui se réunissent à cette table. Les lignes du carré représentent les tours du tournoi, et les nombres dans les cellules du carré représentent les équipes qui doivent jouer à la table et au tour représentés par cette cellule.

Archbold et Johnson ont utilisé des carrés de Room pour construire des plans expérimentaux[5].

Il existe des connexions entre les carrés de Room et d'autres objets mathématiques, comme les quasigroupes, les carrés latins, les factorisations de graphes et les lsystèmes triples de Steiner[6]

Notes et références[modifier | modifier le code]

  1. (en) John J. O'Connor et Edmund F. Robertson, « Robert Anstice », dans MacTutor History of Mathematics archive, université de St Andrews (lire en ligne)..
  2. T. G. Room, « A new type of magic square », Mathematical Gazette, vol. 39,‎ , p. 307.
  3. Wallis 1974.
  4. J. W. P. Hirschfeld et G. E. Wall, « Thomas Gerald Room. 10 November 1902–2 April 1986 », Biographical Memoirs of Fellows of the Royal Society, vol. 33,‎ , p. 575–601 (DOI 10.1098/rsbm.1987.0020, JSTOR 769963). Article aussi publié dans « Thomas Gerald Room », Historical Records of Australian Science, vol. 7, no 1,‎ , p. 109–122 (DOI 10.1071/HR9870710109), version abrégée sur le site l'Académie australienne des sciences.
  5. Archbold et Johnson 1958
  6. Wallis, Street et Wallis 1972, p. 33

Bibliographie[modifier | modifier le code]

  • J. W. Archbold et N.L. Johnson, « A construction for Room squares and an application in experimental design », Annals of Mathematical Statistics, vol. 29,‎ , p. 219–225 (DOI 10.1214/aoms/117770671).
  • J. H. Dinitz et D. R. Stinson (éditeurs), Contemporary Design Theory : A Collection of Surveys, John Wiley & Sons, (ISBN 0-471-53141-3), p. 137-204.
  • Walter D. Wallis, « Solution of the Room square existence problem », Journal of Combinatorial Theory, Series A, vol. 17, no 3,‎ , p. 379-383 (lire en ligne, consulté le 12 mai 2020).
  • Walter D. Wallis, Anne Penfold Street et Jennifer Seberry Wallis, Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices, Springer-Verlag, (ISBN 0-387-06035-9), p. 30-121.

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]