# OLA

###### tags: `Semestre 4`

[ToC]

# OLA, TD1 : Théorie des graphes

## Exercice 1 : _Degré des sommets d'un graphe_

1) La somme des degrés des sommets est égale au double du nombre d'arêtes, car chaque arrête relie 2 sommets et contribue donc de 2 à la somme des degrés.
2) La degré maximal est inférieur ou égal à la somme des degrés (car tous les degrés sont positifs) donc inférieur ou égal à 2m.
Exemple où K = 2m : toutes les arrêtes sont des boucles sur un même sommet.
3) a. $G$ graphe simple à $n$ sommets et $m$ arrêtes, alors
$$m \leq \frac{n(n-1)}{2}$$

Cette borne est atteinte pour toutes les cliques.

b. Dans un graphe simple, un sommet ne peut être relié qu'une fois à chaque autre donc au plus n-1 arêtes incidentes (boucles interdites).

## Exercice 2 : _Clique_
1) 
2) $K_{n}$ a $\frac{n(n-1)}{2}$ arêtes.
3) $K_{n}$ nécessite n couleurs. Preuve par l'absurde, on suppose qu'on a (n-1) couleurs, cela implique que 2 sommets ont la même couleur (puisqu'il y a $n$ sommets), or ces 2 sommets sont reliés par une arrête (puisque notre graphe est une clique), ça ne donne donc pas un bon coloriage.
4) 
$K_4$ est planaire = on peut le dessiner de sorte que les arrêtes ne se croisent pas

5) K5 n'est pas planaire mais un dessin ne suffit pas à le prouver. 
Cependant, d'après le théorème classique: tout graphe planaire peut être colorié avec 4 couleurs, or K5 a besoin de 5 couleurs (d'après 3)) donc K5 n'est pas planaire.

## Exercice 3 : _Coloration_
1) ensemble de sommet : les cours (= les examens)
signification du coloriage : une couleur correspond à une demi-journée. Un sommet est d'une couleur donnée si l'examen correspondant a lieu cette demi-journée là.
ensemble d'arrêtes :
$$ A = \{ \{C1,C2\} \in C² \; \mid \exists e \in E, C1 \in I(e) \; \land \;C2 \in I(e) \} $$
Les arrêtes relient les UE ayant un étudiant en commun.
2) 
On a besoin d'au moins trois couleurs (C1, C2, C3 est une clique) et 3 couleurs suffisent cf dessin, donc 3 demi-journées.

3) 

## Exercice 4 : _Coloration d'arêtes_
1) Condition : deux arêtes incidentes à un même sommet ne doivent pas avoir la même couleur.
2) On a au moins besoin d'autant de couleurs que le degré maximal d'un sommet du graphe.
3) a. C'est une clique. Donc $\frac{n(n-1)}{2}$ arêtes.
b. Au maximum n/2 matchs en même temps

c.

## Exercice 5 : _Un algorithme de coloration_
1)
Remarque : il s'agit de 2 façons de dessiner le MEME graphe (on appelle ce graphe l'étoile à 7 sommets)
2)

3)
$P_{n}$ : un graphe G à n sommets peut être coloré en n’utilisant pas plus que ∆(G)+1 couleurs.

$\underline{Initialisation}$ : Pour n = 1: Si G a 1 seul sommet, alors il peut être coloré avec 1 couleur. En effet G est un graphe simple, donc pas de boucles, donc avec 1 couleur sur le sommet, il n'y aura pas d'arrête entre 2 sommets de même couleur.

$\underline{Héredité}$ : Supposons que P(n) est vrai et montrons que P(n+1) est vrai aussi

Soit $G_{n+1}$ un graphe simple à $n+1$ sommets.
Enlevons un point quelconque de $G_{n+1}$ de sorte qu'on obtienne un autre graphe simple $G_{n}$ à $n$ sommets.
- Par hypothèse de récurrence : on peut colorier $G_{n}$ avec $\Delta(G_{n}) +1$ couleurs.
- Or $\Delta(G_{n})\leq\Delta(G_{n+1})$ ($G_n$ est obtenu à partir de $G_{n+1}$ en supprimant un sommet).
- Prenons donc un coloriage de $G_n$ avec au plus $\Delta(G_{n+1}) +1$ couleurs. Le point qu'on vient de supprimer appelons le $v_{1}$ . On a $deg(v_{1}) \leq \Delta(G_{n+1})$. On peut donc choisir la $\Delta(G_{n+1}) +1$ -ème couleur pour ce point quand on remet le point à sa place. On obtient un coloriage de $G_{n+1}$ à au plus $\Delta(G_{n+1}) +1$ couleurs, cqfd

$\underline{Conclusion}$ :
Donc un graphe $G$ à $n$ sommets peut être coloré en n’utilisant pas plus que $∆(G)+1$ couleurs.

4. Algorithme simple pour colorier les sommets d'un graphe G:
On prévoit ∆(G)+1 couleurs. On considère les sommets de G un par un. Pour chaque sommet, on lui attribue une couleur parmi celles qui n'ont pas déjà été attribuées à ses voisins. On arrivera toujours à trouver une couleur car chaque sommet a au plus ∆(G) voisins et on a prévu ∆(G)+1 couleurs.

# OLA, TD2 : Théorie des graphes

## Exercice 1 du TD2 :

1)

2) Il y a $2^n$ sommets en dimension $n$. Le degré de chaque sommet est $n$. Donc il y a $\dfrac{2^n * n}{2}$ arêtes soit $2^{n-1} * n$ arêtes.
3) Circuit Hamiltonien dans HC2: (00, 01, 11, 10, 00). Autre solution: (01, 11, 10, 00, 01) etc.
4) Supposons un circuit hamiltoninen dans HCn. Il est de la forme a1...an → ... → b1...bn → (a1...an). On ajoute un 0 au début de chaque mot. On obtient 0a1...an → ... → 0b1...bn → (0a1...an). Même chose avec un 1 devant 1a1...an → ... → 1b1...bn → (1a1...an). Il reste à mettre ces 2 cycles en un seul. On retourne le 2e cycle (on décale d'un cran si on avait répété le 1er sommet à la fin) 1b1...bn → ... → 1a1...an → (1b1...bn) et on le concatène avec le 1er. On obtient 0a1...an → ... → 0b1...bn → 1b1...bn → 1a1...an → (0a1...an).
5) HC2: (00, 01, 11, 10, 00). On ajoute des 0 devant, on obtient (000, 001, 011, 010, 000). Même chose avec des 1 devant: (100, 101, 111, 110, 100). On retourne le 2e cycle (100, 110, 111, 101, 100), on le décale d'un cran (110, 111, 101, 100, 110) et on concatène
(000, 001, 011, 010, 110, 111, 101, 100, 110, 000). On obtient un circuit Hamiltonien pour HC3. A partir de celui de HC3, on obtient de même celui de HC4.

## Exercice 2 du TD2 :

1) Soit un cycle eulérien dans $G$. Il est une succession de sommets et d'arrêtes s1 -> a1 -> s2 -> a2 ... -> sn -> an (-> s1). Soit $s$ un sommet de $G$. Chaque occurence de $s$ dans le cycle a une arête précédente et une arête suivante. Ainsi le degré de $s$ en se restreignant aux arêtes du cycle est le double du nombre d'occurence de $s$ dans le cycle.

De plus par définition un cycle eulérien comprend toutes les arêtes du graphe $G$ donc le degré de $s$ est pair.

2) Le même raisonnement qu'en 1) montre que le degré d'un sommet $s$ en se restreignant aux arêtes d'un cycle $C$ est pair (c'est le double du nombre d'occurence de $s$ dans le cycle). Donc en enlevant les arrêtes de C, on dimininue son degré d'un nombre pair. Comme son degré était pair au départ (dans G), il reste pair à l'arrivée (dans G')

3) On prend une arrête a1 (il y en a au moins une par hypothèse). Cette arrête relie 2 sommets s1 et s2. Si c'est 2 fois le même sommet, alors mon arrête à elle seule est un cycle simple et c'est bon. Sinon, alors cette arrête compte pour 1 dans le degré de s2, qui est pair par hypothèse, donc il existe une autre arrête a2 incidente à s2 et qui le relie à un certain sommet s3. On construit ainsi un chemin s1 a1 s2 a2 s3... d'arrêtes distinctes : tant qu'on ne retombe pas sur s1, on peut rajouter une nouvelle arrête (par parité du degré du dernier sommet du chemin). Comme il y a un nombre fini d'arrêtes dans le graphe, ce processus n'est pas inifini, donc on finit par retomber sur s1. A ce moment là, on a obtenu un cycle simple, cqfd.

4) a. Raisonnement par l’absurde: On veut montrer que A implique B, pour cela on suppose A et non B et on aboutit à une contradiction (ici B est l'existence d'un cycle eulérien).

b. Les 3 premières phrases (utilisation des questions 2 et 3 pour construction de C1 et C2) font un raisonnement rigoureux. En revanche, il n'est pas prouvé que l'union de C1 et C2 forme bien un cycle (on pourrait avoir 2 cycles totalement disjoints, donc impossibles à concaténer en un seul cycle).

c. Pour montrer que l'union de C1 et C2 forme bien un cycle, il faudrait avoir pris soin de construire C2 de sorte qu'il ait un sommet commun avec C1. Cela peut se faire en améliorant l'énoncé de la question 3 pour avoir un résultat plus fort (imposer que le cycle construit passe par une arrête donnée).

## Exercice 3 du TD2 :

1)
2)

# OLA, TD3 : Composantes connexes et relations d'équivalence

## Execice 1
1. Vrai, reflexive: chemin vide ; transitive: concaténation des chemins; symétrique: non-orienté donc on peut prendre le chemin dans l'autre sens
2. Faux, non-symétrique car graphe orienté
3.a) Faux, car E a un degré 6 avec la boucle(qui compte pour 2 car elle a deux attaches sur le sommet E)
3.b)Faux, par l'absurde: supposons qu'on peut colorier le graphe avec 4 couleurs mais tous les sommets (au nombre de 5) sont reliés par une arêtes deux par deux donc on ne peut pas colorier avec au plus 4 couleurs.
3.c) Vrai, tout graphe non orienté connexe dont les sommets ont des degrés pairs admet un cycle eulérien (voir TD précédent). Autre façon de le prouver : construire le cycle :

Pour prouver le contraire, ne contient pas cycle eulérien, on raisonne avec graphe orienté ou non et connexe ou non, et des théorèmes comme celui vu au TD précédent.

## Exercice 2

1. Montrons que R est une relation d'équivalence, c'est-à-dire montrons qu'elle est symétrique, reflexive et transitive.
Symétrique: Soient x et y tels que xRy. Par définition de R, f(x)=f(y). Donc f(y)=f(x). Donc yRx, cqfd.
Reflexive: Soit x $\in$ A. On a f(x)=f(x) donc xRx, cqfd.
Transitive: Soient x, y et z tels que xRy et yRz, c'est-à-dire f(x)=f(y) et f(y)=f(z). Donc f(x)=f(z) c'est-à-dire xRz, cqfd.

Classes d'équivalence = ensembles E maximaux tels que pour tout x et y de E, on a xRy. Avec la définition de R, classes d'équivalence de R, ensembles E maximaux tels que pour tout x et y de E, on a f(x)=f(y). Donc les classes d'équivalence de R sont les ensembles d'antécédents des éléments de B.

Classe d'équivalence x sous une relation R:
{ y tels que xRy }
Si on prend x' tel que xRx' alors pour tout y tel que xRy, on a aussi x'Ry (puisque R est une relation d'équivalence donc symétrique et transitive). Donc la classe d'équivalence de x' est la même que celle de x.

2. Pour montrer que l'inclusion n'est pas une relation d'équivalence il suffit de montrer qu'elle n'est pas symétrique. Soit la relation R définie par x $\subseteq$ y. Prenons x = {1, 2} et y = {1}, on a y $\subseteq$ x mais x $\nsubseteq$ y, donc la relation R n'est pas symétrique

## Exercice 3

1. a.Composantes non vides: la composante connexe de a contient au moins a (puisqu'on autorise le chemin vide).

b.Tout sommet appartient au moins à une composante: Soit a un sommet, il apartient à sa composante connexe.

c. Considérons deux composantes connexes A et B. Soient a un sommet tel que A soit la composante connexe de a (de même un sommet b pour B). Si A et B sont disjointes, on est bien dans l'un des deux cas attendu.

Si A et B ne sont pas disjointes, cela signifie qu'il existe un élément x qui appartient à A et à B. Par défintion des composantes connexes, comme x appartient à A, il existe un chemin de a à x. De Même, comme x appartient à B, il existe un chemin de b à x. Or notre graphe est non orienté, donc on a un chemin de x à b. On concatène le chemin de a à x et celui de x à b pour faire un chemin de a à b.
Montrons maintenant que A est inclus dans B:
soit a' dans A, par définition de A, il existe un chemin de a à a' (donc de a' à a puisque G est non-orienté), et donc de a' à b en concaténant avec le chemin de a à b. donc a' appartient à B (composante connexe de b).
De la même façon, on montre que B est inclus dans A.
On a donc A = B.

On a montré que A=B quand A et B sont non disjointes. On a donc bien
A et B sont disjointes ou A et B sont égales.

2. Soit n le nombre de sommets du graphe, on a au maximum n composantes connexes. Exemple où ce maximum est atteint : si on n'a aucune arrête dans le graphe. Dans ce cas chaque sommet est seul dans sa composante connexe, donc une composante connexe correspond exactement à un sommet.
Le nombre minimal de composante connexes est 1. Exemple où ce minimum est atteint : si le graphe est connexe. En effet, par définition d'un graphe connexe, pour tous sommets a et b il existe un chemin de a à b, donc pour tous sommets a et b, ils sont dans la même composante connexe.

3. On ajoute une arrête a-b.

S'il n'y avait pas de chemin entre a et b dans G, alors les composantes connexes CC_G(a) et CC_G(b) sont distinctes, mais dans G' on a l'arrête a-b donc CC_G'(a) = CC-G'(b). Plus précisément, CC_G'(a) = CC_G(a) U CC_G(b) = CC-G'(b) : tous les sommets qui étaient reliés à a ou à b sont maintenant reliés à a et à b. Tous les sommets qui n'étaient reliés ni à a ni à b sont toujours reliés ni à a ni à b. Les autres composantes connexes dont inchangées. On a donc une composante connexe de moins dans G' que dans G.

S'il y avait déjà un chemin entre a et b dans G, alors en ajoutant une arête a-b on crée un cycle (l'ancien chemin + la nouvelle arrête)

On a bien montré que soit un cycle a été crée, soit le nombre de composantes connexes a diminué de 1.

4. Soit G un graphe acyclique à n sommets et soit m le nombre d'arrêtes de G. On veut montrer que m est inférieur ou égal à n-1.
G peut être construit à partir du graphe G_0 qui est le graphe à n sommets sans arrêtes, en ajoutant une à une les m arrêtes de G. On note G_1, G_2 ... G_m les graphes obtenus successivement (en ajoutant les arrêtes une par une). Donc G_i a i arrêtes, et G_m = G. Pour tout i, G_i est acyclique (car G est acyclique et G_i est une sous-partie de G). D'après la question 3. pour tout i, en passant de G_i à G_i+1, soit on crée un cycle, soit on diminue de 1 le nombre de composantes connexes. Or on sait qu'il n'y a pas de cycle, donc pour tout i, G_i+1 a une composante connexe de moins que G_i. Or G_0 a n composantes connexes, donc pour tout i, G_i a n-i composantes connexes. De plus G = G_m a au moins 1 composante connexe, donc n-m >= 1 c'est-à-dire m est inférieur ou égal à n-1, cqdf.

## Exercice 4

1.

2.

3.

4.

5.

# OLA, TD4: Arbres

Sujet:
https://www.lri.fr/~blsk/OLA/td4.pdf

## Exercice 1

1. Vrai, un arbre à n sommets possède n - 1 arêtes
2. Faux
3. Vrai, un arbre est par définition connexe et acyclique, donc ajouter une arête entre 2 sommets créera forcement un cycle
4. Faux

## Exercice 2

Ce raisonnement n'est pas une preuve. Une preuve doit être correcte en toute généralité, il ne doit donc pas y avoir de contre-exemple possible. Or on peut imaginer des contre-exemples à cette "preuve". Par exemple si G s'est fait berner (cas où N lui a effectivement promis de l'aider en échange d'un service illégal, mais n'a ensuite pas tenu sa promesse) ou si N n'a pas réussi (cas où il a effectivement aidé G à obtenir une promotion, mais cela n'a pas abouti).

## Exercice 3

1. a. 9, car il y a 9 cases donc au max 9 coups.
b. Si la partie est finie : 0, sinon 9-k.
c. Chaque configuration de profondeur k à au plus 9 - k fils, donc on aura 9 * 8 * 7 ... * 1 = 9! (et on ajoute un sommet pour la racine)
2. Les configurations de profondeur paire sont celles qui ont le même nombre de X et de O. Dans ces configurations, c'est à X de jouer.
3. a. Oui, si elle joue mal.
b. Non, par définition de position gagnante: quoi qu'Abélard joue, Eloise gagne à coup sûr.
c. Non, comme elle a une possibilité de gagner, par définition, la position est gagnante et pas irrésolue.
d. Oui, si Abélard joue mal.
4. a. Configuration gagnante
b. Aucun des trois cas en particulier
c. Configuration gagnante
d. Aucun des trois cas en particulier
e. Configuration gagnante
f. Configuration perdante
5. Pour les feuilles de l'arbres, ce sont des configurations où on ne peut plus jouer (la partie est finie) donc c'est gagnant pour ∃loïse si et seulement elle a effectivement gagné dans cette configuration.
Puis en remontant dans l’arbre : un nœud interne à profondeur paire (c’est à ∃loïse de jouer) est gagnant si l’un de ses fils est gagnant. Dans le cas d’un nœud à profondeur impaire (c’est à ∀bélard de jouer), il est gagnant si tous ses fils sont gagnants.

## Exercice 4

1. Soit G un graphe ayant une couverture connexe G'. Soient s1 et s2 deux sommets de G. Comme G' est une couverture connexe, s1 et s2 sont des sommets de G' et G' est connexe. Donc il existe un chemin C de s1 à s2 dans G' (c'est-à-dire un chemin utilisant des sommets et des arrêtes de G'). Or les sommets et le arrêtes de G' sont des sommets et des arrêtes de G (par définition d'une couverture connexe). Donc le chemin C est aussi un chemin dans G, et il relie s1 à s2. On a donc bien un chemin de s1 à s2 dans G quels que soient s1 et s2 sommets de G, i.e. G est connexe.

2. Définition d'un arbre : graphe connexe et acyclique.
Soit G' une couverture connexe minimale. Par définition, G' est connexe. Il nous reste à montrer qu'il est acyclique. On va le montrer par l'absurde : supposons que G' n'est pas acyclique, et montrons qu'on aboutit à une contradiction. Si G' a un cycle, on peut supprimer une arrête de ce cycle, et le graphe H qu'on obtient est toujours connexe et a toujours les mêmes sommets, c'est donc toujours une couverture connexe, et H a une somme d'arrêtes strictement inférieure à celle de G', contradiction. G' est donc bien acyclique, c'est donc bien un arbre.

3. On part d'une couverture connexe G' contenant a, et on montre qu'elle n'est pas minimale. Si G' contient tout le cycle p, il n'est pas minimal d'après la question 2. Si G' ne contient pas tout le cycle, il existe une arrête a' qui n'est pas dans G'. Soit H le graphe obtenu à partir de G' en remplaçant a par a'. La somme des arrêtes de H est strictement inférieure à celle G' (puisque a est strictement maximal dans le cycle p). Il reste à montrer que H est bien une couverture connexe.
Par construction de H à partir de G', H est bien une couverture. Il reste à montrer qu'il est connexe. Soient s1 et s2 deux sommets de H. Comme G' est une couverture connexe, il existe un chemin de s1 à s2 dans G'. Si ce chemin n'emprunte pas a, c'est aussi un chemin de H. Si ce chemin emprunte a, on peut s'arranger pour faire un chemin qui passe une seule fois par a, et décomposer le chemin en s1 - ... - s3 - a - s4 - ... - s2. G' étant connexe, en notant s3' et s4' les extrémités de a', il existe un chemin s3 -> s3' et un chemin s4' -> s4. On remplace par un chemin s1 - ... - s3 -> s3' - a' - s4' -> s4 - ... - s2 qui est un chemin de H. H est donc bien connexe, cqfd.

# TP OLA

### Sujet du TP:

https://www.lri.fr/~blsk/OLA/tp1.pdf

#### Une possibilité pour faire du Python en ligne:

https://www.online-python.com

## Exercice 1

## Matrice d'ajacence

1.
g = [[0, 1, 1, 0, 1, 0, 0, 0], #0
     [0, 0, 0, 1, 0, 1, 0, 0], #1
     [0, 0, 0, 1, 0, 0, 1, 0], #2
     [0, 0, 0, 0, 0, 0, 0, 1], #3
     [0, 0, 0, 0, 0, 1, 1, 0], #4
     [0, 0, 0, 0, 0, 0, 0, 1], #5
     [0, 0, 0, 0, 0, 0, 0, 1], #6
     [0, 0, 0, 0, 0, 0, 0, 0]] #7

2.
def compte_sommets(g):
    return len(g)

def compte_aretes(g):
    nb = 0
    for ligne in g:
        for arete in ligne:
            if arete:
                nb += 1
    return nb

3.
def adjacents(g, i, j):
    return g[i][j] or g[j][i]

4.
def successeurs(g, s):
    res = []
    for v in range(len(g[s])):
        if g[s][v]:
            res.append(v)
    return res

5.
def predecesseurs(g, s):
    res = []
    for v in range(len(g)):
        if g[v][s]:
            res.append(v)
    return res

6.
def reflexif(g):
    for i in range(len(g)):
        if not g[i][i]:
            return False
    return True

7.
def symetrique(g):
    for i in range(len(g)):
        for j in range(i):
            if g[i][j] != g[j][i]:
                return False
    return True

8.
def symetrisation(g):
    for i in range(len(g)):
        for j in range(len(g[i])):
            if g[i][j]:
                g[j][i] = True

9.
def transitif(g):
    for i in range(len(g)):
        for j in successeurs(g, i):
            for k in successeurs(g, j):
                if not g[i][k]:
                    return False
    return True

## Listes d'adjacence

1.
g = [[1, 2, 4], #0
     [3, 5],    #1
     [3, 6],    #2
     [7],       #3
     [5, 6],    #4
     [7],       #5
     [7],       #6
     []]        #7

2.
def compte_sommets(g):
    return len(g)

def compte_aretes(g):
    nb = 0
    for s in g:
        nb += len(g[s])
    return nb

3.
def adjacents(g, i, j):
    for x in g[i]:
        if x == j:
            return True
    for x in g[j]:
        if x == i:
            return True
    return False

def adjacentsAlternatif(g, i, j):
    return j in g[i] or i in g[j]

4.
def successeurs(g, s):
    return g[s]

5.
def predecesseurs(g, s):
    res = []
    for v in range(len(s)):
        if s in g[v]:
            res.append(v)
    return res

6.
def reflexif(g):
    for s in range(len(g)):
        if not s in g[s]:
            return False
    return True

7.
def symetrique(g):
    for s in range(len(g)):
        for v in g[s]:
            if not s in g[v]:
                return False
    return True

8.
def symetrisation(g):
    for s in range(len(g)):
        for v in g[s]:
            if not s in g[v]:
                g[v].append(s)

9.
def transitif(g):
    for i in range(len(g)):
        for j in g[i]:
            for k in g[j]:
                if not k in g[i]:
                    return False
    return True

## Conversions

def m2l(g):
    return [successeurs(g, s) for s in range(len(g))]

# Autre solution équivalente
def m2l(g):
    G = []
    for s in range(len(g)):
        G.append(successeurs(g, s))
    return G

# print(m2l([[0,1,0],[1,0,1],[0,1,0]]))


def l2m(g):
    m = [[False] * len(g) for _ in range(len(g))]
    for sommet in range(len(g)):
        for voisin in g[sommet]:
            m[sommet][voisin] = True
    return m

# print(l2m(m2l([[0,1,0],[1,0,1],[0,1,0]])))

## Exercice 2

1.

def verifie_chemin(g, c):
    for i in range(len(c)-1):
        if g[c[i]][c[i+1]] is None:
            return False
    return True

# OLA, TD5: Parcours de graphes

Sujet:
https://www.lri.fr/~blsk/OLA/td5.pdf

## Exercice 1

1. Vrai : FEABCG
2. Faux, à cause de l’orientation
3. Faux, à cause de l’orientation toujours
4. Vrai : le chemin vide
5. Faux : on ne peut pas aller de H aux autres
6. Faux : l’ensemble n’est pas maximal (il faudrait ajouter CG)

## Exercice 2

En logique, si A $\Rightarrow$ B, alors (non B) $\Rightarrow$ (non A)
De même, si (non A) $\Rightarrow$ B, alors (non B) $\Rightarrow$ A

Alice a prouvé H $\Rightarrow$ non T.
Et elle dit que H est faux, elle en déduit que T est juste.
Cette dernière partie de raisonnement est fausse : (H $\Rightarrow$ non T) n'implique pas que (non H $\Rightarrow$ T) : on pourrait avoir H et T tous les deux faux.
Sur ce point là, Basile a raison: Alice a utilisé l'implication dans le mauvais sens. Par contre la fin du raisonnement de Basile n'est pas correcte non plus: s'il prouvait effectivement que H est vrai, il pourrait en déduire que T est faux (d'après l'implication prouvée par Alice). Mais il ne prouve pas que H est vrai, il dit juste que Alice n'a pas prouvé que H est faux.

## Exercice 3

1. Etats successifs de la pile:
[], [A], [A,B], [A,B,C], [A,B,C,D], [A,B,C,D,G], [A,B,C,D,G,F],[A,B,C,D,G],[A,B,C,D,G,H], [A,B,C,D,G], [A,B,C,D], [A,B,C], [A,B],[A,B,E],[A,B], [A], [].

2. L'état final sera le même que l'état initial car la fonction visiter contient une instruction empiler et une instruction dépiler. L'élément qui est retiré à la ligne 12 est s

3. Au début de l'algorithme, la pile est vide, et le chemin vide est bien un chemin. Il reste à montrer que chaque fois qu'on modifie la pile, si elle contenait un chemin avant modification, elle contient toujours un chemin après modification. On modifie la pile ligne 8 et ligne 12. Ligne 8, on empile. Si la pile était vide, on obtient un sommet seul, ce qui forme bien un chemin. Si la pile n'était pas vide, alors le sommet qu'on empile est un successeur du dernier sommet de la pile (puisque la fonction visiter est appelée sur des sucesseurs du sommet en cours). Enfin ligne 12, on dépile, si on avait un chemin avant on a bien toujours un chemin après (plus court).

4. Le critère n'est pas correct: si on l'applique au sous-graphe contenant uniquement les sommets D, G et H du graphe de la question 1, ce critère va nous dire qu'il y a un cycle (on marque H comme successeur de G puis on retombe sur H comme successeur de D) alors qu'il n'y en n'a pas (à cause de l'orientation des arcs, DGH ne forme pas un cycle).
Correction du critère : on a un cycle lorsque le sommet rendant le test vrai est dans la pile en_cours (peut se montrer en utilisant la question 3).

## Exercice 4

1.a.
Preuve par l’absurde. Supposons que le parcours à partir de s1 visite des sommets qui ne sont pas dans la composante fortement connexe C1 de s1. Soit s le premier tel sommet, alors le sommet par lequel on arrive à s est dans C1 (puisque s est le premier sommet pas dans C1) donc s est dans le halo de C1. Par hypothèse, s a un numéro strictement plus petit que les sommets de C1, donc strictement plus petit que 1 (numéro de s1), contradiction (ce qui conclut notre preuve par l'absurde).

1.b. Soit C1 la composante fortement connexe de s1.
Soit S1 l'ensemble des sommets visités lors du parcours en profondeur depuis s1.
On doit montrer S1 = C1.
En 1.a.on a montré S1 $\subset$ C1.
Il nous reste donc à prouver C1 $\subset$ S1, c'est-à-dire montrer que si un sommet est dans la composante fortement connexe de s1, alors il est visité lors du parcours en profondeur depuis s1.
Or un parcours en profondeur (ou en largeur d'ailleurs) depuis un sommet s parcours tous les sommets accessibles depuis s. Et par définition, les sommets de la composante fortement connexe de s1 sont accessibles depuis s1. Ils sont donc bien visités lors du parcours en profondeur depuis s1.

1.c.
Tant qu’il reste des sommets dans G :
Faire un parcours depuis le sommet s de plus petit numéro,
étiqueter tous les sommets atteints comme constituant la composante de s et les retirer du graphe.

2. Ressemble beaucoup à un parcours en profondeur, mais on considère les prédecesseurs des sommets plutôt que leurs successeurs. Cela revient à un parcours en profondeur dans lequel les arêtes sont suivies en sens inverse (autrement dit, un parcours en profondeur classique du graphe dans lequel les arêtes ont été préalablement retournées).

# OLA, TD6: Récurrence

Sujet:
https://www.lri.fr/~blsk/OLA/td6.pdf

Cours:
https://www.lri.fr/~blsk/OLA/OLA3.pdf

## Exercice 1

1. 0! = 1, n! = n $\times$ (n - 1)! $\forall$ n > 0
ou alors: 0! = 1, (n+1)! = (n+1) $\times$ n! $\forall n \in N$
2. $k^0 = 1$, $k^n = k \times k^{n-1}$ $\forall$ n > 0
3. Petit exemple pour bien comprendre ce nouvel opérateur : ${}^23$ = $3^{3^3}$ = $3^{27}$
${}^0k = k$, ${}^nk = k^{({}^{n-1}k)}$ $\forall n > 0$

## Exercice 2
* Initialisation pour n = 1 :
Pour n=1, on doit montrer que pour tout quadrillage de côté de taille 2, si on retire un case quelconque on peut le paver avec des triominos. Il y a 4 façons possibles de retirer une case à un quadrillage de côté de taille 2, et dans tous les cas un unique triomino suffit à paver ce qui reste (rotation du triomino si nécessaire).

* Hérédité: On suppose qu’un quadrillage de côté $2^n$ auquel on retire une case peut toujours être pavé par des triominos. Montrons que c’est également le cas d’un quadrillage de côté $2^{n+1}$ auquel on retire une case.
Un quadrillage de côté $2^{n+1}$ est formé de quatre carrés de
côté $2^n$ . La case retirée est dans exactement un de ces quatre carrés. On peut retirer une case à chacun des trois autres carrés en plaçant un triomino au centre du quadrillage de côté $2^{n+1}$ . On obtient alors un triomino et quatre carrés de côté $2^n$ auxquels une case a été retirée. Par hypothèse de récurrence, ces quatre carrés peuvent être pavés par des triominos donc le quadrillage initial aussi.

## Exercice 3

L'étape d'hérédité qui fait passer du cas $n$ au cas $n+1$ n'est correcte que si $n\geq 2$ en effet dans ce cas on regarde l'ensemble des crayons $2..(n+1)$ qui sont tous de la même couleur et de même pour les crayons $1..n$. Tous les crayons ont donc la même couleur que le crayon numéro $2$. Mais si il n'y a que deux crayons (cas $n=1$), l'hypothèse de récurrence dit que le crayon $2$ a la même couleur que lui-même et que le crayon $1$ a la même couleur que lui-même, mais rien ne permet de conclure que ces deux crayons sont de la même couleur.

## Exercice 4

1. Par récurrence sur la liste l.
* Initialisation: On sait par définition que rev([]) = [], donc longueur(rev([])) = longueur([]) = 0
* Hérédité: Supposons qu'on ait la propriété pour une liste $l$, montrons la propriété pour $x::l$ où x élément quelconque.
Par défintion, rev(x::l) = concat(rev(l), x::[]).
Par hypothèse de récurrence, on a longueur(rev(l)) = longueur(l).
On a égalemnt longueur(x::[]) = 1 + longueur([]) = 1.
D'après une propriété de longueur et concat vue en cours, longueur(concat(l1, l2)) = longueur(l1) + longueur(l2) donc
longueur(concat(rev(l), x::[])) = longueur(rev(l)) + longueur(x::[]) = longueur(l) + 1 = longueur(x::l) donc la propriété est vraie pour $x::l$

2. Par récurrence sur la liste l1
* Initialisation: Quand l1 = [], on a
$$ \begin{align} rev(concat([\,], l2)) &= rev(l2)\\ &= concat(rev(l2), [\,])\\ &= concat(rev(l2), rev([\,])) \end{align}$$

* Hérédité: Supposons qu'on ait la propriété pour $l1= l$, montrons la propriété pour $l1 = x::l$ où x élément quelconque.

rev(concat(x::l, l 2 )) = rev(x::concat(l, l 2))
= concat(rev(concat(l, l 2 )), x::[])
= concat(concat(rev(l 2), rev(l)), x::[])
= concat(rev(l 2 ), concat(rev(l), x::[]))
= concat(rev(l 2 ), rev(x::l))

3. A faire chez vous

## Exercice 5

1. A chaque appel récursif, rev fait aussi un appel à concat.
Donc si on appelle rev sur une liste de taille n, elle appelle concat sur une liste de taille n-1 et rev sur une liste de taille n-1, qui elle-même appelle concat sur une liste de taille n-2 et rev sur une liste de taille n-2, etc.
Or concat a une conplexité proportionnelle à la longueur de son premier paramètre.
Pour un appel à rev sur une liste de taille n, on a donc une conplexité proportionnelle à n-1 + n-2 + n-3 + ... + 1 soit n(n-1)/2 donc de l'ordre de $n^2$, ce qui est beaucoup pour simplement retourner une liste de taille n.

2. rev_rt(l) = aux(l, [])
aux([], acc) = acc
aux(x::l, acc) = aux(l, x::acc)

3. On va faire une preuve par récurrence sur les listes.
Mais la définition de rev_tr n'est pas directement récusive: elle est définie à partir de aux. La fonction aux, elle, est définie de façon récursive -> ce qu'on va montrer par récurrence est une propriété sur aux, par récurrence sur son premier paramètre.

On veut montrer que pour tout liste l, rev_rt(l) = rev(l), i.e. aux(l, []) = rev(l).

On va montrer que pour tout listes l et a, aux(l, a) = concat(rev(l), a).
On va montrer cela par récurrence sur la première liste l.

* Initialisation: Pour l = [], on a aux([], a) = a et concat(rev([]), a) = concat([], a) = a. Donc la propriété est vraie pour l = []

* Hérédité: Supposons qu'on ait la propriété pour $l$, montrons la propriété pour $x::l$ où x élément quelconque.

# OLA, TD7

Sujet:
https://www.lri.fr/~blsk/OLA/td7.pdf

Cours:
https://www.lri.fr/~blsk/OLA/OLA3.pdf

## Exercice 1

1. Faux, l'arbre vide est un arbre binaire
2. Vrai, l'arbre qui ne contient qu'un noeud à la racine
3. Faux, un arbre à 2 noeuds est soit la racine et un fils gauche, soit la racine et un fils droit
4. Vrai, par exemple un arbre dont tous les fils sont du même côté
5. Vrai
6. Faux, un arbre binaire de profondeur 3 contient au plus 15 noeuds
7. Il y en a 42
- 14 avec 4 noeuds à gauche et 0 à droite
- 14 avec 0 noeuds à gauche et 4 à droite
- 5 avec 3 noeuds à gauche et 1 à droite
- 5 avec 1 noeuds à gauche et 3 à droite
- 4 avec 2 noeuds de chaque côté
8. $$ \sum_{k = 0}^{n - 1}{C_k \times C_{n-1-k}}$$

## Exercice 2

1. On se base sur le définition récursive des arbres binaires pour définir notre fonction:
in(n,V) = faux
in(n,N(a1, e, a2)) = n = e ou in(n,a1) ou in(n,a2)

2. infix(V) = $\epsilon$ (notation pour la séquence vide)
infix(N(a1, e, a2)) = infix(a1) . e . infix(a2)

3. S(n) = N(V,n,V) est un arbre binaire de recherche (ABR)
N(S(1),2,S(3)) est aussi un arbre binaire de recherche car S(1) est un ABR, s(3) est un ABR, et (1 <= 2 et 3 >= 2).
N(V, 2, N(S(1), 3, V)) n'est pas un ABR car 1 se situe dans le sous-arbre droit de la racine 2.

4. N( S(1), 2, N( S(3),4,V ) ) "1234"
N( S(1), 2, N( V,3,S(4) ) ) "1234"
N( N(V, 1, S(2)), 3, S(4) ) "1234"
N( N( S(1),2,V ), 3, S(4) ) "1234"

5.
On veut montrer que pour tout arbre binaire de recherche, infix(a) est triée.

Cas de base: arbre vide
infix(V) = $\epsilon$ (séquence vide) qui est bien en ordre croissant. On a donc bien l'initialisation de notre récurrence.

Cas inductif: on suppose que a1 et a2 vérifient la propriété, et on montre que alors N(a1,e,a2) la vérifie aussi, quel que soit e.
infix(N(a1,e,a2)) = infix(a1) . e . infix(a2).
On sait par hypothèse de récurrence que infix(a1) est trié et infix(a2) est trié, de plus par définition d'un ABR on sait que $\forall n_1 \in a1, e \geq n_1$ et $\forall n_2 \in a2, e \leq n_2$.
Donc la séquence infix(a1) . e . infix(a2) est trié

6. Quand on cherche n dans N(a1,e,a2), soit n=e et on s'arrête là (on l'a trouvé), soit n<e et on cherche uniquement dans le sous-arbre gauche, soit n>e et on cherche uniquement dans le sous-arbre droit.

7. inabr(n, V) = Faux
inabr(n, N(a1, e,a2)) =
si n = e alors Vrai
si n < e alors inabr(n, a1)
si n > e alors inabr(n, a2)

# OLA, TD8

Sujet:
https://www.lri.fr/~blsk/OLA/td8.pdf

Cours:
https://www.lri.fr/~blsk/OLA/OLA3.pdf

## Exercice 1

1. $\forall$ x,y, ami(x, y) $\implies$ lié(x, y)
$\forall$ x,y,z, ami(x, y) et lié(y, z) $\implies$ lié(x, z)

2. La définition de lié étant récursive, on va pouvoir utiliser un principe d'induction pour prouver des propriétés P(x,y) vérifiées pour tous éléments x,y tels que lié(x,y).
Le principe d'induction associé à la définition de lié est:
Pour une propriété P(x,y), si on a
$\forall$ x,y, ami(x,y) $\implies$ P(x,y)
et $\forall$ x,y,z ami(x,y) et lié(y,z) $\implies$ P(x,z)
alors P(x,y) est vraie pour tous x,y tels que lié(x,y).

3. a D'après la 2e ligne de la définition de lié, on a
$\forall$ x,y,z, ami(x, z) et lié(z, y) $\implies$ lié(x, y).
Or pour toutes formules A, B et C, on a
A $\implies$ (B $\implies$ C) est équivalent à (A et B) $\implies$ C.
En effet X $\implies$ Y est équivalent à (non X) ou Y.
Donc A $\implies$ (B $\implies$ C) est équivalent à
(non A) ou (B $\implies$ C)
(non A) ou (non B) ou C
(non (A et B)) ou C
(A et B) $\implies$ C.

En particulier, en appliquant celà on obtient
$\forall$ x,y,z, ami(x, z) $\implies$ (lié(z, y) $\implies$ lié(x, y)).

3. b. On veut montrer
$\forall$ x,y,z, lié(x, z) $\implies$ (ami(z, y) $\implies$ lié(x, y)).
C'est-à-dire qu'on veut montrer que pour tous x et z tels que lié(x, z) alors on a (ami(z, y) $\implies$ lié(x, y)) pour tout y.

On va montrer par induction sur les éléments liés la propriété P suivante :
P(x,z) = $\forall$ y, (ami(z, y) $\implies$ lié(x, y))

Cas de base : on doit montrer que
$\forall$ x,y, ami(x,y) $\implies$ P(x,y)

Cas inductif : on doit monter que
$\forall$ x,y,z ami(x,y) et P(y,z) $\implies$ P(x,z).

On aura alors montré que
alors P(x,y) est vraie pour tous x,y tels que lié(x,y).

Case de base: Supposons ami(x,y). On doit montrer P(x,y), c'est-à-dire $\forall$ a, (ami(y, a) $\implies$ lié(x, a)).
Soit a tel que ami(y,a). On a ami(y,a) donc lié(y,a) (par définition de lié première formule). Or par définition de lié (2e formule) ami(x,y) et lié(y,a) $\implies$ lié(x, a). On a donc bien lié(x,a), cqfd.

Cas inductif : supposons ami(x,y) et P(y,z).
c'est-à-dire $\forall$ a, (ami(z, a) $\implies$ lié(y, a)).

On doit montrer P(x,z), c'est-à-dire
$\forall$ a, (ami(z, a) $\implies$ lié(x, a)).

Soit a tel que ami(z, a). D'après l'hypothèse d'induction on a lié(y, a), or on a également ami(x, y). Par définition de lié (2e formule) on a alors lié(x,a), cqfd.

4. On veut montrer, pour tous x,y, lié(x,y) $\implies$ lié(y,x). On veut montrer P(x,y) = lié(y,x) pour tous x,y tels que lié(x,y). On va faire une preuve par induction.

Cas de base: On veut monter $\forall$ x, y, ami(x, y) $\implies$ P(x, y)
Supposons ami(x, y). On sait que ami est symétrique donc on a ami(y, x). Or par définition de lié (1ère formule) on a ami(y, x) $\implies$ lié(y, x), or justement lié(y,x) = P(x, y).

Cas inductif : On doit montrer que
$\forall$ x, y, z, ami(x, y) et P(y, z) $\implies$ P(x,z)
c'est-à-dire $\forall$ x, y, z, ami(x, y) et lié(z, y) $\implies$ lié(z,x).
Suppons ami(x, y) et lié(z, y). On a aussi ami(y,x) puisque ami est symétrique. Or on a montré en question 3b que
$\forall$ x,y,z, lié(z, y) $\implies$ (ami(y, x) $\implies$ lié(z, x)). On a donc bien lié(z,x), cqfd.

## Exercice 2

1. A faire à la maison

2. Le principe d'induction associé à la définition de R est:

Pour une propriété P(x,y,n), si on a

P(0,1,0)
et $\forall$ x,y,n, P(x, y, n) $\implies$ P(x+y, y+2, n+1)

alors P(x,y,n) est vraie pour tous x,y,n tels que R(x,y,n).

3. On prend P(x,y,n) = (x=$n^2$ et y=2n+1) et on la montre par induction sur les éléments en relation.

Cas de base: P(0,1,0) = (0=$0^2$ et 1=2\*0+1) est bien vrai.
Cas inductif: Supposons P(x, y, n), c'est-à-dire x=$n^2$ et y=2n+1.
On doit montrer P(x+y, y+2, n+1).
Par hypothèse de récurrence, x+y = $n^2 + 2n + 1 = (n + 1)^2$
et y+2 = 2n+3 = 2\*(n+1)+1, cqfd.

## Exercice 3

1. Définition de F:
F(0,0,1)
$\forall n,m,y$ F(n,m,y) $\implies$ F(n+1,m,2y)
$\forall n,m,y$ F(n,m,y) $\implies$ F(n,m+1,3y)

(en effet, si f(n,m) = y alors f(n+1,m) = 2y,
de même si f(n,m) = y alors f(n,m+1) = 3y)

f(4,3) peut être déduit de f(3,3) ou de f(4,2), et cela pourrait donner des valeurs différentes (ce qui serait problématique pour la fonction).

Prouver que f est bien une fonction, c'est prouver que la valeur f(n,m) est unique, quels que soient n et m.

C'est-à-dire, prouver que pour tous n et m, il y a un unique y tel que F(n,m,y).

On va utiliser le principe d'induction associé à la définition de F.

Pour une propriété P(n,m,y), si on a

P(0,0,1)
et $\forall$ n,m,y, P(n, m, y) $\implies$ P(n+1, m, 2y) et P(n, m+1, 3y)

alors P(n,m,y) est vraie pour tous n,m,y tels que F(n,m,y)
(et donc P(n,m,y) est vraie pour tous n,m,y tels que f(n,m)=y).

# OLA, TD9

Sujet:
https://www.lri.fr/~blsk/OLA/td9.pdf

Cours:
https://www.lri.fr/~blsk/OLA/OLA4.pdf

## Exercice 1

1. Le nombre de trains augmente si on tombe sur un train de taille > 1, sinon il diminue.
Le nombre de wagon diminue si on tombe sur un train de taille 1, sinon il reste le même.
Il serait très compliqué de définir un ordre strictement décroissant avec cela. On va donc faire autrement (en questions suivnte)

2. Les arrêtes sont les liens entre les wagons. A chaque étape, soit le nombre d'arrêtes diminue, soit le nombre de sommets diminue. Si on pose n la somme du nombre d'arrêtes et de sommets du graphe, n est un entier naturel qui décroit strictement à chaque étape, donc l'aglorithme termine

## Exercice 2

1. Le nombre de sommets dans l'ensemble a-explorer peut rester stable ou augmenter. Le nombre de sommets marqués peut rester stable ou augmenter (donc le nombre de sommets non marqué peut rester stable ou diminuer).

2. On prend l'ordre lexicographique sur le couple (nb sommets non marqués, nb sommets à explorer). Cela diminue strictement à chaque étape de l'algorithme. En effet, si le sommet s a certains voisins non marqués, alors on va les marquer et donc le nb de sommets non marqués diminue strictement. Sinon, le nombre de sommets non marqués reste stable mais le nomdre d'éléments dans a-explorer diminue strictement (on a enlevé un élément et on n'a ajoute aucun). Par définition de l'ordre lexicographique (voir cours), on a une suite strictement décroissante sur un ordre bien fondé, donc l'algorithme termine.

## Exercice 3

Si un a un tableau t de taille 1 et que l'élément de t est plus petit que l'élément chérché e, alors l'algorithme ne termine pas. En effet, dans ce cas on aura l=0, u=1 donc m=0 (le quotient de 1 par 2). La condition t[m] < e est vérifié donc on fera l = m c'est-à-dire l=0, donc ni l ni u ne seront changés. A chaque étape de boucle, l et u restent les mêmes. Donc l'algorithme ne termine pas.
A chaque étape on considère le même élément t[m] (car l et u restent les mêmes et m dépend de l et u).
Ce qui pose problème est l = m (ligne 9). Il faut la remplacer par l = m+1.

## Exercice 4

1. D'après la deuxième règle, on a 00 < 1$\epsilon$ (c'est-à-dire 00<1), on peut en déduire que 100 < 11 (3ème règle).

2. 1 > 00 et 1 > 0000 (2ème règle)
$\epsilon$ < 00 (1ère règle) donc 00$\epsilon$ < 0000 (3ème règle)
Conclusion : 00 < 0000 < 1

3. test($\epsilon$, $\epsilon$) = 0
test($\epsilon$, xm) = 1
test(xm, $\epsilon$) = 0
test(xm1, ym2) =
si x == 0 et y == 1 alors 1
si x == 1 et y == 0 alors 0
si x == y alors test(m1, m2)

4. On doit montrer une certaine propriété quand test est faux, c'est-à-dire quand test vaut 0. On se référe à la définition de la question précédente pour savoir quels sont ces cas.
Comme test est définie de façon recursive, on va montrer la pripriété par récurrence (les cas de base sont les cas où la fonction ne fait pas d'appel récursif, les cas inductifs sont ceux où la fonction fait un appel récursif).
- Dans le cas test($\epsilon$, $\epsilon$)=0 on a bien $\epsilon$ = $\epsilon$
- Dans le cas test(xm, $\epsilon$) = 0 on a $\epsilon$ < xm d'après la 1ère règle, donc xm > $\epsilon$
- Dans le cas test(xm1, ym2):
Si x == 1 et y == 0, on a bien 1 > 0 donc xm1 > ym2
Si x == y et que test(xm1, ym2) est faux, alors test(m1,m2)=0 (par définition récursive de test).
Par hypthèse de récurrence, m1 > m2.
Donc d'après la règle 3, xm1 > xm2 i.e. xm1 > ym2, cqfd.

5. a. Cas de base: n = 0, On a $x^0$ = $\epsilon$ et $x^1$ = $x\epsilon$, or d'après la 1ère règle $\epsilon$ < $x$m pour tout m, donc $x^0$ < $x^1$
Cas inductif: On suppose la propriété vraie pour n i.e. $x^n$ < $x^{n+1}$, on veut la montrer pour n+1 c'est-à-dire $x^{n+1} < x^{n+2}$
On sait que $x^n$ < $x^{n+1}$, d'après la 3ème règle on a $x(x^n) < x(x^{n+1})$, c'est-à-dire $x^{n+1} < x^{n+2}$

5.b. Même principe que 5.a., à faire par vous-mêmes pour vous entraîner !

# OLA, TD10

Sujet:
https://www.lri.fr/~blsk/OLA/td10.pdf

Cours:
https://www.lri.fr/~blsk/OLA/OLA4.pdf

## Exercice 1

1. E1 = $C \wedge \neg B$
E2 = $(A \vee C) \wedge \neg B$
E3 = $A \Rightarrow B$

2.

| | $A$ | $B$ | $C$ | $C \wedge \neg B$ | $(A \vee C) \wedge \neg B$ | $A \Rightarrow B$ |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 1 | V | V | V | F | F | V |
| 2 | V | V | F | F | F | V |
| 3 | V | F | V | V | V | F |
| 4 | F | V | V | F | F | V |
| 5 | F | F | V | V | V | V |
| 6 | F | V | F | F | F | V |
| 7 | V | F | F | F | V| F |
| 8 | F | F | F | F | F | V |

3. Si tous les enfants disent la vérité, cela veut dire que les 3 formules des 3 dernières colonnes doivent être à vrai. Il y a une seule ligne du tableau qui vérifie cela : la ligne 5. Sur cette ligne, A et B valent faux et C vaut vrai. On en déduit que Carole a touché le vase, et Alice et Basile ne l'ont pas touché.

4. Si exactement un enfant ne dit pas la vérité, cela veut dire que exactement 1 des 3 formules des 3 dernières colonnes doivent être à faux. Il y a une seule ligne du tableau qui vérifie cela : la ligne 3. Sur cette ligne, A et C valent vrai et B vaut faux. On en déduit que Carole et Alice ont touché le vase, et Basile ne l'a pas touché.

## Exercice 2

0. Solution première grille:
V3 V2 V1
B1 B2 B3
R1 R2 B4
Pour la grille d'à côté : Le 4 est focément bleu (il n'y a pas de 4 rouge ni de 4 vert). Le 3 bleu est obligé d'être à sa droite (pas d'autre place à côté pour du bleu). Le 2 bleu est obligé d'être au-dessus du 3 bleu (si on le met à droite, on n'aura plus de place pour le 1). Enfin le 1 bleu est obligé d'être au-dessus du 2. Cela donne:
_ B1 _
V B2 R
B4 B3 _
On n'a pas le choix pour les positions des bleus, mais une fois les bleus placés on n'a plus la place de mettre les 3 verts sur des cases consécutives.
Cette grille n'a donc pas de solution.

1. Une clause par case contrainte:
$R^1_1$
$V^4_1 \vee V^4_2 \vee V^4_3\ $ (il y a 3 canards verts)
$V_3^5 \vee B_3^5\ $ (il n'y pas de canard rouge numéro 3)
$B_4^8$ (seuls les bleus ont un canard numéro 4)

2. $B_1^1 \vee B_1^2 \vee B_1^3 \vee ...\vee B_1^9$

3. $B_1^2 \ \Rightarrow (B_2^1 \vee B_2^3 \vee B_2^5)$
$(\neg B_1^2) \vee (B_2^1 \vee B_2^3 \vee B_2^5)$
$\neg B_1^2 \vee B_2^1 \vee B_2^3 \vee B_2^5$

4. On veut compter le nombre de phrases de la forme
« si le canard $C_k$ est sur la case numéro n, alors le canard $C_{k+1}$ est sur une case adjacente ».
Il y a 9 possibilités pour la valeur de n (numéro de la case). Pour chacune de ces 9 possibilités, il y a 1+2+3 possibilités pour le canard $C_{k+1}$ (1 seule possibilité s'il est rouge, 2 s'il est vert, 3 s'il est bleu).
On a donc 9x6 = 36 phrases de ce type. Chacune de ces phrase peut ensuite se trnasformer en clause comme à la question précédente. On a donc 36 clauses de cette forme.

En raisonnant comme à la question précédente, on voit que s'il y a p cases voisines, alors il y a p+1 littéraux dans la clause (un pour la case considérée et p pour les voisines).
Le nombre minimal est pour une case dans le coin : 2 voisines donc 3 littéraux.
Le nombre maximal est pour une case au milieu : 4 voisines donc 5 littéraux.

5. On veut montrer que les clauses mentionnées jusqu'ici suffisent pour déduire que B_4 est présent dans la grille.
Remarque préliminaire : si on avait juste les clauses de la question 2 et de la question 3, on ne pourrait pas en déduire que le canard B_2 est présent. En effet, la clause de la question 3 nécessite que B_1 soit en case 2 pour pouvoir en déduire que B_2 est sur une case voisine, et la clause de la question 2 ne dit pas que B_1 est en case 2.
Par contre si on a toutes les clauses mentionnées en question 4 en plus de celle de la question 1, on peut en déduire que B_2 est présent. En effet, la clause de la question 2 nous dit que B_1 est présent quelque part dans la grille. On note x le numéro de la case où il est. Alors l'une des clauses de la question 4 nous dit que B_2 est dans une case voisine de x. On en déduit que B_2 est présent dans a grille.
Maintenant qu'on a montré que B_2 est présent, on en déduit de la même manière que B_3 est présent, ce qui implique de même que B_4 est présent.

6. $\neg V_1^4 \vee \neg V_2^4$ est équivalent à
$\neg (V_1^4 \wedge V_2^4)$ ce qui signifie que $V_1$ et $V_2$ ne peuvent pas être tous les deux sur la case 4.
De même $\neg V_1^4 \vee \neg V_3^4$ signifie que $V_1$ et $V_3$ ne peuvent pas être tous les deux sur la case 4.
De même $\neg V_2^4 \vee \neg V_3^4$ signifie que $V_2$ et $V_3$ ne peuvent pas être tous les deux sur la case 4.
Ces 3 clauses ensemble signifient donc qu'il ne peut pas y avoir 2 canards parmi $V_1, V_2, V_3$ qui sont en même temps sur la case 4.

7. Il y a en tout 9 canards (2+3+4). Chaque clause du type de la question précédente concerne 2 canards différents.
Si je fixe une case de la grille, pour exprimer qu'il n'y a pas 2 canards différents présents sur cette case, il faut 9x8/2 clauses (une clause pour chaque façon de choisir 2 canards différents parmi les 9) soit 36 clauses par case.
Il y a 9 cases, donc au total 9x36 = 324 clauses.

Remarque : vous devez connaître la formule qui donne le nombre de façons de prendre k éléments différents parmi n éléments (nombres binomiaux) : $\frac{n!}{k!(n-k)!}$

## Exercice 3

A faire à la maison