Version interactive avec LaTeX compilé

ENS Informatique Fondamentale (Maths Info) MP PC 2002

Notez ce sujet en cliquant sur l'étoile

0.0(0 votes)

🔗 Explorer

X-ENS MP/PC X-ENS 2002 MP/PC Maths Info Maths Info 2002

2025_08_29_13d329cec6759f562299g

Filières MP et PC (groupe I)
(Epreuve commune aux ENS de Paris et Lyon)

MATHEMATIQUES-INFORMATIQUE

Durée : 4 heures

L'usage de toute calculatrice est interdit.

Autour des carrés latins

Notations

On note

l'ensemble des entiers naturels,

l'ensemble des entiers relatifs,

et, pour tout

l'ensemble des entiers de 0 à

. Si

, on note

mod

le quotient et le reste dans la division euclidienne de

par

, c'est-à-dire les uniques entiers tels que

. Si

, on note

le plus grand diviseur commun (

) de

et de

lorsque (

)

et, par convention,

. Par définition, le pgcd est donc un entier strictement positif sauf si

. On définit de façon similaire le pgcd d'un ensemble d'entiers. On rappelle que, pour

, les quatre propriétés suivantes sont équivalentes : (i)

, (ii) il existe

tel que

(propriété de Bezout), (iii)

tel que

, (iv)

est un générateur du groupe défini par

muni de l'addition modulo

Une matrice

de taille

à coefficients dans

est une famille

d'éléments de

. Une matrice carrée de taille

est une matrice de taille

. La ligne d'indice

(resp. la colonne d'indice

) de

est la famille

(resp.

). Attention : les lignes et colonnes sont donc indexées à partir de 0 et non à partir de 1 , ceci pour simplifier les notations de certaines parties du sujet. De même, on numérote les composantes d'un

-uple

de 0 à

et on note

sa composante d'indice

Partie 1. Quelques propriétés des matrices carrées entières

Une matrice est entière si elle est à coefficients dans

. On dit qu'une matrice est unimodulaire si elle est carrée, entière et si son déterminant vaut 1 ou -1 . Avec l'addition et le produit usuels sur les matrices, l'ensemble des matrices entières carrées de taille

forme un anneau

dont l'élément unité est noté

Forme d'Hermite d'une matrice carrée entière

On note

la matrice dont tous les coefficients sont nuls sauf

. Les matrices

et, lorsque

sont appelées matrices élémentaires.

Question 1.1. Quel est l'effet, sur une matrice

, de la multiplication à droite par une matrice élémentaire? Quel est le déterminant des matrices élémentaires? Ont-elles un inverse dans

Question 1.2. Que fait l'algorithme de la figure 1 pour une matrice

? Montrer qu'il se termine toujours et que, quel que soit

, le pgcd de la ligne d'indice

n'est pas modifié par l'algorithme.

Question 1.3. Soit

. Montrer, en donnant un algorithme inspiré de celui de la question précédente, qu'il existe une matrice

triangulaire inférieure, à diagonale positive ou nulle, et une matrice unimodulaire

telles que

. Montrer que si le déterminant de

est non nul, on peut de plus imposer

pour tout

Pour $j$ de 0 à $n-1$
    Si $(A(0, j)<0) A \leftarrow A S_{j} ;$
FinPour
$C \leftarrow\left\{j \in \mathcal{N}_{n} \mid A(0, j) \neq 0\right\} ;$
Tant que ( $C \neq \emptyset$ )
    $m \leftarrow \min \{A(0, j) \mid j \in C\} ;$
    Soit $k \in C$ tel que $A(0, k)=m$;
    $A \leftarrow A P_{0, k}$;
    Pour $j$ de 1 à $n-1$
        $q \leftarrow A(0, j) \div m ;$
        $A \leftarrow A\left(R_{0, j}\right)^{q}$;
    FinPour
    $C \leftharpoondown\left\{j \in \mathcal{N}_{n} \backslash\{0\} \mid A(0, j) \neq 0\right\} ;$
FinTantQue

Fig. 1 - Algorithme de la question 1.2.

Question 1.4. Montrer que toute matrice unimodulaire est produit de matrices élémentaires et que l'ensemble des matrices unimodulaires de taille

est l'ensemble des inversibles de

Question 1.5. Montrer que si le déterminant de

est non nul, il existe une unique décomposition

vérifiant toutes les propriétés de la question 1.3. On dit alors que la matrice

est la forme d'Hermite de

Équations en nombres entiers et opérations «modulo»

Étant donné un

-uple

, on note

. Si

, on définit l'application

par

où l'opération modulo est calculée composante par composante, c'est-à-dire

mod

. Dans la suite, on suppose que

sont donnés et on cherche des conditions pour que la restriction de

à un ensemble de la forme

soit une bijection de

dans

. On note

Question 1.6. Soit

. Montrer que la restriction de

est injective si et seulement si

est l'unique solution de

avec

On note

la matrice de

, diagonale, définie par

. On vérifie alors aisément que

si et seulement s'il existe

tel que

Question 1.7. On suppose pour commencer que

sont quelconques dans

mais que

est unimodulaire. Montrer que si la diagonale de la forme d'Hermite de

est égale à

alors la restriction de

est une bijection de

dans

Question 1.8. On suppose à présent que

est quelconque mais que

. On a alors

. En utilisant la forme d'Hermite de

, montrer que si

alors la restriction de

est injective. Montrer que si

est surjective, il existe deux matrices

telles

. En déduire que

. Conclure.

Tournez la page S.V.P.

Partie 2. Quelques propriétés des carrés latins

Carrés latins et groupes

On dit qu'une matrice carrée de taille

à coefficients dans

est un carré latin de taille

si chaque élément de

apparaît exactement une fois dans chaque ligne et dans chaque colonne. On dit que deux carrés latins

sont équivalents si on peut passer de l'un à l'autre par renommage bijectif des éléments et permutation des lignes et des colonnes, c'est-à-dire si

sont de même taille

et s'il existe trois permutations

telles que pour tout

. Cette relation sur les carrés latins est évidemment une relation d'équivalence.

Un ensemble muni d'une loi de composition interne est appelé magma. À un carré latin

de taille

, on associe le magma

où la loi

est donnée par

.
Question 2.1. Construire un carré latin dont le magma associé n'a pas d'élément neutre. Montrer que pour tout carré latin, il existe un carré latin équivalent dont le magma associé possède 0 comme élément neutre. Combien y a-t-il de classes d'équivalence de carrés latins de taille

pour

? De carrés latins de taille

pour

Question 2.2. Existe-t-il des carrés latins de n'importe quelle taille?
Question 2.3. Soit (

) un magma possédant un élément neutre et soit (

) un magma dont la loi

est associative. On suppose qu'il existe une bijection

dans

et deux bijections

dans

telles que pour tout

. Montrer que pour tout

. En déduire que

, puis montrer que

est un isomorphisme, c'est-à-dire que pour tout

.
Question 2.4. Donner un représentant par classe d'équivalence de carrés latins de taille 4. Construire un carré latin de taille minimale qui ne soit pas équivalent à un carré latin associé à un groupe. Dans les deux cas, ne pas oublier de justifier avec soin.

Carrés eulériens et carrés magiques

Étant donnés deux carrés latins

de taille

, on définit la matrice

à coefficients dans

par

. Si tous les coefficients de

sont distincts, on dit que

sont orthogonaux et que

est un carré eulérien de taille

.
Question 2.5. Soient

deux carrés latins de taille n. Pour tout

, on note

la permutation telle que, pour tout

. Montrer que

sont orthogonaux si et seulement si, quel que soit

, tous les

sont distincts. En déduire qu'un carré latin associé à un groupe cyclique d'ordre pair n'a pas d'orthogonal. (On pourra considérer la somme, modulo

, de tous les éléments de

.)
Un carré latin de taille

est diagonal si tous les éléments

de la diagonale sont distincts, ainsi que tous les éléments

de l'anti-diagonale. Un carré eulérien (

) est diagonal si

sont diagonaux. Une matrice carrée de taille

, à coefficients dans

, est un carré magique de taille

si tous ses coefficients sont distincts et si toutes les sommes des coefficients d'une ligne, d'une colonne, de la diagonale et de l'anti-diagonale sont égales (

Question 2.6. Montrer que l'on peut construire un carré magique de taille

à partir d'un carré eulérien diagonal de taille

Question 2.7. Pour

, déterminer s'il existe des carrés eulériens, des carrés eulériens diagonaux et des carrés magiques de taille

. En cas de réponse positive, en donner un exemple.

Question 2.8. Donner une condition nécessaire et suffisante sur

pour que la matrice de taille

définie par

soit un carré latin. Même question pour un carré latin diagonal. Soient

dans

. Montrer que les deux carrés latins définis par

sont orthogonaux si et seulement si

. (On pourra raisonner directement en introduisant

tel que

ou bien faire le lien avec la question 1.8.)

Question 2.9. Montrer qu'il existe un carré magique de taille

pour tout entier

qui n'est multiple ni de 2 ni de 3 . Donner un carré magique de taille 5.

Partie 3. Hyper-rectangles latins

On dit qu'une application

dans

définit une multi-bijection de

dans

, pour

, si tous les éléments de

ont le même nombre d'antécédents par

dans

. Un tableau de dimension

, de taille

, dans un ensemble

, est une application de

dans

. Un tableau

est un hyper-rectangle latin si

, l'application

définit une multi-bijection de

dans

. Autrement dit, un tableau peut être vu comme la généralisation d'une matrice en dimension

et un tableau est un hyper-rectangle latin si dans tout sous-tableau obtenu en fixant un indice, tous les éléments de

apparaissent le même nombre de fois. Lorsque toutes les multi-bijections sont des bijections (chaque élément apparaît alors une et une seule fois dans chacun des sous-tableaux), on dit que le tableau est un hyper-cube latin. En dimension 2 , lorsque

, les hyper-cubes latins sont de taille

et on retrouve la notion de carré latin de taille

Étude des tailles compatibles élémentaires

On s'intéresse pour commencer au problème suivant : comment répartir

boules identiques dans

boîtes distinctes de sorte que chaque boîte contienne au plus

boules et qu'au moins

boîtes en contiennent exactement

Question 3.1. Montrer qu'il existe une telle répartition si et seulement si

. Expliquer, en justifiant avec précision, ce que fait la procédure

de la figure 2 lorsque

. (Par convention, une boucle «Pour

» n'est pas exécutée si

Pour qu'il existe un hyper-rectangle latin de taille

, de dimension

, dans un ensemble de cardinal

, il faut évidemment que, pour tout

soit un multiple de

. Lorsque

vérifie cette propriété, on dit que

est une taille compatible avec

. Lorsque, de plus, il n'existe pas de taille

, compatible avec

, telle que

avec

, on dit que

est élémentaire pour

. L'objet des questions suivantes est de générer toutes les tailles élémentaires pour

Étant donnés

dans

, on définit l'occurrence de

dans

comme le plus grand entier naturel

tel que

divise

Tournez la page S.V.P.

$\mathrm{P}(n, m, c, d)\{$
    Si $(d=1)$
        boîte $[d-1]=n$;
    Sinon
        Pour $i$ de $\max (0, n-m(d-1))$ à $\min (m-1, n-c m)$
            boîte $[d-1]=i$;
            $\mathrm{P}(n-i, m, c, d-1) ;$
        FinPour
        Si $(n \geq m)$
            boîte[ $d-1]=m$;
            $\mathrm{P}(n-m, m, \max (0, c-1), d-1)$;
        FinSi
    FinSi
\}

Fig. 2 - Code de la procédure P.

Question 3.2. Soit

une taille compatible avec

un facteur premier de

d'occurrence

. On note

l'occurrence maximale de

dans une composante de

. Montrer que l'occurrence de

dans

est au moins

. Montrer de plus que si

est élémentaire pour

, alors l'occurrence de a est égale à

pour au moins deux composantes de

et l'occurrence de

dans

est exactement

Question 3.3. Lorsque

n'a qu'un seul facteur premier, écrire un programme utilisant la procédure

de la figure 2 pour générer toutes les tailles élémentaires pour

. Comment pourrait-on générer toutes les tailles élémentaires pour un entier

quelconque?

Une construction particulière d'hyper-rectangles latins de la forme

Soient

, compatible avec

. L'objet de cette dernière partie est de mettre au point un programme compact, généralisant le principe de construction d'un carré latin de la question 2.8 , pour construire

(avec

) et une matrice entière

, de taille

, tels que lapplication

dans

, définie par

, soit un hyper-rectangle latin.

Question 3.4. Soient

entière de taille

. Montrer que les propriétés suivantes sont équivalentes : (i)

est un hyper-rectangle latin de

dans

, (ii)

définit une multi-bijection de

dans

, (iii)

définit une multi-bijection de

dans

où

est la matrice obtenue en supprimant la colonne d'indice

est obtenu en supprimant la composante d'indice

Question 3.5. On s'intéresse ici au cas particulier des hyper-cubes. Vérifier que s'il existe un hyper-cube latin de taille

alors

avec

(d'où l'appellation de «cube»). Réciproquement, lorsque

avec

, construire un hyper-cube latin de taille

dans un ensemble de cardinal-p. (On pourra s'inspirer des résultats des questions 1.8 et 3.4 et choisir une matrice bi-diagonale.)

définit un hyper-rectangle latin de

dans

et si

vérifie

avec

, alors

, en tant qu'application de

dans

, définit également un hyper-rectangle latin. Il suffit donc de savoir construire un hyper-rectangle latin de n'importe quelle taille élémentaire pour savoir construire un hyper-rectangle latin de n'importe quelle taille compatible. En dimension 2, il n'existe qu'une taille élémentaire pour

, c'est (

) qui correspond à un carré latin de taille

. En dimension

en revanche, toutes les tailles élémentaires ne correspondent pas à des hyper-cubes latins (considérer par exemple

qui est élémentaire pour 30 ) et il ne suffit pas de savoir construire des hyper-cubes latins pour savoir construire des hyper-rectangles latins de n'importe quelle taille compatible. L'objet des questions suivantes est de mettre en place un procédé différent de construction d'hyper-rectangles latins, par récurrence sur la dimension.

Dans la suite, pour un

-uple

, on note

le (

)-uple obtenu en supprimant la dernière composante de

Question 3.6. Soient

une matrice entière de taille

telle que

soit un hyper-rectangle latin de dimension (

) de

dans

. Soit

une matrice entière de taille

de la forme :

Montrer que si la dernière composante de

(c'est-à-dire

) divise la dernière composante de

(c'est-à-dire

) et que

est une multi-bijection de

dans

alors

est un hyper-rectangle latin de dimension

dans

On définit à présent

, en fonction de

, par la formule suivante (où, par convention, un produit sans termes vaut 1 ) :

Question 3.7. Montrer que, pour des entiers

non nuls, on a

. Montrer les propriétés suivantes : (1)

, (2)

, (3)

divise

, (4) on retrouve

en appliquant la formule (1) avec

et l'entier

, (5)

est compatible avec

et,

est multiple de

Question 3.8. Soit

, matrice diagonale de

, et

de la forme :

En considérant pour commencer le cas où

est de taille 2 puis en généralisant, montrer que la diagonale

de la forme d'Hermite de

est donnée par la récurrence descendante suivante :

pour

, enfin

On étudie maintenant la récurrence descendante définie par

et, pour

.
Question 3.9. Montrer, en utilisant la propriété (3) de la question 3.7, que

et que

divise

, lorsque

. Montrer, par une récurrence descendante sur

et en utilisant la propriété (5) de la question 3.7, que

divise

. En déduire que

divise

Soit

, unimodulaire, et

de la forme:

On vérifie aisément que si

alors

est unimodulaire et son inverse est :

Question 3.10. En regroupant tous les résultats de cette dernière partie et en utilisant le résultat de la question 1.7, donner un procédé récursif de construction d'un hyper-rectangle latin de toute taille

compatible avec

. (On remarquera que la matrice

apparaissant dans la construction est unimodulaire triangulaire inférieure et que multiplier une matrice à gauche par une matrice unimodulaire triangulaire inférieure ne change par les coefficients diagonaux de sa forme d'Hermite.)

On peut vérifier que le programme ci-dessous suit le principe développé dans cette partie et calcule bien une matrice

telle que

soit un hyper-rectangle latin de taille

compatible avec

lorsque

est donné par la formule (1).

Matrice $(d, \vec{c}, \vec{a})\{$
    Pour $i$ de 0 à $d-2$
        Pour $j$ de 0 à $d-1$
            Si $(j=0$ ou $j=i+1) A(i, j)=1$; Sinon $A(i, j)=0$;
        FinPour
    FinPour
    Pour $i$ de 1 à $d-2$
        $r=a_{i} ;$
        Pour $j$ de $i-1$ à 0 (par valeurs descendantes)
            $w=\frac{r}{r \wedge c_{j+1}} ; r=\left(w a_{j}\right) \wedge r ;$
            Pour $k$ de 0 à $i$
                $A(i, k)=A(i, k)-w A(j, k) ;$
            FinPour
        FinPour
    FinPour
\}

ENS Informatique Fondamentale (Maths Info) MP PC 2002

Filières MP et PC (groupe I) (Epreuve commune aux ENS de Paris et Lyon)

MATHEMATIQUES-INFORMATIQUE

Autour des carrés latins

Notations

Partie 1. Quelques propriétés des matrices carrées entières

Forme d'Hermite d'une matrice carrée entière

Équations en nombres entiers et opérations «modulo»

Tournez la page S.V.P.

Partie 2. Quelques propriétés des carrés latins

Carrés latins et groupes

Carrés eulériens et carrés magiques

Partie 3. Hyper-rectangles latins

Étude des tailles compatibles élémentaires

Tournez la page S.V.P.

Une construction particulière d'hyper-rectangles latins de la forme

Filières MP et PC (groupe I)
(Epreuve commune aux ENS de Paris et Lyon)