Combinatoire - Corrigé du contrôle du 20 octobre 2017
=====================================================

(1) Il faut suivre l'indication !! Si les n jours de permanence de
quelqu'un doivent être consécutifs, ils forment alors une période (ou
un "bloc") unique long de n jours; si ces n jours peuvent être pris
indépendemment l'un de l'autre, ils forment alors n périodes (ou
"blocs") de 1 jour chacune.

Les périodes de chacun ne sont pas ordonnées entre elles, elle forment
donc une combinaison; si on a attribué les périodes de quelqu'un, le
choix des périodes pour le suivant se fait parmi les jours restants,
et non pas le nombre total. Donc si A fait x périodes, B fait y
périodes et C fait z périodes, le nombre de plannings est:
(x parmi x+y+z) * (y parmi y+z) * (z parmi z) =
(x parmi x+y+z) * (y parmi y+z)
puisque (z parmi z) = 1. En permutant l'ordre de A,B,C pour les choix,
on obtient des formules équivalentes avec une permutation de x,y,z. En
fait c'est le coefficient trinomial:
(x;y;z dans x+y+z) = (x+y+z)!/x!y!z!

(i) A 3 périodes, B 2 périodes, C 2 périodes. Donc:
(3 parmi 7) * (2 parmi 4) = (3;2;2 dans 7) = 7!/3!2!2!

(ii) A 1 période, B 2 périodes, C 2 périodes. Donc:
(1 parmi 5) * (2 parmi 4) = (1;2;2 dans 5) = 5!/1!2!2!

(iii) A 1 période, B 1 période, C 2 périodes. Donc:
(1 parmi 4) * (1 parmi 3) = (1;1;2 dans 4) = 4!/1!1!2!
Il est aussi possible de compter, pour chaque emplacement possible de
la période de 3 jours de A dans les 7 jours, le nombre de possibilités
pour placer la période de 2 jours de B, et en additionnant on obtient
12.

(iv) A 1 période, B 1 période, C 1 période. Donc:
(1 parmi 3) * (1 parmi 2) = (1;1;1 dans 3) = 3!/1!1!1!
On peut aussi remarquer qu'un planning est une permutation de la suite
des 3 périodes respectives de A, B et C, donc ça fait 3! permutations.

(2) Il s'agit en fait du problème du damier, où f donne la couleur des
cases et R U R^{-1} la relation d'adjacence horizontale ou verticale
entre les cases.

(i) On a (a,b) R^2 (x,y) ssi on a (u,v) avec (a,b) R (u,v) R
(x,y). Combinant deux +1 sur l'une ou l'autre coordonnée, cela donne 3
possibilités:
(x,y) = (a+2,b) ou (a+1,b+1) ou (a,b+2).
Comme R^{-2} est la relation inverse de R^2, (a,b) R^{-2} (x,y) donne
3 possibilités:
(x,y) = (a-2,b) ou (a-1,b-1) ou (a,b-2).

(ii) Pour (a,b) R (x,y) on a x+y = a+b+1, donc modulo 2 on obtient
f(x,y) congru à f(a,b)+1, en d'autres termes, f(x,y) est le complément
booléen de f(a,b). Pour (a,b) R^2 (x,y), f(x,y) est le complément
booléen du complément booléen de f(a,b), donc f(x,y) = f(a,b); sinon,
on a x+y = a+b+2, congru à a+b modulo 2, d'où f(x,y) = f(a,b).

(iii) Soit S la relation "a la même valeur par f que", c.-à-d. (a,b) S
(x,y) ssi f(a,b) = f(x,y). C'est bien sûr une relation d'équivalence,
et par (ii) elle contient R^2. Donc S contient la relation
d'équivalence engendrée par R^2. Pour montrer que les deux sont
égales, il suffit de voir que S est engendrée par itération de R^2 et
R^{-2}.

Soient (a,b) et (c,d) avec f(a,b) = f(c,d). Si c >= a, on a c = a+n
pour un naturel n, et alors
(a,b) R^2 (a+1,b+1) R^2 ... R^2 (a+n,b+n),
donc pour e=b+n, on a (a,b) R^{2n} (c,e). Si c =< a, on a c = a-n
pour un naturel n, et alors
(a,b) R^{-2} (a-1,b-1) R^{-2} ... R^{-2} (a-n,b-n),
donc pour e=b-n, on a (a,b) R^{-2n} (c,e). Dans les deux cas, on a
f(c,e) = f(a,b) = f(c,d), donc c+e est congru modulo 2 à c+d,
c.-à-d. d et e ont la même parité. Si d >= e, on a d = e+2m pour un
naturel m, et alors
(c,e) R^2 (c,e+2) R^2 ... R^2 (c,e+2m),
donc (c,e) R^{2m} (c,d). Si d =< e, on a d = e-2m pour un naturel m,
et alors
(c,e) R^{-2} (c,e-2) R^{-2} ... R^{-2} (c,e-2m),
donc (c,e) R^{-2m} (c,d). On a ainsi prouvé que (a,b) est relié à
(c,d) par une succession de relations R^2 ou R^{-2}, donc ils sont
reliés par la relation d'équivalence engendrée par R^2.

L'argument est illustré ci-dessous, le point P est relié aux points V
et W par une succession de relations R^2 ou R^{-2}:

--------------x--
-------------x---
------------x-x--
-----------x-----
----V-----x---W--
---------x-------
----x---P--------
-------x---------
----x-x----------
-----x-----------
----x------------

Les classes d'équivalence de "a la même valeur de f que" sont les deux
sous-ensembles de couples d'entiers, celui des couples (a,b) avec a+b
pair, puis celui des couples (a,b) avec a+b impair: les cases noires
et les cases blanches du damier!

(3) (i) f et g sont bijectives:
f o (g o f) = Id est surjective, donc f est surjective;
(f o g) o f = Id est injective, donc f est injective;
g o (f o g) = Id est surjective, donc g est surjective;
(g o f) o g = Id est injective, donc g est injective.

(ii) f = g. Voici 4 preuves:

1. f o (g o f) = (g o f) o g = Id, donc (g o f) a un inverse à gauche
f et un inverse à droite g; or les inverses à gauche et à droite,
s'ils existent tous deux, sont égaux (vu en TD).

2. g o (f o g) = (f o g) o f = Id, donc (f o g) a un inverse à gauche
g et un inverse à droite f; or les inverses à gauche et à droite,
s'ils existent tous deux, sont égaux (vu en TD).

3. Calcul de g o f o g o f:
g o (f o g o f) = g o Id = g  et  (g o f o g) o f = Id o f = f, donc
f = g.

4. Calcul de f o g o f o g:
f o (g o f o g) = f o Id = f  et  (f o g o f) o g = Id o g = g, donc
g = f.

On ne peut rien dire de plus, à part que f^3 = g^3 = Id; par exemple f
= g = rotation d'un tiers de tour dans le plan.