CCINP Informatique optionnelle MP 2021

Corrigé

(c'est payant, sauf le début) : - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


SESSION 2021 @ MP7IN

CONCOURS
COMMUN
INP

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH

ÉPREUVE SPÉCIFIQUE - FILIÈRE MP

INFORMATIQUE

Durée : 4 heures

N.B. : le candidat attachera la plus grande importance à la clarté, à la 
précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur 
d'énoncé, il le signalera sur sa copie
et devra poursuivre sa composition en expliquant les raisons des initiatives 
qu'il a été amené à prendre.

RAPPEL DES CONSIGNES

«_ Utiliser uniquement un stylo noir ou bleu foncé non efjaçable pour la 
rédaction de votre composition ; d'autres
couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les 
schémas et la mise en évidence

des résultats.
° Ne pas utiliser de correcteur.
«_ Écrire le mot FIN à la fin de votre composition.

Les calculatrices sont interdites.

Le sujet est composé de trois parties indépendantes.

1/11
Partie I- Étude des partitions non croisées

Dans cette partie, on introduit et on étudie de façon élémentaire les 
partitions non croisées, objets com-
binatoires apparaissant dans divers domaines des mathématiques, notamment dans 
la théorie des proba-
bilités libres et des matrices aléatoires.

Le langage de programmation utilisé dans cette partie est le langage Python.

Dans la suite, pour tout couple (i,n) EUR N°, les notations [n] et [i,n] 
désignent respectivement les en-
sembles {1,2,...,n} et {i,i+1,...,n}. Par convention, [0] = Y et si i > n alors 
[i,n] = 0.

Définition 1 (Partition)
Soit À un sous-ensemble non vide de N. Une partition ? de À est un ensemble de 
parties de À tel que :

1. VPEP,P40:; 2. VPO)EP?,(P£OQ) -- (PNnO=0): 3. | JP=A.
PEP
Par exemple, {{2, 4,5},{7,9},{8}} est une partition de l'ensemble {2, 4, 5, 7, 
8,9}.

Définition 2 (Classe)
Soit P une partition d'un sous-ensemble À non vide de N. Soit : un élément de 
À. La classe de : est
l'unique élément P de F tel que 1 EUR P. Elle est notée CI(:).

Par exemple, pour P = {{2,4,5},{7,9},{8}}, on a CI(4) = {2,4, 5}.

Définition 3 (Partition non croisée)
Soit P une partition d'un sous-ensemble À non vide de N. On dit que F est non 
croisée si pour tout
quadruplet (a, b, c, d) EUR A* tel que a < b  (CI(a) = CI(b) = CI(c) = CI(d)).

Par exemple, P = {{2,4,5},{7,9},{8}} est bien une partition non croisée de {2, 
4,5,7,8,9}. En efïtet,
aucun quadruplet (a, b, c, d) EUR {2,4,5,7,8, 9) tel que a < b < c < d'ne vérifie la condition Cl(a) = CI(c), CI(b) = Cd). De même, Q = {{2,7,8,9}, {4,5}} en est bien une. En effet, (a, b, c,d) = (2, 7,8, 9) est l'unique quadru- plet tel que a < b < c < d vériñant Cl(a) = CI(c), CI(D) = CI(d) et ces quatre éléments sont bien dans la même classe. Par contre, R = {{2,5},{4,7,9},{8}} n'en est pas une. En effet, CI(2) = CI(S) et CI(4) = CI(7) mais CI(2) 4 CI(4). Le terme « non croisée » découle naturellement des représentations picturales des partitions (figure 1). Figure 1 - Représentations picturales de P, Q,R 2/11 Dans la suite, on s'intéresse uniquement aux partitions d'un sous-ensemble fini de N. On les représente en Python à l'aide de listes de listes croissantes d'entiers triées dans l'ordre lexicographique. Par exemple, les partitions P = {{2,4,5},{7,9},{8}} et R = {{2,5},{4,7,9},{8}} sont respectivement représentées par les listes P = [[2,4,5],[7,91,[8]]etR = [[2,5],[4,7,91,[8]1]. L.1 - Exemples et fonctions élémentaires (Informatique Pour Tous) Q1. Justifier brièvement que P = {{1,7},{2},{3,4,5},{6}} est une partition non croisée de [7] et que Q = {{1,6},{2},{3,4,5,7}} n'en est pas une. Q2. Parmi les ensembles suivants, indiquer sans justification lesquels sont des partitions de [5]. Parmi les partitions, préciser sans justification lesquelles sont non croisées. 1 P1 ={{1,3},{2,4,5}}, 2. P, = {1,3},{1,2},{4,5}}, 3. P3 = {{1,3}{2,4}}, 4, Pa = {1,4,5},{2,3}}. Q3. Décrire l'ensemble des partitions non croisées de [41]. Pour Q4, QS et Q6, on se fixe un ensemble fini À EUR N. Cet ensemble est représenté en Python par la liste croissante d'entiers À, définie au préalable. On suppose également que pour ces questions, la variable P désigne une liste de listes croissantes d'entiers triée dans l'ordre lexicographique. On définit la fonction Python mystere(P) par : def mystere(P) L = [False for _ in range(len(A))] for 1 in range(len(P)) If PI[1] == {| return False else for j] in range(len(Pf1l])) if P[i][j] not in A : return False else # A.index(a) renvoie l'indice de a dans A Kk = A.index(P[1][]l]) if LIKk] return False else LIKk] = True return not (False in [L) Q4. Uniquement dans cette question, on suppose que À = [1,2,3,4,5]. Expliciter sans justification les valeurs de : 1. mystere([[1,3],[1,5],[2,4]]) 2. mystere([[1,3,4],[2]1]) 3. mystere([[1,3,5],[2,4]1]) 4, mystere([[1,[1,2,3,4,5]]). Q5. Écrire une fonction Python classe(P,i) prenant en arguments une variable P représentant une partition Y de À et un entier i EUR À qui renvoie une liste L représentant CI(i). 3/11 On définit la fonction Python au code incomplet est_nc(P) suivante : def est _nc(P) # On rappelle que À est une liste triée dans l'ordre croissant N = Ilen(A) for 1 in range(N) for J in range(1+1l,N) for K in range(]j+1,N) for 1 in range(k+1,N) Q6. Recopier et compléter le code de la fonction est_nc(P), sachant qu'elle prend en argument une variable P représentant une partition P de À et qu'elle renvoie True s1 P est non croisée et False sinon. 1.2 - Nombre de partitions non croisées Pour tout n > 1, on note C, le nombre de partitions non croisées d'un ensemble 
À EUR N ayant exac-

tement n éléments et NC(A) l'ensemble des partitions non croisées de A. Par 
convention, Co = 1
et NC(0) = {0}.

Définition 4 (Partition non croisée emboîtée)

Soient À un ensemble fini de N de cardinal n et P une partition non croisée de 
À. On dit que ? est em-
boîtée si le minimum m et le maximum M de À sont dans la même classe (Cl(m) = 
CI(M)). L'ensemble
des partitions non croisées et emboîtées de À et son cardinal sont 
respectivement notés NCE(A) et D,.

Par exemple, S = {{1,2,5,9},{3,4}, {6,7, 8}} est une partition non croisée et 
emboîtée de [9].

Le terme « emboîtée » découle naturellement des représentations picturales des 
partitions (figure 2).

Figure 2 - Représentations picturale de S

Q7. Montrer que pour toutn eN,onaC, = D,:1.

QS. Soit n EUR N. On définit l'application D, comme suit :

n+]

D,: | JNCE(DXNC(i+Ln+1]) -- NC(n+1])

i=1
(Q1, Q) k Qi U OO».

n
En admettant que ®, est une application bijective, montrer que C,:1 = > CrCn-k-
k=0

Q9. (Informatique Pour Tous) Écrire une fonction Python calcul_C(n) qui prend 
en argument un
entier naturel n et qui renvoie la valeur C,.

4/11
Partie II - Logique et étude du problème Horn-Sat

Dans cette partie, A, V, --, désignent respectivement les connecteurs de 
conjonction, de disjonction et de
négation. Les symboles V, F désignent respectivement les valeurs de vérité VRAI 
et FAUX du calcul
propositionnel.

Dans la suite, on s'intéresse au problème Horn-Sat, qui peut être décrit de la 
façon suivante : étant
donnée une formule de Horn P, existe-t-1l une interprétation J telle que [P]; = 
V ?

L'objectif est d'expliciter un algorithme permettant de résoudre ce problème.

Définition 5 (Formule propositionnelle)
Soit X un ensemble de symboles appelés variables propositionnelles. Les 
formules propositionnelles
sur À sont alors définies de façon inductive comme suit :

- V,F sont des formules propositionnelles ;

- tout élément x de X est une formule propositionnelle ;

- si P et Q sont des formules propositionnelles, alors --P, (P A O),(P V ©) 
sont des formules pro-
positionnelles.

Dans la suite, les variables propositionnelles et formules propositionnelles 
considérées sont construites
à l'aide d'un ensemble X qui ne sera pas explicité.

Définition 6 (Littéral)
Soit x une variable propositionnelle. Un littéral est la formule x ou la 
formule -x. Le littéral x (respec-
tivement --x) est un littéral positif (respectivement négatif).

Définition 7 (Clause disjonctive)

Soient ñn EUR N, x1,x2,...,x, des littéraux. La formule x; V x V ... V x, est 
appelée clause disjonctive à
n littéraux (ou de taille n). Par convention, () désigne la clause disjonctive 
vide, c'est-à-dire la clause
sans littéral.

Une clause de Horn est une clause disjonctive contenant au plus un littéral 
positif.
Une clause unitaire est une clause composée d'un unique littéral.

Définition 8 (Forme normale conjonctive)

Soit P une formule propositionnelle. On dit que P est une forme normale 
conjonctive s'il existe un
entier n EUR N, Ci, C2,...,C, des clauses disjonctives vérifiant P = C3 À C3 À 
... À C,. Par convention,
une forme normale conjonctive sans clause est représentée par Ü.

Définition 9 (formule de Horn)
Soit P une formule propositionnelle. On dit que P est une formule de Horn s'il 
existe n EUR N, Ci, C,...,C;
des clauses de Horn vérifiant P = CAC A...AC,.

Définition 10 (Interprétation)
Soient n EUR N et x1,X2,...x, des variables propositionnelles. Une 
interprétation est une application
L: {X1, X, . . . ; Xn} mn {V,F}.

Définition 11 (Évaluation)

Soient P une formule propositionnelle, x:,x2,...,2x, les variables 
propositionnelles apparaissant dans P
et / une interprétation sur {x1,x2,...,x,}. L'évaluation de P suivant 
l'interprétation 7 que l'on note [P];
est définie par récurrence de la façon suivante :

5/11
- S PE {V,F}, alors [P]; = P;

- SP E{X,,x2,...,Xx,}, alors [P]; = I(P);

- Si P = -Q où Q est une formule propositionnelle, alors [P]; = -[Q];;

- S P = A0 B où À,B sont des formules propositionnelles et o EUR {A, V}, alors 
[P]; = [A]; o [B;.
Par convention, [0]; = F et [Y]; = V.

Définition 12 (Satisfiable)
Soit P une formule propositionnelle. On dit que P est satisfiable s'il existe 
une interprétation J telle que
[P | I -- V.

Q10. Pour chacune des formules suivantes, montrer qu'elle est satisfñable ou 
qu'elle est non satisfable.

LP = (XV) AGXV=y) A (XV =), 2. P3 = (x) A (x V =y) A (y V2) A (2),
3. P3 =0(, 4. Pa =(XV-YV =) AVE V x V -y).

Q11. Parmi les fomules de la Q10, lesquelles sont des formules de Horn ? On ne 
justifiera pas la
réponse.

Définition 13 (Propagation unitaire)
Soit P une forme normale conjonctive contenant une clause unitaire (x). On 
construit une formule P" à
partir de P de la façon suivante :

1. supprimer de P toutes les clauses où x apparaît ;
2. enlever toutes les occurrences du littéral -x.
Cette procédure de simplification est appelée propagation unitaire.

Par exemple, si P = (x V -y V z) À (-x V y V z) A (x), on a alors P" = (y Vz). 
Si P = (x) A(-x),;ona
alors P" = ().

Dans la suite, on note II(P) une formule sans clause unitaire obtenue en 
itérant la propagation unitaire
sur P. On admet que si IT(P) ne contient pas de clause vide () alors IT(P) est 
unique et que s1 IT(P)
contient au moins une clause vide alors toute formule sans clause unitaire 
obtenue par itération de la
propagation unitaire sur P contient au moins une clause vide.

Q12. On pose :

P = (x) A (x V x V x) À (x V %3 V X4) À (x V 1%) À (=X2 V x] V %3)
À (2%3 V =Xxa V Xs) À (2x1 V X2 V Xs).

Calculer IT(P). On pourra donner le résultat directement sans détailler les 
calculs.

Q13. Soit P une formule de Horn. Montrer que II(P) est une formule de Horn.
Q14. Soit P une forme normale conjonctive. Montrer que P est satisfñable s1 et 
seulement si II(P) est
satisfable.

Q15. Soit P une forme normale conjonctive. Montrer que si () apparaît dans 
II(P), alors P n'est pas
satisfable.

Q16. Soit C une clause de Horn. Montrer que si C n'est n1 la clause vide n1 une 
clause unitaire positive,
alors C est satisfable.

Q17. Soit P une formule de Horn ne contenant ni de clause vide n1 de clause 
unitaire positive. Montrer
que P est satisfiable.

Q18. Soit P une formule de Horn. Montrer que P n'est pas satisfable si et 
seulement si () apparaît
dans II(P).

6/11
Partie III - Étude des classes sylvestres

Étant donné un arbre binaire de recherche T,, sa classe sylvestre est 
l'ensemble des mots qui donnent
l'arbre T' après insertion dans l'arbre vide. L'objectif de cette partie est de 
donner une caractérisation et
une description de cet ensemble. On commence par rappeler la structure des 
arbres binaires de recherche
ainsi que leurs propriétés usuelles. Puis, on introduit la notion de 
S-équivalence sur les mots qui permet
de caractériser la classe sylvestre d'un arbre T. Enfin, à l'aide du produit de 
mélange, on présente un
algorithme calculant la classe sylvestre d'un arbre donné.

Dans toute la suite, Z désigne un alphabet fini totalement ordonné. Le symbole 
& désigne le mot vide.

III. 1 - Algorithme d'insertion dans un arbre binaire

Définition 14 (Arbre binaire)
Un arbre binaire 7 (étiqueté par les éléments de Y) est récursivement soit :

- l'arbre vide que l'on note o;
- un triplet (7,,r, Ta) où r est un élément de », T, et 7, des arbres binaires. 
Les éléments 7, T, et Ta
sont respectivement appelés racine, sous-arbre gauche et sous-arbre droit de T.

Définition 15 (Arbre binaire de recherche)
Un Arbre Binaire de Recherche (abrégé en ABR) T est récursivement soit :

- l'arbre vide:

- un triplet (T,,,r, Ta) où r est un élément de », T, et T, des ABR. De plus, 
toute valeur apparaissant
dans 7, est strictement inférieure à r et toute valeur apparaissant dans T, est 
supérieure ou égale
à r.

Définition 16 (Insertion dans un arbre binaire)
L'insertion d'un élément a de Z dans un arbre binaire T est une opération que 
l'on note T + a définie
récursivement comme sui :

- ST =0,alors T -- a=(0,a,0);
- ST =(T,;r, Tyetr a, alosT -», als TT - char arbre -> char arbre

et telle que insertion_lettre a t est l'arbre binaire obtenu en insérant la 
lettre a dans
l'arbre binaire t.

Q21. Ecrire une fonction récursive en Ocamil de signature :
insertion _ mot : char list -> char arbre -> char arbre
et telle que insertion_mot w t est l'arbre binaire obtenu en insérant le mot w 
dans l'arbre

binaire t.

Définition 18 (Lecture préfixe)
Soit T un arbre binaire. La lecture préfixe de T que l'on note w7 est le mot 
défini récursivement par :

- si Î = o, alors wr = EUR;
- ST = (T,,r, Ta), alors wr = rw,wa où w, et w, sont les lectures préfixes 
respectives de T, et de
Ta.

8/11
Q22. Expliciter wr pour l'arbre binaire T représenté ci-dessous :
S
y TT
N V

7° \ /

O O

\

Ê

/\ À

/

O

4 MN,
\ \  /

Figure 4 - Représentation de T de Q22

Q23. Ecrire une fonction récursive en Ocamil de signature :
prefixe : char arbre -> char list

et telle que prefixe t est le mot qui correspond à la lecture préfixe de 
l'arbre t.

Q24. Soit T un ABR, soit w7 la lecture préfixe de T. Montrer que T est l'ABR 
associé à wr.
IIL.2 - Une relation d'équivalence sur les mots

Définition 19 (S-adjacence)
Soient u et v deux mots sur Z. On dit que u est S-adjacent à v (ou que u et v 
sont S-adjacents) s'il existe
trois lettres a < b < c de X et trois mots f., f), f; sur Z vérifiant : (u -- f.bfacf; et v = f.bf,caf;) ou (u -- f.bf,caf; et v = f.bf,acf;). Définition 20 (S-équivalence) Soient z et y deux mots sur Z. On dit que u est S-équivalent à v (ou que u et v sont S-équivalents) s'il existe nEN,(Wwp,W1,...,Wn) EUR OE*)" vérifiant : u = Wo,vV = Wy, VIE {0,1,...,n--1},w; est S-adjacent à w;,1. SL Q25. Montrer que la relation " être S-équivalent à " est bien une relation d'équivalence sur X*. Q26. Soient a, b,c trois lettres de Z vérifiant a < b < c. Montrer que pour tout arbre binaire de recherche T contenant au moins la lettre b, on a: T + ac =T + ca. On pourra raisonner par récurrence sur le nombre de noeuds de T. Q27. Montrer que si deux mots et v sont S-équivalents, alors les ABR (0 + u)et(o « y) sont égaux. 9/11 existe un mot w' = ruv où u (respectivement v) est un mot dont toutes les lettres sont plus petites strictement (respectivement plus grandes au sens large) que r et tels que w et w' sont S-équivalents. On note À l'ensemble des mots S-équivalents à w. Pour tout a = äpdi...4y_1 EUR À, on pose : Q28. Soit w un mot de longueur n > 1 sur », soit r la première lettre de w. On 
veut montrer qu'il

N(@a)= {Gi jefln-1fPli< ja; char list list -> char list list

et telle que ajout_lettre a liste est la liste de mots de la forme a: :w où w 
est un élément
de liste.

Écrire une fonction récursive en Ocaml de signature :
shuffle : char list-> char list -> char list list

et telle que shuffle u v est une liste contenant exactement tous les mots de w 
LL v avec
répétitions possibles d'un même mot. On devra utiliser la fonction auxihaire 
ajout_lettre et
l'opérateur de concaténation @.

Écrire une fonction récursive en Ocaml de signature :
shuffle_1l : char list list -> char list list -> char list list

et telle que shuffle_1l I m est une liste contenant exactement tous les mots de 
L 111 M où la
liste 1 (respectivement m) représente le langage L (respectivement M), avec 
répétitions possibles
d'un même mot. Seules les fonctions définies précédemment peuvent être 
utilisées en fonctions
auxiliaires.

Ecrire une fonction récursive en Ocaml de signature :
sylvestre _T : char arbre -> char list list

et telle que sylvestre_T t est une liste contenant exactement tous les éléments 
de la classe
sylvestre de t. Seules les fonctions définies précédemment peuvent être 
utilisées en fonctions
auxiliaires.

FIN

11/11

Extrait du corrigé obtenu par reconnaissance optique des caractères



CCINP Informatique optionnelle MP 2021
Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (professeur en CPGE) ; il a été
relu par Pacôme Luton (ENS Lyon) et Benjamin Monmege (enseignant-chercheur
à l'université).

Cette épreuve est constituée de trois exercices indépendants touchant chacun à
trois thématiques différentes du programme de prépa.
· Le premier exercice s'intéresse à la notion de partition emboîtée d'un 
sousensemble d'entiers. Après quelques questions élémentaires servant uniquement
à vérifier la compréhension des définitions données, on utilise le langage 
Python
pour implémenter des fonctions permettant de vérifier qu'une liste de listes 
représente dans un premier temps une partition d'un ensemble, puis une partition
emboîtée. L'exercice se termine par des questions relatives au dénombrement
de ces partitions.
· Le deuxième exercice porte sur la logique et la satisfiabilité. On définit une
classe particulière de formules sous forme normale conjonctive qui porte le nom
de formules de Horn. À l'aide d'une règle de simplification portant le nom de
propagation unitaire, on met en place une méthode permettant de décider de
manière efficace si une telle formule est satisfiable.
· Le dernier exercice a pour objet l'étude des classes sylvestres d'un arbre 
binaire
de recherche. On définit dans un premier temps l'arbre binaire de recherche
associé à un mot w, noté   w, comme l'arbre obtenu par insertion successive des 
lettres de w dans un arbre initialement vide. La classe sylvestre d'un
arbre T est alors l'image réciproque de {T} par l'application w 7- (  w).
Après l'écriture de quelques fonctions élémentaires OCaml, l'énoncé s'attache
à donner une caractérisation simple, via une relation d'équivalence, de 
l'appartenance de deux mots à une même classe sylvestre. Il s'achève sur une 
nouvelle
salve d'écriture de fonctions dont l'objectif est de calculer la classe d'un 
arbre
donné en argument.
Il s'agit d'un excellent problème de révision pour les concours. Les trois 
exercices
traitent de problématiques variées et le sujet est très bien écrit. La dernière 
partie
est assez technique mais la décomposition en de nombreuses sous-questions la 
rend
très abordable. Le seul reproche que l'on pourrait faire à cette épreuve porte 
sur son
aspect très théorique, et son faible nombre de questions de programmation, 
sachant
de plus que l'énoncé facilite tellement le travail que les codes à écrire font 
en moyenne
cinq lignes.

Indications
Partie I
3 Pour gagner du temps, chercher les partitions qui ne sont pas non croisées 
(elles
ne sont pas nombreuses).
4 La fonction mystere détermine si la liste donnée en argument représente une
partition de l'ensemble des valeurs de A.
5 Chercher l'élément i à l'intérieur de chaque liste contenue dans P.
6 À l'intérieur de la quadruple boucle, il ne reste qu'à vérifier si le 
quadruplet
(i, j, k, l) contredit la condition non croisée.
7 Construire une bijection entre les ensembles NC([[n]]) et NCE([[n + 1]]).
8 Deux ensembles finis en bijection ont même cardinal et le cardinal d'une union
disjointe (respectivement d'un produit cartésien) d'ensembles est la somme 
(respectivement le produit) des cardinaux des ensembles.
9 Calculer les valeurs C0 , . . . , Cn en utilisant la programmation dynamique.
Partie II
12 On doit aboutir à (P) = (x3  x4 ).
13 Montrer que la propriété « P est une formule de Horn » est invariante par 
application de la règle de propagation unitaire.
14 Montrer que la propriété « P est satisfiable » est invariante par 
application de
la règle de propagation unitaire.
15 On rappelle que [()]I = F quelle que soit l'interprétation I.
16 La question est mal posée donc triviale. Montrer plutôt qu'on peut 
satisfaire C
à l'aide d'une interprétation indépendante de C.
17 Utiliser l'indication de la question précédente.
18 Raisonner par double implication en utilisant l'équivalence de la question 
14 et
les résultats des questions 15 (par contraposée) et 17.
Partie III
19 Dessiner l'arbre au fur et à mesure au brouillon.
22 On doit retrouver un mot qui apparaît un peu partout dans cette partie.
23 Donner une implémentation récursive utilisant les opérateurs :: et @.
24 Il s'agit de justifier que pour tout arbre T, on a   wT = T. On pourra
raisonner par récurrence sur la hauteur ou le nombre de noeuds de l'arbre.
25 Montrer que la relation est réflexive, transitive et symétrique. On 
remarquera
que la relation « être S-adjacent à » est symétrique par définition.
26 Raisonner par récurrence sur le nombre de noeuds de l'arbre. Pour le cas 
général,
on distinguera trois cas suivant la position relative de la racine r de l'arbre 
par
rapport à a et c.
27 Justifier la propriété pour deux mots S-adjacents à l'aide de la question 
précédente.
28a Remarquer que deux mots S-adjacents ont la même longueur.

28b Remarquer que deux mots S-adjacents conservent la même première lettre.
28c Étant donnés 1 6 i < j 6 n - 1 tels que aj < r 6 ai , raisonner sur X = {s  [[ i ; j ]] | as > r}
28d Considérer cette fois X = {s  [[ 1 ; n - 1 ]] | as > r}
28e C'est la question la plus délicate du sujet. Supposer N(a) 6=  et montrer 
qu'en
permutant les lettres ak et ak+1 où (k, k + 1) est le couple de la question 28c,
alors le cardinal de N(a) diminue exactement d'une unité.
29 À ce stade du sujet, on pourra utiliser sans justification le fait que si u1 
, u2 , v1 ,
v2 sont quatre mots tels que u1 et u2 sont S-équivalents, de même que v1 et v2 ,
alors u1 v1 et u2 v2 le sont.
30 Tout a été fait aux questions 27 et 29.
31 Mélanger deux mots u et v revient à construire tous les mots w qui 
contiennent
toutes les lettres de u et toutes celles de v (comptées avec multiplicités) en
conservant l'ordre des lettres de u et des lettres de v.
33 Implémenter sous la forme d'une fonction récursive la définition 21 de 
l'énoncé.
34 Remarquer que pour tous ensembles L0 , M0 et tous mots u et v
({u}  L0 )

({v}  M0 ) = (u

v)  ({u}

M0 )  (L0

M)

et traduire cette égalité en une fonction récursive.
35 Implémenter sous la forme d'une fonction récursive le résultat admis après la
définition 22 de l'énoncé.

Publié dans les Annales des Concours

I. Étude des partitions non croisées
1 Pour la partition P, les couples d'entiers distincts appartenant à une même
classe sont (1, 7), (3, 4), (3, 5) et (4, 5). Si a < b < c < d vérifie Cl(a) = Cl(c) et Cl(b) = Cl(d), alors nécessairement a = 1, puis c = 7. Mais dans ce cas, {b, d} est inclus dans {3, 4, 5} et d < c. Par conséquent, La partition P est non croisée. Pour la partition Q, on peut remarquer que 1<5<6<7 avec Cl(1) = Cl(6) et Cl(5) = Cl(7) ce qui prouve que La partition Q n'est pas une partition non croisée. 2 Parmi les quatre exemples proposés, on distingue 2 partitions, dont une seule est non croisée. Plus précisément, · · · · P1 P2 P3 P4 est une partition qui n'est pas non croisée. n'est pas une partition. n'est pas une partition. est une partition non croisée. Si l'énoncé ne demande pas de justification, il ne faut pas chercher à en donner le jour du concours. On n'y gagnera pas grand chose mis à part un peu de bienveillance du correcteur (mais sans garantie), et on risque surtout de perdre du temps. Dans un souci pédagogique, on peut toutefois préciser dans ce corrigé que · P1 n'est pas non croisée car 1 < 2 < 3 < 4 avec 1 et 3 (respectivement 2 et 4) dans la même classe, mais pas dans une classe commune. · P2 n'est pas une partition car les parties {1, 3} et {1, 2} ne sont pas disjointes. · P3 n'est pas une partition car {1, 3}{2, 4} n'est pas égal à {1, 2, 3, 4, 5}. 3 Une partition P de [[4]] n'est pas non croisée par définition s'il existe a < b < c < d quatre entiers tels que a et c (respectivement b et d) sont dans une même classe C1 (respectivement C2 ), mais avec C1 6= C2 . Puisque [[4]] ne contient que 4 éléments, cela impose (a, b, c, d) = (1, 2, 3, 4) et P = {{1, 3} , {2, 4}}. Il n'y a donc qu'une seule partition de cette nature. Toutes les partitions de [[4]] sont non croisées, à l'exception de {{1, 3} , {2, 4}}. L'énoncé ne précise pas très clairement s'il attend que l'on dresse la liste des partitions non croisées de [[4]]. Pour ce faire, on peut ordonner les partitions de cet ensemble en fonction de leur cardinal : · Il y a une seule partition à une seule partie, c'est {{1, 2, 3, 4}}. · On distingue parmi les partitions à deux parties celles constituées de deux parties de cardinal 2 et celles constituées de deux parties de cardinal 3 et 1.