Exercices de khôlle pour la MPSI

Année scolaire 1997-1998

Cinquième semaine (naturels, combinatoire)

David A. Madore ( )

Exercice plutôt facile. On suppose que la relation d’“avoir serré la main” est irréflexive et symétrique, et que l’ensemble des personnes est fini. Montrer que le nombre de personnes ayant serré la main d’un nombre impair de personnes est un nombre pair.

Exercice du même genre. On suppose que la relation d’“être l’ami de” est réflexive et symétrique, et que l’ensemble des personnes est fini. Montrer qu’il existe deux personnes ayant autant d’amis.

Exercice d’Olympiades, assez difficile. Montrer qu’il n’existe pas φ: ℤ → ℤ tel que φ(φ(k)) = k + 1997 pour tout k.

Exercice d’Olympiades, assez difficile. Soit f: ℕ^{∗} → ℕ^{∗} telle que pour tout n ∈ ℕ^{∗}, f(n + 1) > f(f(n)). Montrer que f est l’identité.

Indication : Montrer par récurrence sur n que si f(m) ≤ n alors m ≤ n.

Exercice de Concours Général, assez difficile. Soit p un naturel et n = 2^{p}. On considère les parties A de l’ensemble E = {1, 2, …, n} possédant la propriété suivante : si x ∈ A alors 2x ∉ A. Déterminer le nombre maximal d’éléments d’une telle partie.

Exercice de combinatoire idiot. Montrer que

\binom{a + b}{n} = ∑_{k=0}^{n} \binom{a}{k}\binom{b}{n − k}

Exercice de décomptage (Olympiades). Montrer que le nombre moyen de points fixes d’une permutation de n éléments est 1. Autrement dit : si p_{n}(k) est le nombre de permutations de {1, …, n} ayant k points fixes, alors

∑_{k=0}^{n} kp_{n}(k) = n!

Exercices de dénombrement. Calculer

(o) Le nombre de fonctions de {1, …, k} vers {1, …, n}.

(i) Le nombre de fonctions strictement croissantes de {1, …, k} vers {1, …, n}. (ii) Le nombre de fonctions croissantes de {1, …, k} vers {1, …, n}. (iii) Le nombre de fonctions injectives de {1, …, k} vers {1, …, n}. (iv) Le nombre de fonctions f de {1, …, k} vers {1, …, n} telles que f(i + 1) > f(i) + 1

pour tout i. (Réponse : \binom{n−k+1}{k}).

(v) Le nombre de fonctions f strictement croissantes de {1, …, k} vers {1, …, n} telles que f(i) ait même parité que i pour tout i.

Exercice marrant (Olympiades). Peut-on trouver 1983 naturels deux à deux distincts, inférieurs à 10^{5} tels que trois d’entre eux ne soient pas les termes consécutifs d’une progression arithmétique ?

Exercice de dénombrement. Soit E = {1, …, n}. Combien y a-t-il de k-uplets (A_{1}, …, A_{k}) de parties de E telles que

|A_{1} ∩ ⋯ ∩ A_{k}| = p
|A_{1} ∪ ⋯ ∪ A_{k}| = q
Réponse : \binom{n}{p}\binom{n−p}{q−p}(2^{k} − 2)^{q−p}.