Jeu "azul"

depasse

Bonjour
Je sèche sur le problème suivant que je me pose à propos de mon cadeau de Noël, le jeu AZUL.

Combien y a-t-il de matrices $n\times n$ dont l'ensemble des coefficients de chaque ligne et de chaque colonne est $1,n$ ?

Il est probable que ces matrices ont un nom depuis longtemps ! Si jamais je l'ai connu, je l'ai oublié.
Je pense au produit des $n$ premières factorielles mais n'arrive pas à le prouver. C'est peut-être tout simplement faux !
Une référence me ferait plaisir.
Merci.
Paul.

Poirot

Le nombre que tu donnes est un majorant mais pas le cardinal recherché. Il y a $n!$ possibilités pour constituer la première ligne. Mais pour la seconde ligne, il y a strictement moins de $(n-1)!$ possibilités. En effet, il y a $n-1$ choix possibles pour le coefficient en position $2,1$, $n-2$ choix possibles pour le coefficient en position $2,2$, etc. Mais certains de ces choix mènent à une impasse. Par exemple pour $n=3$, si on a commencé notre matrice comme ceci $$\begin{pmatrix}1&2&3\\2&1&(*)\\&\dots&\end{pmatrix}$$ on voit que l'on ne pourra pas finir.

Si on note $p_i$ le nombre de possibilités pour remplir a $i$-ème ligne, on doit avoir que $i!-p_i$ est strictement décroissant, car il y a de plus en plus de contraintes à chaque nouvelle ligne.

depasse

Merci Poirot,

mais il me semble qu'il y a bien 12 solutions pour $n=3$:

$6$ possibilités pour la première ligne, deux pour chacune de ces 6 pour la seconde ligne et 1 enfin pour la troisième ligne une fois choisies les deux premières.

Dreamer

Bonjour.

Si j'ai bien compris, il s'agit de carrés latins.
Il y a une abondante source d'informations sur le sujet, tout comme sur leur comptage.

À bientôt.

Poirot

Je pense que c'est la fameuse loi des petits nombres. Pour $n=4$ on voit qu'il y a (contrairement à ce que je disais !) strictement plus que $3!$ manières de remplir la seconde ligne : $$\begin{pmatrix}1&2&3&4\\&&&\\2&1&4&3\\2&3&4&1\\2&4&1&3\\3&1&4&2\\3&4&1&2\\3&4&2&1\\4&1&2&3\\4&3&1&2\\4&3&2&1\end{pmatrix}.$$ Mais après rien ne dit que toutes ses configurations sont remplissables jusqu'en bas...

depasse

Carré latin, mais c'est bien sûr! Merci Dreamer.
D'après Villemin, pas de formule mais, comme le flaire Poirot, le produit des premières factorielles serait en fait un minorant.
Cordialement
Paul

raoul.S

Je ne pensais pas qu'on aboutirait à un problème si difficile avec les carrés latins : en fait on a même pas de formule générale pour le nombre de carrés latins d'ordre $n$.

Dans cet article il est dit :

"Soit $I_n$ le nombre de carrés latins d'ordre n ; jusqu'à ce jour, on a pu déterminer les valeurs exactes de $I_n$ pour $1\leq n\leq 8$. Pour calculer $I_8$, on a dû recourir à l'usage d'ordinateurs, mais même avec ceux-ci, en l'absence de nouvelles méthodes, on ne peut espérer aller bien loin dans cette direction."

Dreamer

Sur OEIS, Ils vont au moins jusqu'à 11...
Ce sont les carrés latins réduits qui semblent être la difficulté à surmonter.
Il y a des articles récents mais rien de concluant effectivement.
En tous cas, il y a de la lecture pour intéressé.
À bientôt.

PetitLutinMalicieux

Bonjour

depasse a écrit:

D'après Villemin, pas de formule

Soyons précis. Pour ton jeu Azul, n=5. Et Gérard Villemin indique clairement qu'il y a 161 280 possibilités, dans ton cas.

Eric

Quand tu auras fini avec le premier Azul, passe au deuxième (pas encore testé le troisième). Tu vas pouvoir te poser des problèmes combinatoires ...

Dreamer

Il semble que cette gamme de jeux n'est pas très interactive et est très "kitche".

Je n'ai pas vu de présentation du jeu qui mette en avant sa mécanique intrinsèque, contrairement à Dobble, par exemple.

À bientôt.