Oral X

⋆ a) Pour n dans N*, soit αn le nombre de permutations de {1,…,n} dont tous les cycles sont de longueur ≤ n⁄2. Calculer αn et déterminer la limite de (αn⁄n!) quand n → +∞.
b) Un dictateur enferme 100 mathématiciens dans une pièce et leur tient le discours suivant. ≪ J’ai écrit chacun de vos noms sur un papier et ai mis chaque papier dans un des 100 coffres de la pièce voisine. Chacun de vous va venir ouvrir 50 coffres qu’il choisira et revenir sans avoir la possibilité de communiquer avec les autres. Vous serez libres si chacun de vous trouve le coffre contenant le papier portant son nom. Dans le cas contraire, on recommence (et bien sûr je change le contenu des coffres). ≫ Imaginer une stratégie permettant aux mathématiciens d’espérer être libérés en un temps raisonnable.

Une idée pour le premier exercice.l'exercice est équivalent à trouver le nombre de permutations de {1,2,...,2n} dont tous les cycles sont de longueurs inférieures à n.
soit k un entier entre n+1 et 2n. il y a 2n façon de choisir un premier élément du support du k-cycle, et 2n-1 de choisir un deuxième élément,et ainsi de suite....il y a (2n)!/(2n-k)! façons de choisir dans l'ordre le support du k-cycle. Et vue qu'on obtient plusieurs fois le même cycle, alors pour tout élément du support, il peut être choisi comme étant le premier. En somme, il y a (2n)!/(2n-k)!k façons de choisir le k-cycle. alors lim a(2n)/(2n)!=0.