DM1 : Ensembles finis, combinatoire, raisonnement par récurrence
Exercice 1
Soit
Exercice 2 : Théorème de Cantor Berstein
Soient
- Soit
l'ensemble des parties
de
telles que
.
Montrer queest un élément de
- On pose
. Montrer que
appartient à
- Montrer que
.
- Dans ce qui suit, on note
l'application réciproque de
telle que
. A l'aide de la question 3, montrer que l'application
de
définie par les formules
est une bijection de
Exercice 3
Dans tout l'exercice,
Une chaîne dans
Une antichaîne dans
Un élément
- Soit
. On suppose que toutes les chaînes de
.
- Montrer que
l'ensemble des éléments maximaux de
est non vide, puis montrer que
- Soit
. Démontrer que toute chaîne de
.
- Montrer que
- Démontrer alors par récurrence le résultat suivant : Soit
. Si toute chaîne de
- Soit
.
- Montrer que si
, alors
ou une antichaîne de cardinal
.
- En déduire que toute suite de
réels distincts possède une sous-suite strictement croissante de longueur
- Montrer que si
Exercice 4
Autour d'une table ronde où siège une commission formée d'un nombre impair de personnes est organisé un vote à plusieurs tours sur une question à laquelle on répond par oui ou par non. Au premier tour, chacun vote selon sa propre opinion. Dès le second tour, chaque membre de la commission modifie son vote en fonction de celui de ses voisins immédiats de table et en suivant la règle suivante : si ces derniers ont un vote contraire au sien, il se range à leur avis, sinon, il conserve sont vote.
- Montrer qu'au bout d'un certain nombre de tours, les avis restent stables.
- Examiner le cas d'un nombre pair de personnes.
On est bien dans la section "défis et énigmes" non ? 
J'ai posté ce DM parce que je sais qu'il est un défi intellectuel pour toute personne un tant soit peu intéressée par les mathématiques et ayant le bagage nécessaire (ce qui n'est même pas mon cas d'ailleurs, j'ai récupéré ce DM d'une personne que je connaissais à LLG mais je n'ai pas du tout le niveau pour le faire).
.