Le drapeau hollandais

Le problème du drapeau hollandais, proposé par Dijkstra, consiste à trier un tableau contenant des boules de couleurs bleues, blanches et rouges de façon à retrouver le drapeau hollandais.

Exercice

On dispose d’un tableau de taille $n$ contenant soit des boules bleues, soit des boules blanches. Nous représentons les boules bleues par l’entier $0$ et les boules blanches par $1$. Les seules opérations autorisés sont la lecture d’une case du tableau et l’échange de deux cases.

$1)$ Proposer un algorithme de tri sur place du tableau effectuant au plus $n$ lecture de cases.

$2)$ Combien d’échange au maximum l’algorithme effectue-t-il ?

Le problème du drapeau Hollandais, fonctionne sur le même principe excepté qu’on ajoute cette fois-ci des boules rouges représentées par $2$. Notre but est de trier notre tableau en bleu-blanc-rouge en effectuant le moins de lecture de cases possible.

$3)$ Proposer un algorithme de tri sur place du tableau effectuant au plus $n$ lecture de cases.

$4)$ Combien d’échange au maximum l’algorithme effectue-t-il ?

Correction

$1)$ On propose l’algorithme suivant.

La quantité $y-x$ est entière et décroît de 1 à chaque itération. De plus, on sort de la boucle si $y-x \lt 0$. Ainsi, l’algorithme termine après $n$ itérations de boucles. Or chacune n’effectue qu’une unique lecture. On effectue donc exactement $n$ lectures mémoires.

Prouvons la correction de cet algorithme. Pour ce faire, nous exhibons un invariant de boucle $\mathcal{I}$ en définissant $\mathcal{I}(i) = $ « À la fin de l’itération $i$, les boules de $1$ à $x$ sont toutes bleues et les boules de $y+1$ à $n$ sont toutes blanches » . Avant d’entrer dans la boucle, $x(i)=1$ et $y(i)=n$ donc la propriété est vérifiée.

On suppose que l’invariant est vérifié à l’étape $i$. À l’étape $i+1$ si $T[x(i)]$ est bleue et $x(i+1)=x(i)+1$. Les boules de $0$ à $x(i+1)-1$ sont bleues et comme $y$ n’est pas modifié, on a encore que les boules de $y(i+1)+1$ à $n-1$ sont toutes blanches. Si $T[x(i)]$ est blanche, on montre de même que l’invariant est conservé.

Enfin, à la sortie de la boucle après l’itération $n$, on a $y(n) \lt x(n)$. Ainsi, notre algorithme renvoie bien un tableau trié.

$2)$ Dans chaque itération, on effectue au plus un échange. On effectue donc au plus $n$ échanges. De plus, ce nombre est atteint dans le cas du tableau ne contenant que des boules blanches.

$3)$ On considère l’algorithme suivant.

On effectue exactement $n$ passages dans la boucle. On effectue donc bien exactement $n$ lectures de cases.

La preuve de la correction et de la terminaison est similaire à l’algorithme du cas deux couleurs. L’invariant à considérer est $\mathcal{I}(i) = $ « À la fin de l’itération $i$, les boules de $1$ à $x$ sont toutes bleues, les boules de $y+1$ à $z$ sont toutes blanches et les boules de $z+1$ à $n$ sont toutes rouges. »

$4)$ Dans le pire des cas, on effectue deux échanges par itération. On effectue donc au plus $2n$ échanges. Ce pire cas est atteint dans le cas du tableau ne contenant que des boules rouges.

Stabilité des langages rationnels

Le but de cet exercice est de présenter plusieurs opérations stables sur les langages rationnels. On suppose connu l’équivalence entre les langages rationnels et les langages reconnaissables par automate fini.

Exercice

Soit $\mathcal{L}_1$ et $\mathcal{L}_2$ deux langages rationnels sur l’alphabet $\Sigma$. Montrer que les langages suivants sont rationnels.

$1)$ $\overline{\mathcal{L}_1} = {\;w \in \Sigma^{*}\;|\;w \notin \mathcal{L}_1\;}$ le complémentaire de $\mathcal{L}_1$.

$2)$ $\mathcal{L}_1 \cap \mathcal{L}_2$ l’intersection de $\mathcal{L}_1$ et $\mathcal{L}_2$.

$3)$ $\mathcal{L}_1 \setminus \mathcal{L}_2$ la différence ensembliste de $\mathcal{L}_1$ et $\mathcal{L}_2$.

$4)$ $Mir(\mathcal{L}_1) = \{\;\bar{w} = w_1 w_2 \ldots w_n \in \Sigma^{*}\;|\;w_i \in \Sigma,\;w = w_n \ldots w_2 w_1 \in \mathcal{L}_1\;\}$ le langage miroir de $\mathcal{L}_1$.

$5)$ $Pre(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists v \in \Sigma^{*}, \; wv \in \mathcal{L}_1\;\}$, le langage des préfixes de $\mathcal{L}_1$.

$6)$ $Suf(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists u \in \Sigma^{*}, \; uw \in \mathcal{L}_1\;\}$, le langage des suffixes de $\mathcal{L}_1$.

$7)$ $Fac(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists u,v \in \Sigma^{*} \; uwv \in \mathcal{L}_1\;\}$, le langage des facteurs de $\mathcal{L}_1$.

$8)$ $\mathcal{L}_1\#\mathcal{L}_2$ : le produit mélangé de $\mathcal{L}_1$ et $\mathcal{L}_2$. Les mots mélangé sont les $u_1v_1 \ldots u_kv_k$ avec les $u_i, v_i \in \Sigma^{*}$, avec $u=u_1u_2\ldots u_k \in \mathcal{L}_1$ et $v=v_1v_2\ldots v_k \in \mathcal{L}_2$.

$9)$ $\sqrt{\mathcal{L}_1} = \{\;w \in \Sigma^{*}\;|\; ww \in \mathcal{L}_1\;\}$, la racine carré de $\mathcal{L}_1$.

$10)$ $\frac{\mathcal{L}_1}{2} = \{\;w \in \Sigma^{*}\;|\;\exists u \in \Sigma^{*},\;|w|=|u|,\; wu \in \mathcal{L}_1,\;\}$, la moitié de $\mathcal{L}_1$.

Correction

Dans toute la suite, on notera $\mathcal{A}_1 = \left(\Sigma,\; Q,\; q_0,\; F,\; \delta\right)$ et $\mathcal{A}_2 = \left(\Sigma,\; Q’,\; q’_0,\; F’,\; \delta’\right)$ deux automates déterministe complet reconnaissant respectivement $\mathcal{L}_1$ et $\mathcal{L}_2$.

$1)$ Un mot $w$ appartient à $\mathcal{L}_1$ si et seulement si on atteint un état de $F$ dans $\mathcal{A}_1$ lorsqu’on lit $w$. De ce fait, un mot n’est pas dans $\mathcal{L}_1$ si et seulement si on atteint un état de $Q \setminus F$ dans $\mathcal{A}_1$ lorsqu’on lit $w$. Il en résulte donc que le complémentaire de $\mathcal{L}_1$ est reconnu par l’automate : \[\overline{\mathcal{A}}_1 = \left(\Sigma,\; Q,\; q_0,\; Q \setminus F,\; \delta\right)\] De ce fait, les langages rationnels sont stables par complémentaire.

$2)$ Pour deux ensembles $A$ et $B$ on rappel qu’on a la formule suivante : \[A \cap B = \overline{\overline{A} \cup \overline{B}}\] On a donc : \[\mathcal{L}_1 \cap \mathcal{L}_2 = \overline{\overline{\mathcal{L}_1} \cup \overline{\mathcal{L}_2}}\] Les langages rationnels étant stables par union et complémentaire, il en résulte qu’ils sont stables par intersection et $\mathcal{L}_1 \cap \mathcal{L}_2$ est rationnel.

$3)$ On rappel que pour deux ensembles $A$ et $B$ on a : \[A \setminus B = A \cap \overline{B}\] On a donc que les langages rationnels sont stables par différence ensemblistes.

$4)$ On considère $\delta^{-1}$ la fonction qui à $(q,a) \in Q \times \Sigma$ associe l’ensemble, éventuellement vide, des états $q’$ de $Q$ tels que $\delta(q,a) = q’$. On veut montrer que $Mir(\mathcal{L}_1)$ est reconnu par l’automate non déterministe suivant : \[Mir(\mathcal{A}_1) = \left(\Sigma,\; Q,\; F,\; \{q_0\},\; \delta^{-1}\right)\] En effet, si $w \in Mir(\mathcal{L}_1)$ alors $\bar{w} \in \mathcal{L}_1$. De ce fait, on considère la suite d’états de $q_0$ à $q’ \in F$ par lequel passe $\mathcal{A}_1$ en lisant $\bar{w}$. On note qu’un chemin dans $Mir(\mathcal{A}_1)$ en lisant $w$ est le chemin inverse de $q’$ à $q_0$. Donc on a bien $Mir(\mathcal{A}_1)$ qui reconnaît $w$. Réciproquement, si $w$ est reconnu par $Mir(\mathcal{A}_1)$ alors par définition de $\delta^{-1}$, on a un chemin de $q_0$ à un élément de $F$ dans $\mathcal{A}_1$ qui reconnait $\bar{w}$ et $w$ appartient à $Mir(\mathcal{L}_1)$. Ainsi, les langages rationnels sont stables par miroir.

$5)$ Soit $T$ l’ensemble des états $q$ de $\mathcal{A}_1$ tel qu’il existe un chemin de $q$ vers un état de $F$. Soit $v_q$ le mot formé par ce chemin. On considère un mot $w$ tel que $\mathcal{A}_1$ arrive dans un état $q$ de $T$ lorsqu’il le lit. On note alors que si on lit $wv_q$ on arrive dans un état de $F$. Il en résulte que $wv_q \in \mathcal{L}_1$ Donc $w \in Pre(\mathcal{L}_1)$. De plus, si $w$ est un mot préfixe de $\mathcal{L}_1$ alors il existe $v$ tel que $wv \in \mathcal{L}_1$. Donc, si $\mathcal{A}_1$ arrive dans un état $q$ en lisant $w$ alors $q \in T$. Il en résulte que $Pre(\mathcal{L}_1)$ est reconnu par l’automate suivant : \[Pre(\mathcal{A}_1) = \left(\Sigma,\; Q,\; q_0,\; T,\; \delta\right)\] Donc le langage des préfixes d’un langage rationnel est un langage rationnel.

$6)$ On note que le langage des suffixes de $\mathcal{L}_1$ est le miroir du langage des préfixes de $Mir(\mathcal{L}_1)$. Il en résulte donc que le langage des suffixes d’un langage rationnel est un langage rationnel.

$7)$ On remarque que les facteurs d’un mot correspond à l’ensemble des préfixes de ses suffixes. On a donc : \[Fac\left(\mathcal{L}_1\right) = Pre\left(Suf\left(\mathcal{L}_1\right)\right)\] Il en résulte que le langage des facteurs d’un langage rationnel est un langage rationnel.

$8)$ On pose $\Delta$ une fonction de $\left(Q \times Q’\right) \times \Sigma$ dans $\mathcal{P}\left(Q \times Q’\right)$ l’ensemble des parties de $Q \times Q’$ et définie par : \[\Delta((q,q’),a) = \left\{\;(r,q’)\;|\;\delta(q,a) = r\;\right\} \bigcup \left\{\;(q,r’)\;|\;\delta'(q’,a) = r’\;\right\} \] On a $\mathcal{L}_1\#\mathcal{L}_2$ est reconnu par l’automate non déterministe suivant : \[\mathcal{A}_{\#} = \left(\Sigma,\;Q \times Q’,\;\{(q_0,q’_0)\},\;F \times F’,\; \Delta \right) \] Ainsi, les langages rationnels sont stables par mélange de mots.

$9)$ Le principe de l’automate qu’on va construire ici est de simuler la lecture de notre mot d’entrée en partant de tous les états à la fois. Ainsi, une fois qu’on aura terminer de lire notre mot, on pourra directement le lire une seconde foi. L’ensemble d’états qui nous intéresse est donc $Q^{n}$ où $n$ est le nombre d’états de l’automate. Notre état initial est $(q_0,q_1, \ldots, q_{n-1})$ où les $q_i$ sont les états de $Q$ numérotés de $0$, l’état initial, à $n$. Notre fonction d’état $\delta_n$ est donnée par : \[\delta_n((p_0,\ldots,p_{n-1}),a) = (\delta(p_0,a), \ldots, \delta(p_{n-1},a))\] L’ensemble des états finaux $F_{\sqrt{\;}}$ est l’ensemble des $(p_1, \ldots, p_n)$ tel que $p_1 = q_i$ et $p_{i} \in F$. Autrement dit on regarde dans quel état on se trouve après avoir lu $w$ et on en déduit où on termine après avoir lu $ww$. Ainsi l’automate $\mathcal{A}_{\sqrt{\;}}$ suivant reconnaît bien $\displaystyle \sqrt{\mathcal{L}_1}$ : \[\mathcal{A}_{\sqrt{\;}} = \left(\Sigma,\;Q^{n},\;(q_0,q_1,\ldots,q_{n-1}),\;F_{\sqrt{\;}},\;\delta_n \right)\] Les langages rationnels sont stables par racine carrée.

$10)$ On procède de même que pour la racine carrée excepté qu’on utilise un automate non déterministe. Cette fois-ci, on s’intéresse à tous les états accessible à partir de chaque état. Notre automate a pour ensemble d’état $Q^{n+1}$. Notre fonction d’état $\delta_{n+1}$ est donnée par : \[\delta_{n+1}((p,p_0,\ldots,p_{n-1}),a) = \{\;(\delta(p,a),\delta(p_0,x_1), \ldots, \delta(p_{n-1},x_n)\;|\;\exists x_1,\ldots,x_n \in \Sigma\;\}\] L’ensemble d’états finaux est l’ensemble des $(p,p_1,\ldots,p_n)$ tel que $p=p_i$ et $p_i \in F$. Enfin, l’ensemble d’états initiaux est $\{(q_0,q_0,q_1,\ldots,q_n)\}$. Ainsi, les langages rationnels sont stables par moitié.

La fonction d’Ackermann

Ici on s’attaque à un des exercices les plus classiques en matière de terminaison d’algorithme. On présente une fonction récursive et le but est de montrer qu’un algorithme calculant cette fonction termine.

Exercice

La fonction d’Ackermann est une fonction de $\mathbb{N}^{2}$ dans $\mathbb{N}$ et est définie par : \[A(m,\:n) = \begin{cases} n+1& \text{ si }m=0\\ A(m-1,\:1) & \text{ si }m\gt 0 \text{ et }n=0\\ A(m-1, A(m,\:n-1)) & \text{ si }m\gt 0 \text{ et }n\gt 0 \end{cases}\]

$1)$ Munir $\mathbb{N}^{2}$ d’un ordre bien fondée.

$2)$ En déduire que la fonction d’Ackermann est bien définie.

Correction

$1.$ Considérons l’ordre lexicographique $\lt_{lex}$ définie par :
\[(x,y) \lt_{lex} (x’,y’) \Leftrightarrow x\lt x’ \text{ ou } ( x=x’ \text{ et } y\lt y’ )\]

Prouvons que cet ordre est bien fondée. Nous proposons deux méthodes utilisant les deux définitions équivalentes de l’ordre bien fondée.

Première méthode : montrons qu’il n’existe pas de suite infinie strictement décroissante Par l’absurde, supposons qu’une telle suite existe. Appelons-là $\displaystyle (u_n)_{n\in\mathbb{N}}$. Soit $u_0 = (x,y)$. On note que les éléments de $(u_n)$ sont de la forme $(k,k’)$ avec $0 \leq k \leq x$. Notre suite étant infinie et le nombre de possibilité pour le premier élément étant finie, on a $K \in \mathbb{N}$ tel qu’on ait une infinité d’élément de $(u_n)_{n\in\mathbb{N}}$ de la forme $(K,k’)$. Ainsi, on a $\varphi$ une extractrice de $\mathbb{N}$ telle que la suite $(u_{\varphi(n)})$ soit strictement décroissante et n’ait que des valeurs de la forme $(K,k’)$. On pose $u_{\varphi(0)} = (K,K’)$. Or, nous n’avons que $K’+1$ éléments distincts compris entre $(K,K’)$ et $(K,0)$, ce qui contredit l’hypothèse de stricte décroissance. Ainsi, $\lt_{lex}$ définit bien un ordre bien fondé sur $\mathbb{N}^{2}$.

Deuxième méthode : montrons que pour tout sous ensemble de $\mathbb{N}^{2}$, il existe un élément strictement minimal au sens de l’ordre $\leq_{lex}$. Pour cela, il suffit de considérer un ensemble de $\mathbb{N}^{2}$ et de considérer le sous-ensemble constitué des éléments dont le premier élément du $2$-uplet est minimale. Puis, on prend le plus petit élément dans cet ensemble par rapport à la seconde composante, ce qui est possible dans les deux cas car $(\mathbb{N},\lt )$ est bien fondée. On a bien exhibé un plus petit élément, donc $(\mathbb{N}^{2},\lt_{lex})$ est bien fondé.

$2)$ Prouvons à présent que la fonction d’Ackermann est bien définie. On peut considérer notre définition comme un algorithme récursif et la question est alors de savoir si notre programme termine. Pour le prouver, on procède par induction sur l’entrée.

Tout d’abord, si $m=0$, $A(m,n)$ termine en une étape.

Soit $(m,n) \in \mathbb{N}^{*}\times\mathbb{N}$. On suppose que la fonction d’Ackermann termine sur tout $(k,l)\lt_{lex}(m,n)$. Montrons qu’elle termine sur l’entrée $(m,n)$. Si $n=0$, Ackermann termine sur $(m-1,1)$ donc termine sur $(m,n)$. Sinon, par hypothèse d’induction, $A(m,n-1)$ existe et le calcul termine. De plus $(m-1,A(m,n-1))\lt_{lex}(m,n)$. Ainsi, toujours par hypothèse d’induction, notre fonction termine sur l’entrée $(m-1,A(m,n-1))$ et donc termine sur $(m,n)$. Cela prouve donc le cas $(m,n)$ et achève la récurrence.

Nous avons donc prouvé que la fonction d’Ackermann est bien définie.

La fonction 91 de McCarthy

Exercice

On définit la fonction récursive suivante due à McCarthy. Elle prend en entrée un entier $n$ et est définie par : \[f(n) = \begin{cases} n – 10 & \text{ si } n \gt 100 \\ f(f(n+11)) & \text{ sinon} \end{cases}\]

On considère l’algorithme qui calcule $f(n)$ en partant de la formule de récurrence. Montrer que cet algorithme termine et donner une valeur explicite de $f(n)$ pour tout entier $n$.

Correction

Nous savons que notre algorithme termine pour tout entrée supérieur à $101$, mais nous ignorons comment il se comporte pour des entrées plus petites. On doit donc effectuer une récurrence décroissante.

Montrons par induction que f l’algorithme calculant la fonction de McCarthy termine sur toute entrée entière $n$ et renvoie $n – 10$ si $n$ est supérieur ou égale à $101$ et renvoie $91$ sinon.

On initialise notre induction pour les cas de bases $n\gt100$. Dans ce cas, la fonction de McCarthy termine bien et renvoie ce que l’on souhaite.

On suppose maintenant la propriété vraie pour tout $n \gt k$ avec $ 0 \leq k\leq100$. Montrons qu’elle le reste au rang $k$.

Si $100\geq k\geq90$ : alors $f(k) = f(f(k+11))$. Or ici, $k+11 \gt 100$ et $f(k+11)$ termine et renvoie $k+1$. Donc $f(f(k+11)) = f(k+1)$. Par hypothèse d’induction, la fonction termine sur l’entrée $k+1$. De plus, si $k=100$ alors $f(k+1)=f(101)=91$ et si $k<100$, alors $f(k)=f(k+1)=91$. Donc la fonction de McCarthy termine sur l'entrée $k$ et renvoie $91$.

Si $90 \gt k$ : On a $f(k)=f(f(k+11))$. Or, par hypothèse d’induction, $f$ termine sur l’entrée $k+11$ et renvoie $91$. Donc $f(k)=f(91)$ qui termine et vaut $91$.

Cela achève notre induction et nous permet donc de conclure que l’algorithme calculant la fonction de McCarthy termine sur toute entrée entière $k$ et est définie par :

\[f(k) =\begin{cases} n – 10 & \text{ si } n \gt 100 \\ 91 & \text{ sinon} \end{cases}\]

Coloration de Wigderson

Exercice

Le but de cet exercice est de colorer un graphe que l’on sait $3$-coloriable en utilisant le moins de couleurs possible.

$1)$ Soit un graphe $G$ quelconque de degré maximal $\Delta$. Donner une borne sur le nombre chromatique de $G$.

Soit $G$ un graphe $3$-coloriable. Pour $u$ un sommet de $G$, on note $N(u)$ l’ensemble des voisins de $u$.

$2)$ Montrer qu’on peut colorier avec $3$ couleurs en temps polynomial le sous-graphe induit par $\{u\} \bigcup N(u)$.

$3)$ En déduire un algorithme qui tourne en temps polynomial pour colorier un graphe $3$-coloriable de $n$ sommets avec $3\sqrt{n}$ couleurs.

Correction

$1.$ On propose l’algorithme suivant : on colorie chaque sommet un par un en lui attribuant la plus petite couleur non attribué à un de ses voisins. De ce fait, chaque sommet a une couleur inférieur ou égale au nombre de ses voisins plus un. Ainsi, pour un graphe $G$ de degré maximal $\Delta$, son nombre chromatique est borné par $\Delta + 1$.

On note que dans le cas du graphe complet, cette borne est atteinte. Il s’agit donc de la meilleure borne possible.

$2.$ On attribue à $u$ la couleur $1$. De plus, comme $G$ est $3$-coloriable, cela signifie que l’ensemble de ses voisins forme un graphe bipartie. Or $2$-colorier un graphe bipartie est faisable par un simple parcours. On a donc colorié notre sous-graphe avec trois couleurs en un temps polynomial.

$3.$ Soit $n$ le nombre de sommets de notre graphe. On propose l’algorithme récursif suivant : on cherche le sommet $s$ de degré maximal. Si ce degré est strictement inférieur à $\sqrt{n}$ on peut colorier le graphe avec $\sqrt{n}$ couleurs. Sinon, on considère ses voisins qui forment donc un graphe bipartie. On les colorie avec $2$ couleurs qu’on ne réutilisera plus. On supprime les sommets coloriés du graphe et on recommence. On effectue au plus $\sqrt{n}$ passage dans la boucle. Dans chaque passage, on utilise $2$ nouvelles couleurs, soit $2\sqrt{n}$ au total. Enfin, on passe au plus une fois dans le cas où on colorie utilisant $\sqrt{n}$ couleurs.

Notre algorithme permet donc bien de colorier un graphe $3$-coloriable avec $3\sqrt{n}$ couleurs.

Cette approximation a été proposée par Wigderson. Khanna, Linial et Saffra ont montré en 1993 que le problème de colorier un graphe qu’on sait $3$-coloriable avec $4$ couleurs est NP-difficile.

Sudoku #2

Sudoku haché

Résoudre en ligne !

Les règles habituelles du sudoku s’appliquent. Le long des flèches, la somme des entiers est divisible par le nombre le plus proche de la flèche. De plus, le long d’une flèche, tous les nombres sont différents. Enfin, la somme des cellules le long de la triple flèche est divisible par le cube du nombre le plus proche de la triple flèche.

Bonne chance !

Mot croisé cryptique #2

Horizontal

1 : Beaucoup de centaures décapités $(4)$ — Drogue d’une pauvre à moitié enceinte $(5)$

2 : Arrêté, ce con donnera un cocktail $(10)$

3 : Un bouleversement austère $(2)$ — Possède un peu d’ail $(2)$ — Note pour s’arrêter au bon endroit $(2)$

4 : Maladie de la roue d’un moine dans tous ses états $(9)$

5 : Endort des équidés, une boisson que tu tises mal $(12)$

6 : Trouée après le soutien $(5)$ — Tes changements au tennis $(3)$

7 : Moche bout de faim, plat sur la table $(10)$

8 : Menuisier que tu bénis pendant l’été $(8)$ — Eau d’une autre lettre $(3)$

9 : Démangeaison qui recuirait la salade $(9)$ — Période du mi-dimanche $(2)$

10 : Début de descente du prix d’une lettre $(2)$ — L’intelligence de vider quoi $(2)$ — Nous sommes au centre d’un cercle $(2)$ — Tissu remontant l’Égypte $(3)$

11 : Réservé le milieu d’une alouette $(4)$ — Neurone éventré en son sein $(4)$

12 : Frappa caché dans une classe nationale $(6)$ — Organe avec presque rien $(4)$

Vertical

A : Imbécile, gâteux complexé et perturbé, infectieux $(10)$

B : Milieux de nombres puérils en orée $(8)$

C : On renverse un drame lyrique $(2)$ — Autorise un remous trempé $(6)$ — On sécurise au début un imprévu $(2)$

D : Danse d’argentins qui coupe une querelle modifié $(12)$

E : Médecin dont l’identité modifié incorpore ses collègues innomés $(11)$

F : Exclamation à la limite horrible $(2)$ — Bruit sceptique au milieu du brouhaha $(2)$ — Douane très sévèrement arriéré et débutante $(3)$

G : Le menu ornait étrangement la liste $(11)$

H : Route nationale un peu radioactive $(2)$ — Osciller au bout dans le corps $(2)$ — Flouer, enrober un ordre asséché $(6)$

I : Pivot de ruban nippon interdit $(5)$ — En bouscule pas $(2)$

J : Ne retourne qu’à l’intérieur $(2)$ — Rivière au remous tissé $(5)$ — Pièces proche d’une île $(3)$

K : Décréter l’amoindrissement d’une coupe $(5)$ — Détesté à l’ouest d’une île des Caraïbes $(3)$

L : Personnage devançant Edd $(3)$ — Présent en étrange entrée avec aversion $(7)$

Solution ici !

Formule de Cayley

Exercice

La formule de Cayley affirme que pour $n \gt 1$, le nombre $C_n$ d’arbres qu’on peut construire sur $n$ sommets est $n^{n-2}$.

Le matrix tree theorem ou théorème de Kirchhoff, déjà présenté en exercice, nous permet de calculer directement cette valeur.

$1)$ Prouver la formule de Cayley à l’aide du Matrix Tree Theorem.

Une autre preuve, due à Jim Pitman, consiste en une preuve par double dénombrement.

On cherche à dénombre de deux façons différentes le nombre $D_n$ de façon d’ajouter consécutivement $n-1$ arêtes orientées au graphe nul à $n$ sommets : le graphe $G_n$ à $n$ sommets sans arêtes.

On commence par un dénombrement à partir d’arbres orientés.

$2)$ À partir d’un arbre non orienté sur $n$ sommets, expliquer comment obtenir un arbre orienté.

$3)$ En déduire une méthode en partant d’un arbre non orienté pour trouver plusieurs manières d’ajouter $n-1$ arêtes orientées à $G_n$.

$4)$ Montrer qu’utiliser cette méthode à partir de tous les arbres non orientés permet d’obtenir chaque construction possible une et une seule fois.

$5)$ Exprimer $D_n$ en fonction de $C_n$ et $n$.

On effectue maintenant un comptage directe.

$6)$ Combien compte-t-on de composante connexes après avoir ajouté $k \lt n$ arêtes à $G_n$ ?

$7)$ Après avoir ajouté $k \lt n-1 $ arêtes à $G_n$, combien de possibilité reste-t-il pour placer la prochaine ?

$8)$ En déduire une expression de $D_n$ ne dépendant que de $n$.

$9)$ Calculer $C_n$.

Correction

$1.$ Le nombre d’arbres non-orientés pouvant être construits sur $n$ sommets correspond au nombre d’arbre couvrant du graphe complet à $n$ sommets. Soit $L$ la matrice de dimension $n-1 \times n-1$ avec des $n-1$ sur la diagonale, et des $-1$ partout ailleurs. On a donc par le théorème de Kirchhoff :

\[C_n = \det\left(L\right)\]

\[C_n = \begin{vmatrix} n-1 & -1 & -1 & \cdots & -1 \\ -1 & n-1 & -1 & \cdots & -1 \\ \vdots & -1 & -1 & n-1 & \dots & -1\\ \vdots & \ddots & \ddots & \vdots \\ -1 & -1 & -1 & \cdots & n-1\end{vmatrix}\]

On soustrait à chaque colonne autre que la première la première colonne :

\[C_n = \begin{vmatrix} n-1 & -n & -n & \cdots & -n \\ -1 & n & 0 & \cdots & 0\\ -1 & 0 & n & \ldots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ -1 & 0 & 0 & \cdots & n\end{vmatrix}\]

On ajoute maintenant à la première ligne les $n-2$ suivantes.

\[C_n = \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 \\ -1 & n & 0 & \cdots & 0\\ -1 & 0 & n & \ldots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ -1 & 0 & 0 & \cdots & n\end{vmatrix}\]

En développant par rapport à la première ligne, on obtient bien :

\[C_n = n^{n-2}\]

$2.$ Un arbre composé d’arêtes orientées est un arbre enraciné. Ainsi, en partant d’un arbre non orienté, choisir un de ses sommets comme racine suffit à définir un arbre orienté.

$3.$ En partant d’un arbre non-orienté, on commence par l’enraciner, puis on choisit l’ordre d’insertion des arêtes. Cela nous donne une façon de construire un arbre orienté à partir de $G_n$ en ajoutant successivement les arêtes.

$4.$ On commence par noter qu’à partir d’un même arbre, toutes les constructions obtenues sont distinctes. De plus, si on supprime l’orientation des arêtes de l’arbre obtenu, on retrouve l’arbre de départ. De ce fait, toutes nos constructions sont distinctes. Enfin, si on considère une construction, on note qu’on peut l’obtenir à partir de l’arbre final auquel on a supprimé l’orientation. Ainsi, nous obtenons bien toutes les constructions une et une seule fois.

$5.$ Pour chaque arbre, on dispose de $n$ choix possible pour la racine. De plus, il existe $(n-1)!$ ordre différents pour la sélection des arêtes. Autrement dit $\displaystyle D_n = C_n n!$.

$6.$ On note que $G_n$ comporte $n$ composantes connexes distincts, tous composés d’un unique sommet. À la fin de la construction, il nous reste plus qu’un arbre. De plus, ajouter une arête diminue au plus le nombre de composantes de $1$. Or, on ajoute $n-1$ arêtes. Il en résulte qu’après avoir ajouté $k \lt n$ arêtes, il reste $n-k$ composantes connexes.

$7.$ On rappel qu’un arbre enraciné, est un graphe acyclique tel que tous les sommets sauf un ont un degré entrant de $1$. Lors de notre construction, on doit donc conserver le caractère acyclique et que chaque sommet ait au plus $1$ parents.

Ainsi, après avoir placé $k \lt n-1$ arêtes dans $G$, on dispose de $n-k$ composante connexe. Chacune de ces composante connexes possède un unique élément sans arête entrante. En effet, tous les sommets ont degré entrant au plus $1$ et pour assurer la connexité, la composante est constitué d’au moins autant d’arête que le nombre de sommets moins un.

De ce fait, pour ajouter une arête, on peut sélectionner n’importe quel sommet comme parent, et pour l’enfant, on doit nécessairement sélectionner une autre composante connexe. Or dans chaque autre composante connexe, il existe un unique sommet ayant degré entrant nul. De ce fait, pour chaque sommet, on peut le connecter à exactement $n-k-1$ arêtes.

Autrement dit, après avoir placé $k$ arêtes, il y a $n(n-k-1)$ possibilités pour sélectionner la prochaine arête.

$8.$ On peut donc exprimer $D_n$ sous forme d’un produit.

\[D_n = \prod\limits_{k=0}^{n-2} n(n-k-1)\]

On sort les $n$ du produit.

\[D_n = n^{n-1}\prod\limits_{k=0}^{n-2} (n-1-k) \]

Donc on reconnaît l’expression de la factorielle. Ce qui nous permet donc d’exprimer $D_n$.

\[D_n = n^{n-1}(n-1)!\]

$9.$ On réunit donc les deux formules de $D_n$.

\[C_n n! = n^{n-1}(n-1)!\]

Ce qui nous donne donc bien :

\[C_n = n^{n-2}\]

Sudoku #1

Sudoku au carré

sudoku_carre

Résoudre le sudoku en ligne.

Les règles habituelles du sudoku s’appliquent. On ajoute la règle suivante relative aux zones vertes.

  • Chaque case appartient à exactement une zone verte délimitée par un encadré vert.
  • Au sein d’une même zone verte, tous les nombres sont distincts.
  • La somme des nombres à l’intérieur d’une zone verte est toujours égale à un entier au carré (par exemple, 25, 36, 81…)

Bonne chance !

Mot croisé cryptique #1

Horizontal

1 : Pourtant dans le port $(2)$ — L’excitation de secouer un flacon $(5)$

2 : Piège le son d’un DJ et de sa flûte $(4-5)$

3 : Prêt à attaquer un parent $(4)$

4 : Piste des extrémités de l’apéro proche de Valence $(9)$

5 : Langue interne d’un hibou $(3)$ — Désigne la compression d’une entrée de conflit $(4)$

6 : Empereur dans tous ses états couronné $(5)$ — Mousse en bordure d’une pièce $(3)$

7 : Arbres s’emmêlant dans les cieux $(6)$ — À couper pour cela $(2)$

8 : Dans un déferlement cranté $(7)$

9 : Tu doserais, confus, ce que tu me dois $(8)$

Vertical

A : Terres des finales anglaises $(7)$

B : Soit chez nous $(2)$ — À table sans elle, un plaisir renversant $(4)$

C : Blâmer un ami dans le métro $(9)$

D : Se débarrassa du flou d’un principe $(3)$ — Redonne de l’ordre à ce dîner sans complexe $(4)$

E : Poudre d’un froussard pincé $(4)$ — Donc le sang bouleverse $(4)$

F : Opéra amputé et greffé et donc soigné $(5)$ — Titre hindou du crépuscule renversant des soirs $(3)$

G : S’inverse à Madrid $(2)$ — Interjection pour prendre son café dans l’arène $(3)$ — Se renverse avant le centième élément $(2)$

H : Archives d’une limace chamboulée et peu gentille $(9)$

I : Tu existes vers l’aube $(2)$ — Sondage désuet, truqué $(6)$

Solution ici !