Des articles

15.2 : Carrés latins et Sudokus - Mathématiques


15.2 : Carrés latins et Sudokus - Mathématiques

Ce nombre peut être simplifié à 71 après avoir pris en compte davantage de symétries [18].

Arratia, R., DeSalvo, S. : Approximation de Poisson et de processus indépendant pour les structures combinatoires aléatoires avec un nombre donné de composants, et comportement quasi universel pour les assemblages de bas rang. arXiv préimpression arXiv:1606.04642 (2016)

Arratia, R., DeSalvo, S. : Diviser pour régner probabiliste : une nouvelle méthode de simulation exacte, avec des partitions entières comme exemple. Peigne. Probable. Calcul. 25(3), 324–351 (2016)

Colbourn, C.J. : La complexité de compléter des carrés latins partiels. Appl. discret. Math. 8(1), 25–30 (1984)

Dahl, G. : Matrices de permutation liées au sudoku. Appl. d'algèbre linéaire. 430(8), 2457–2463 (2009)

DeSalvo, S. : Diviser pour régner probabiliste : seconde moitié déterministe. arXiv préimpression arXiv:1411.6698 (2014)

DeSalvo, S. : Améliorations apportées à l'échantillonnage exact de Boltzmann à l'aide de la méthode probabiliste diviser pour régner et de la méthode récursive. arXiv préimpression arXiv:1608.07922 (2016)

Devroye, L. : Génération de variables aléatoires non uniformes. Handb. Oper. Res Manag. Sci. 13, 83–121 (2006)

Diaconis, P., Sturmfels, B., et al. : Algorithmes algébriques pour l'échantillonnage à partir de distributions conditionnelles. Anne. Stat. 26(1), 363–397 (1998)

Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G. : échantillonneurs Boltzmann pour la génération aléatoire de structures combinatoires. Combiner. Probable. Calcul. 13(4–5), 577–625 (2004)

Felgenhauer, B., Jarvis, F. : Mathématiques du sudoku i. Math. Spectre. 39(1), 15–22 (2006)

Flajolet, P., Sedgewick, R. : Combinatoire analytique. Cambridge University Press, Cambridge (2009)

Fontana, R. : Fractions de permutations. une application au sudoku. J. Stat. Planifier. Inférence 141(12), 3697–3704 (2011)

Fontana, R. : Génération de carrés latins aléatoires et de dessins de sudoku. arXiv préimpression arXiv:1305.3697 (2013)

Fontana, R., Rapallo, F., Rogantin, M.P. : bases de Markov pour les grilles de sudoku. Dans : Advanced Statistical Methods for the Analysis of Large Data-Sets, pages 305-315. Springer, (2012)

Godsil, C.D., McKay, B.D. : Dénombrement asymptotique de rectangles latins. J. Comb. Théorie Ser. B 48(1), 19–44 (1990)

Huber, M.L. : Simulation parfaite. Chapman & Hall/CRC Monographies sur les statistiques et la probabilité appliquée. Taylor & amp Francis, (2015)

Jacobson, M.T., Matthews, P. : Génération de carrés latins aléatoires uniformément distribués. J. Comb. Des. 4(6), 405–437 (1996)

Jerrum, M., Sinclair, A., Vigoda, E. : Un algorithme d'approximation en temps polynomial pour le permanent d'une matrice avec des entrées non négatives. J. ACM 51(4), 671-697 (2004). (électronique)

Levin, D.A., Peres, Y., Wilmer, E.L. : Chaînes de Markov et temps de mixage. Société mathématique américaine, Providence (2009)

Newton, P.K., DeSalvo, S.A. : L'entropie de Shannon des matrices de sudoku. Dans : Actes de la Royal Society of London A : Sciences mathématiques, physiques et techniques, page rspa20090522. La Société Royale (2010)

Nijenhuis, A., Wilf, H.S. : Une méthode et deux algorithmes sur la théorie des partitions. J. Comb. Théorie Ser. UNE 18, 219–222 (1975)

Nijenhuis, A., Wilf, H.S. : Algorithmes combinatoires. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-Londres, deuxième édition, 1978. Pour ordinateurs et calculatrices, Computer Science and Applied Mathematics (1978)

Structure aléatoire. Algor. Échantillonnage exact avec chaînes de Markov couplées et applications à la mécanique statistique. 9(1–2), 223–252 (1996)

Ridder, A. : Comptage du nombre de sudoku par simulation d'échantillonnage d'importance (2013)

Russell, E., Jarvis, F. : Mathématiques du sudoku II. Math. Spectre. 39(2), 54–58 (2006)

Sloane, N.J.A. : Encyclopédie en ligne des séquences entières. Publié électroniquement sur http://www.oeis.org/

Stones, D.S. : Les nombreuses formules du nombre de rectangles latins. Électron. J. Comb. 17(1), article 1 46 (2010)

van Lint, J.H., Wilson, R.M. : A Course in Combinatorics, 2e éd. Cambridge University Press, Cambridge (2001)

Von Neumann, J. : Diverses techniques utilisées en rapport avec les chiffres aléatoires. Appl. Maths Ser. 12(36–38), 1 (1951)

Yordzhev, K. : Sur le nombre de paires disjointes de matrices de permutation s. Appl. discret. Math. 161(18), 3072–3079 (2013)

Yordzhev, K. : Permutations aléatoires, matrices de sudoku aléatoires et algorithmes aléatoires. arXiv préimpression arXiv:1312.0192, (2013)


Carrés Latins

J. Dénes , A.D. Keedwell , dans Annals of Discrete Mathematics , 1991

(5) Ensembles complets de carrés latins orthogonaux de colonnes et de plans affines

K. Vedder (1983) a défini deux carrés latins A = [aje] et B = [bje] du même ordre n être colonne orthogonale si, pour chaque couple fixe d'entiers j, k, on a unje = bje pour au plus une valeur de i. Il a donné l'exemple suivant d'un ensemble de quatre carrés latins orthogonaux aux colonnes d'ordre 3 définis sur l'ensemble de symboles <1, 2, 3, 4> :

Un tel ensemble de n carrés d'ordre n−1 basé sur un ensemble de n symboles et avec un des symboles omis de chaque carré de l'ensemble, il a appelé un ensemble complet de carrés latins orthogonaux mutuellement colonnes de type n−1. Il a prouvé le théorème suivant. (Comparer le théorème 1.1 de ce chapitre et son corollaire.)

Un ensemble complet de carrés latins orthogonaux mutuellement colonnes de type n−1 est équivalent à un plan projectif (ou affine) d'ordre n.

Preuve. On désigne les différentes classes parallèles du plan affine par les lettres majuscules A, E, B1, B2, …, Bn-1 comme dans le théorème 1.1 de ce chapitre. Soit les lignes de ces classes parallèles étiquetées comme suit : a1, une2, …, unem sont les droites de la classe A eo,e1, …, en-1 sont les droites de la classe E bj1, bj2, …, bJn sont les droites de la classe Bj. Tout point P(h, i) du plan peut alors être identifié à un ensemble de n+1 nombres (h, i, ℓ1,2, …,n-1) décrivant les n+1 lignes eh, uneje, b1ℓ1, b2ℓ2, …, bn−1ℓn-1 avec laquelle il est incident, un de chacune des n+1 classes parallèles.

On construit un ensemble de carrés latins orthogonaux colonnes A1, UNE2, … UNEm de la manière suivante. Les colonnes du i-ième carré Aje sont définis par les n lignes passant par le point (0, i). Soit bjℓ être l'une de ces lignes et supposons qu'elle contienne les points (1, i1), (2, je2), …, (n−1, jen-1). Alors la j-ième colonne du carré Aje est le vecteur colonne (i1, je2, …, jen-1) T . Puisque chacun des n points sur la ligne bjℓ est incidente avec une autre droite de la classe parallèle A, l'ensemble 1, je2, …, jen-1> est l'ensemble des nombres naturels <1, 2, …, n>. Aussi, puisque deux lignes bjℓ et Bkm de classes parallèles distinctes ont exactement un point en commun qui est le point (0, i) si et seulement si bjℓ et Bkm définir deux colonnes du même carré Aje, chaque carré est latin et les colonnes de carrés distincts concordent au plus sur une ligne. C'est-à-dire que les carrés forment un ensemble complet de carrés latins orthogonaux mutuellement colonnes de type n-1, comme requis.

De la méthode de construction, il est clair que si j≠k alors la j-ème colonne du carré Aje s'accorde exactement à un endroit avec la k-ème colonne de chaque autre carré, tandis que d'un autre côté, les j-ème colonnes de chaque paire de carrés ne s'accordent à aucun endroit. Un ensemble complet de carrés latins orthogonaux à colonnes mutuelles ayant cette propriété sera appelé normalisé. Il est facile de voir que tout ensemble complet peut être ainsi normalisé et ensuite, en inversant la construction décrite ci-dessus, nous complétons la preuve de notre théorème.

Vedder a montré qu'à partir d'un ensemble complet normalisé de carrés latins orthogonaux mutuellement colonnes de type n−1, on peut construire un ensemble de n−1 carrés latins orthogonaux mutuellement colonnes nxn et inversement. Il a appelé un ensemble de ce dernier type un ensemble complet de carrés latins orthogonaux mutuellement colonnes de type n.

Soit A1, UNE2, …, UNEm être un ensemble complet normalisé de carrés latins orthogonaux mutuellement colonnes de type n−1. On forme un nxn carré latin Bj (j = 1, 2, …, n−1) en prenant comme colonnes de Bj, les j-ième colonnes de A1, UNE2, …, UNEm respectivement chacun dirigé par son symbole manquant. Le fait que ces symboles manquants soient tous différents découle de la construction du théorème 5.1. Le fait que chacun des carrés Bj Ce latin découle du fait qu'il n'y a pas deux j-ième colonnes d'accord en aucun endroit. Ainsi, les carrés B1, B2, …, Bn-1 forment un ensemble complet de carrés latins orthogonaux mutuellement colonnes de type n. Cette construction est illustrée pour le cas n = 4 sur la figure 5.1 .

En général, les ensembles complets de carrés latins mutuellement orthogonaux n'ont pas besoin d'être mutuellement orthogonaux aux colonnes (l'ensemble complet de m.o.l.s. qui représente le plan de Hughes d'ordre 9 donné dans la section suivante est un contre-exemple). Cependant, Vedder a montré que les carrés latins orthogonaux qui sont construits par la méthode d'automorphisme de H. B. Mann (voir H. B. Mann (1942) ou page 234 de [DK]) sont nécessairement aussi des colonnes orthogonales. En particulier:

Un ensemble complet de m.o.l.s. basé sur le groupe d'addition d'un champ proche et construit par la méthode d'automorphisme (en utilisant des multiplications) est un ensemble complet de carrés latins orthogonaux mutuellement colonnes de type n.


1 réponse 1

Si $L_n$ est le nombre de carrés latins d'ordre $n$, et $R_n$ est le nombre de carrés latins réduits d'ordre $n$, alors $L_n = n!(n-1) ! R_n.$ Le facteur $n! (n-1)!$ vient en comptant :

Étant donné un carré latin d'ordre $n$, il existe un unique permutation des colonnes pour que la première ligne soit dans l'ordre ($1,2,ldots,n$), après quoi il y a un unique permutation des lignes qui fixe la première ligne pour que la première colonne soit en ordre.

Dans l'autre sens, étant donné un carré latin réduit d'ordre $n$, si on permute les lignes sauf la première et permute les colonnes, on génère $n ! (n-1)!$ distinct Carrés latins d'ordre $n$.

Ainsi, chaque carré latin réduit correspond à $n ! (n-1)!$ (pas nécessairement réduit) carrés latins, et chaque carré latin (pas nécessairement réduit) donne exactement un carré latin réduit.

En tant que tel, le calcul de $L_n$ est effectivement le même que le calcul de $R_n$. Bien qu'il existe de nombreuses formules pour le nombre de carrés latins, elles ne sont efficaces en calcul que jusqu'à $n=11$. Avec la meilleure technique de comptage actuelle (méthode de Sade), à ​​mesure que le matériel s'améliore, nous pourrions voir $L_<12>$ au cours de notre vie.

Autant que je sache, la méthode de Sade est la seule méthode qui a été utilisée pour $n geq 10$.

Pour les commandes $n leq 9$, il est possible de générer des représentants de classe principale pour chaque classe principale, en calculant leur taille de classe principale à l'aide de nauty, dont la somme est égale à $L_n$ (tâche pas facile pour $n=9$ [ Je ne sais pas si quelqu'un l'a réellement fait de cette façon] les représentants peuvent être téléchargés sur le site Web de Brendan McKay pour $n leq 8$).

Il est possible d'utiliser la formule de Doyle pour calculer le nombre de rectangles latins $6$-ligne, qui, pour $7$ colonnes, est égal à $L_7$ (réf.).


Références et lectures complémentaires :

Birken, Marcia et Coon, Anne C. (2008) Découvrir des régularités en mathématiques et en poésie, Amsterdam, Rodopi.

Fishwick, Duncan (1964) « Sur l'origine du carré Rotas-Sator ». La revue théologique de Harvard, vol. 57, non. 1, 1964, p. 39-53. http://docshare02.docshare.tips/files/16340/163404657.pdf

Glaz, Sarah (2012) « Poésie mathématique des motifs ». Actes de la conférence Bridges 2012 http://m.archive.bridgesmathart.org/2012/bridges2012-65.pdf

Coxson, G. E. « Le blog de la poésie avec les mathématiques de JoAnne Growney – Une appréciation », Revue de Mathématiques Humanistes, Volume 2, numéro 2 (juillet 2012), pages 140-150. DOI : 10.5642/ jhummath.201202.12. Disponible sur : https://scholarship.clarremont.edu/jhm/vol2/iss2/12

Hix, H. L. (2000) Nombres rationnels, Truman State University Press

Lajeunesse, Lisa (2019) « Poèmes carrés gréco-latins. » Actes de la conférence Ponts 2019http://archive.bridgesmathart.org/2019/bridges2019-35.pdf

May D. (2020) « Poèmes structurés par les mathématiques ». Dans : Sriraman B. (eds) Manuel des Mathématiques des Arts et des Sciences. Springer, Cham.

Motoyama, Hiroshi (2001) Théories des chakras. Livres New Age, Delhi

Platon, Timée et Critias, tr. Desmond Lee (1965). Penguin Classics, Middlesex


Chercheurs en théorie de la conception combinatoire et dans les domaines de la statistique tels que la conception et l'analyse d'expériences. Le livre peut également intéresser les mathématiciens amateurs intéressés par les carrés magiques, la conception de tournois de jeux et/ou les carrés latins liés aux puzzles Sudoku.

Chapitre 1 : Propriétés élémentaires

  • 1.1 La table de multiplication d'un quasi-groupe
  • 1.2 La table Cayley d'un groupe
  • 1.3 Isotopie
  • 1.4 Conjugaison et paratrophie
  • 1.5 Transversales et cartographies complètes
  • 1.6 Sous-carrés et sous-quasigroupes latins

Chapitre 2 : Types particuliers de carré latin

  • 2.1 Identités quasi-groupes et carrés latins
  • 2.2 Quasigroupes de certains types particuliers et le concept d'associativité généralisée
  • 2.3 Systèmes triples et quasigroupes
  • 2.4 Carrés latins à base de groupes et noyaux de boucles
  • 2.5 Transversales dans les carrés latins groupés
  • 2.6 Carrés latins complets

Chapitre 3 : Carrés latins partiels et transversales partielles

  • 3.1 Rectangles latins et rangées de carrés latins
  • 3.2 Ensembles critiques et puzzles de Sudoku
  • 3.3 Les problèmes de Fuchs
  • 3.4 Carrés latins incomplets et quasigroupes partiels
  • 3.5 Transversales partielles et transversales généralisées

Chapitre 4 : Classification et énumération des carrés et rectangles latins

  • 4.1 Le groupe d'autotopisme d'un quasi-groupe
  • 4.2 Classification des carrés latins
  • 4.3 Historique de la classification et du dénombrement des carrés latins
  • 4.4 Dénombrement des rectangles latins
  • 4.5 Dénombrement des transversales
  • 4.6 Dénombrement des sous-carrés

Chapitre 5 : Le concept d'orthogonalité

  • 5.1 Questions d'existence pour des ensembles incomplets de carrés latins orthogonaux
  • 5.2 Ensembles complets de carrés latins orthogonaux et de plans projectifs
  • 5.3 Ensembles de MOLS de taille maximale et minimale
  • 5.4 Quasigroupes orthogonaux, groupoïdes et systèmes triples
  • 5.5 Carrés et quasigroupes latins auto-orthogonaux et parastrophiques orthogonaux
  • 5.6 Orthogonalité dans d'autres structures liées aux carrés latins

Chapitre 6 : Liens entre les carrés latins et les carrés magiques

  • 6.1 Carrés latins diagonaux (ou magiques)
  • 6.2 Construction de carrés magiques à l'aide de carrés latins orthogonaux
  • 6.3 Résultats supplémentaires sur les carrés magiques
  • 6.4 Les carrés de salle : leur construction et leurs usages

Chapitre 7 : Constructions de carrés latins orthogonaux qui impliquent des réarrangements de lignes et de colonnes


Carrés Latins

Un carré latin d'ordre n est un tableau de n symboles dans lequel chaque symbole apparaît exactement une fois dans chaque ligne et exactement une fois dans chaque colonne. Voir l'interactivité Teddy Town pour quelques exemples de places latines.

Construisez vous-même des carrés latins et voyez combien d'arrangements différents vous pouvez trouver pour chaque valeur de n. Deux carrés latins sont essentiellement les mêmes, le terme mathématique est isomorphe, si l'un peut être transformé en l'autre en renommant les éléments ou en intervertissant les lignes ou les colonnes.

Par exemple, les disques colorés de cette illustration forment un carré latin d'ordre 3. Ce carré latin est isomorphe au carré avec les symboles B, R et G et au carré avec les symboles 1, 2 et 3.

Les carrés latins de tous les ordres $m> 2$ peuvent être construits en utilisant l'arithmétique modulaire comme dans cet exemple pour $m=5$. L'entrée $S_$ dans la ligne $i$ colonne $j$ est donné par $S_=i+j$ (mod $5$), où ceci est défini comme étant le reste lorsque la somme $i+j$ est divisée par $5$.

Par exemple, l'entrée dans la 4ème ligne et la 3ème colonne est donnée par $S_<4,3>=4+3$ (mod $5$) $=7$ (mod $5$) $=2$.

Les mêmes tableaux peuvent être trouvés en cyclant simplement les éléments de sorte que cette méthode devient plus utile lors de la résolution de problèmes impliquant des combinaisons de deux carrés latins.

Deux carrés latins sont dits orthogonaux s'ils peuvent être combinés cellule par cellule de sorte que chaque cellule se compose d'une paire de symboles différente.

Les deux carrés latins d'ordre 3, donnés au paragraphe trois ci-dessus ne sont pas orthogonaux car dans la première ligne et la première colonne la combinaison est B1 et la même combinaison se produit dans la deuxième ligne et la deuxième colonne. Cependant les carrés latins à droite sont orthogonaux.

Essayez de créer vous-même des carrés latins orthogonaux en utilisant les cartes d'honneur (As, Roi, Dame, Valet) d'un paquet standard de cartes à jouer. Tout d'abord, ignorez complètement les couleurs et concentrez-vous sur l'arrangement du tableau 4 par 4 de sorte que chaque ligne et colonne contienne un As, un Roi, une Dame et un Valet, ou de manière équivalente de sorte qu'aucune ligne ou colonne n'ait deux As, ou deux Rois etc. Notez l'arrangement.

Concentrez-vous maintenant sur les combinaisons et ignorez les images et notez la disposition des combinaisons. Parce que chaque carte est différente, c'est-à-dire que toutes les combinaisons sont différentes, par exemple As de pique, As de cœur, As de carreau et As de trèfle, le carré latin des « couleurs » est nécessairement orthogonal au carré latin des « images » .

En 1783, Euler a fait une conjecture sur les carrés latins orthogonaux et il a fallu près de 200 ans aux mathématiciens pour prouver que les carrés latins orthogonaux existent pour tous les ordres sauf 2 et 6.

Combien de solutions différentes pouvez-vous trouver au problème suivant qui a été initialement posé par Euler ?

« Disposez 25 officiers, chacun ayant l'un des cinq grades différents et appartenant à l'un des cinq régiments différents, en une formation carrée 5 par 5, de sorte que chaque rangée et chaque file ne contiennent qu'un officier de chaque grade et un seul de chaque régiment. "

Le problème correspondant avec 36 officiers de six grades différents et appartenant à six régiments différents ne peut pas être résolu bien que pour 49 officiers il soit facile à résoudre comme indiqué ci-dessus.


15.2 : Carrés latins et Sudokus - Mathématiques

Bâtiment III.1.1 - Soit b1 ,b2 . bm être les éléments d'un corps fini GF(n) où n = p k . Soit b1 être l'identité multiplicative ( = 1) et bm soit l'identité additive ( = 0) de GF(n). Pour e = 1,2, . n-1 définit le tableau n &fois n L (e) = (aje (e) ) en prenant unje (e) = (be &fois bje ) + bj, où les opérations de droite sont sur le terrain. Les carrés résultants forment un ensemble complet de MOLS d'ordre n.

Devoirs : Construire des ensembles complets de MOLS des ordres 8 et 9, puis les mettre sous forme standard

Preuve: Il faut montrer que chaque L est en fait latin et que toute paire d'entre eux est orthogonale.

On montre d'abord que L (e) est un carré latin. Supposons que L (e) fasse apparaître deux fois le même élément dans la ligne i, alors unje (e) = unje (e) . Donc, nous aurions be &fois bje + bj = be &fois bje + bk ainsi, en utilisant les propriétés du champ, nous avons bj = bk , et donc j = k. Ainsi, tous les éléments d'une même rangée sont distincts. De même, (remplissez les détails) nous pouvons montrer que tous les éléments d'une colonne sont distincts. Ainsi, L (e) est un carré latin pour toute valeur de e.

Considérons maintenant deux carrés L (e) et L (f) . Supposons que (unje (e) , unje (f) ) = (unkm (e) , unkm (f) ) ce qui implique, unje (e) = unkm (e) et unje (f) = unkm (F) . Cela conduit à deux équations, be &fois bje + bj = be &fois bk + bm et BF &fois bje + bj = bF &fois bk + bm. En soustrayant la seconde à la première puis en utilisant les lois de distribution, on obtient (be -bF ) &fois bje = (be -bF ) &fois bk et depuis ef, be -bF0 et nous pouvons conclure que bje = bk , donc je = k. En utilisant cela dans la première de nos équations originales, nous permet de conclure que bj = bm et donc j = m. Nous avons montré que les paires ordonnées sont uniques et que les carrés sont donc orthogonaux.

Notez que dans cette construction, le premier carré a une ij-ième entrée égale à bje + bj , de sorte que ce premier carré est un isotope de la table d'addition du champ. Notez également, dans les exemples que vous avez calculés, que chacun des autres carrés de l'ensemble n'est qu'une permutation de ligne du premier carré (essayez de le prouver pour vos devoirs). Les MOLS qui sont liés de cette manière sont dits basé sur le carré d'origine. Cette construction donne donc un ensemble de MOLS basé sur le groupe additif d'un corps (un p-groupe abélien élémentaire).

Question de recherche: Quel est le plus grand nombre de MOLS dans un ensemble basé sur un groupe cyclique d'ordre non premier ? (Pour l'ordre premier, le groupe cyclique est le groupe additif d'un champ et donc un ensemble complet existe, mais pour les ordres non premiers en général, la réponse n'est pas connue.)

Comme nous le verrons plus loin dans le terme, il existe des ensembles complets de MOLS qui ne découlent pas de cette construction. En outre, il existe des méthodes de construction d'ensembles de MOLS qui ne garantissent pas des ensembles complets comme le fait cette construction.

Avions Affine de MOLS

Soit L1, L2, . Lq-1 être un ensemble complet de MOLS d'ordre q et une matrice A a q × q contenant q 2 symboles distincts. On définit des ensembles de taille q (lignes du plan affine) sur cet ensemble de q 2 symboles (points du plan affine) de la manière suivante : Il y a q ensembles qui sont les lignes de A, et q ensembles qui sont les colonnes de A. Les ensembles q 2 - q restants sont formés en prenant chaque Lje à son tour, le superposant à A et prenant comme ensembles les éléments de A qui correspondent à un seul symbole dans le Lje.

A titre d'exemple considérons l'ensemble des 3 MOLS d'ordre 4 : Soit A la matrice, Les droites du plan affine sont : <1,2,3,4> <5,6,7,8> <9, 10,11,12> <13,14,15,16> <1,5,9,13> <2,6,10,14> <3,7,11,15> <4,8,12,16 >- à partir des lignes et des colonnes, et
<1,6,11,16> <2,5,12,15> <3,8,9,14> <4,7,10,13> <1,7,12,14> <2,8, 11,13> <3,5,10,16> <4,6,9,15> <1,8,10,15> <2,7,9,16> <3,6,12,13> < 4,5,11,14>- des carrés latins.

Exercice : Construire deux plans affines à partir des 2 MOLS d'ordre 3.

On peut aussi inverser la construction et produire un ensemble complet de MOLS à partir d'un plan affine de la manière suivante :

Soit un plan affine d'ordre n. Pour chaque classe parallèle de lignes de , étiquetez arbitrairement avec les chiffres 1. n chaque ligne de la classe parallèle. Sélectionnez maintenant deux classes parallèles. Les lignes contenues dans ces classes parallèles serviront à indexer les lignes et les colonnes des carrés latins, étiquetez donc l'une des classes R et l'autre C. Les n 2 points d'intersection des lignes en R et C sont associés à des paires de nombres, le numéro de la ligne dans R et le numéro de la ligne dans C. Maintenant, pour chaque classe parallèle en autre que R ou C, nous allons former un carré latin de la manière suivante : Si P est une classe parallèle, nous ont déjà étiqueté toutes les lignes de P. Les n 2 points d'intersection des lignes R et C doivent tous se trouver sur les n lignes étiquetées de P. Dans la cellule du carré correspondant à l'un des points d'intersection on place l'étiquette de la droite en P qui passe par ce point. Il est facile de voir que le carré ainsi produit est un carré latin d'ordre n. Cette procédure est répétée pour chacune des classes parallèles autres que R ou C, donnant n-1 carrés latins.

Pour voir qu'ils sont mutuellement orthogonaux, considérons deux de ces carrés et supposons que lorsqu'ils sont superposés, il y a deux cellules contenant (a,b). Puisque les deux cases du premier carré ont reçu l'étiquette a, les deux points qui correspondent aux cases doivent avoir été sur la même ligne (notée a) de la classe parallèle correspondant au premier carré. Puisque ces mêmes cellules ont l'étiquette b dans le deuxième carré, les deux points doivent également être sur la ligne étiquetée b contenue dans une classe parallèle différente. Ceci est impossible par l'axiome A1, on voit donc que ces carrés doivent être orthogonaux entre eux.

Par la construction III.1.1 et la construction ci-dessus, nous voyons qu'un plan affine d'ordre n existe toujours si n est une puissance première ou première, c'est-à-dire l'ordre d'un corps fini. Le seul théorème que nous ayons qui exclut certains plans affines est le suivant :

Théorème VIII.1.4 - [Bruck-Ryser Thm.] Si n 1 ou 2 mod 4 alors un plan affine (projectif) d'ordre n n'existe pas à moins que n soit la somme de deux carrés entiers.

Ce théorème implique qu'il n'existe pas de plan affine (projectif) d'ordre 6, résultat que nous aurions pu déduire puisqu'il n'existe aucune paire, et encore moins un ensemble complet, de MOLS d'ordre 6. Remarquons que, puisque 10 = 9 + 1, ce théorème ne dit rien sur l'existence d'un plan projectif d'ordre 10. Une recherche informatique extrêmement longue a finalement prouvé que ce plan n'existe pas (voir note en fin de chapitre). Le plus petit cas ouvert est n = 12 que le théorème de Bruck-Ryser ne couvre pas et ensuite n = 18, qui puisque 18 = 9 + 9, le théorème ne dit rien. Les seuls ordres connus sont les nombres premiers et les puissances premières, bien qu'il existe des constructions alternatives qui donnent des plans projectifs qui ne sont pas isomorphes à ceux produits par la construction carrée latine. La renommée et la reconnaissance instantanées seront la récompense du mathématicien qui tranche la question de l'existence de plans projectifs d'ordre composite.

Il y a plusieurs questions de recherche intéressantes concernant les filets. Par exemple, quelles conditions sur un réseau sont suffisantes et nécessaires pour que le réseau s'étende à un plan affine ? Quelles conditions sont nécessaires pour qu'un réseau extensible à un plan affine ne puisse être étendu que d'une seule manière ?


2 réponses 2

Ce qui suit est une preuve standard de ce fait. J'esquisse la logique avec une série de questions.

Si $A$ est un carré latin, vous en obtenez un autre en renommant les entrées. De cette façon, vous pouvez mettre $A$ dans une sorte de forme standard $A_$ qui a $(1,2,ldots,n)$ comme première ligne.

$ A=gauche(egin 2&1&33&2&11&3&2fin ight), $ alors nous pouvons mettre cela sous une forme standard en mettant un '1' partout où il y a un '2' et un '2' partout où il y a un '1' et obtenir $ A_=gauche(egin 1&2&33&1&22&3&1findroit) $

Lemme : Si $A$ et $B$ sont des carrés latins orthogonaux, alors $A_ le sont aussi$ et $B_$.

Vous le prouvez ! Ce n'est pas difficile. Permettez-moi d'illustrer avec un exemple. Le LS $A$ ci-dessus est orthogonal au carré latin $ B=left(egin 2&3&13&1&21&2&3fin ight), $ car les paires d'entrées sont (2,2),(1,3),(3,1) sur la première ligne, (3,3),(2,1),(1,2) sur le second et (1,1),(3,2),(2,3) sur le dernier. La forme standard de $B$ est (cochez ceci pour comprendre ce que signifie la forme standard) $ B_=gauche(egin 1&2&32&3&13&1&2findroite). $ Pour vérifier que vous comprenez l'orthogonalité, je vous invite à vérifier que $A_$ et $B_$ sont, en effet, orthogonaux.

Donc si $A^<(1)>, A^<(2)>,ldots A^<(k)>$ sont des carrés latins orthogonaux entre eux, alors par le lemme nous pouvons supposer qu'ils sont tous sous la forme standard . Les premières lignes contiennent donc les paires $(i,i),i=1,2,ldots,n$ pour toutes les paires de carrés latins. Regardons ensuite la position de 2 sur la première colonne de $A^<(1)>$. Disons que cela se produit sur la ligne $j$, donc $A^<(1)>_=2$.

Question 1 : Pourquoi est-il illégal d'avoir $A^<(i)>_=2$ pour tout $i=2,3,ldots,k$?

Question #2 : Pourquoi est-il illégal d'avoir $A^<(i)>_=1$ pour tout $i=2,3,ldots,k$?

Question 3 : Pourquoi est-il illégal d'avoir $A^<(i)>_=A^<(ell)>_$ pour deux indices $i$ et $ell$ tels que $2le i<ellle k$?

Question n°4 : Pourquoi les réponses aux questions précédentes impliquent-elles $k<n$ ?

Démontrez le lemme (à moins que cela ne soit fait dans le livre) et répondez aux questions ! Bonne chance!


Voir la vidéo: Beginner Guide: How to solve Super Fiendish sudoku: 18 Jan 18 (Décembre 2021).