Le facteur ne repassera pas - Collège Alain Fournier (Orsay)

Un facteur doit distribuer le courrier dans une rue. Celle-ci ne comporte qu'une seule rangée de maisons régulièrement espacées et numérotées 1, 2, ..., n. Le facteur doit distribuer une lettre par maison. Pour cela, il laisse son vélo à la maison 1, y dépose le courrier correspondant, et ensuite distribue les lettres au hasard, puis revient à la maison 1 récupérer son vélo. Il effectue ainsi un trajet, représenté par les numéros successifs des maisons où il a déposé le courrier. Par exemple, si n = 5, un trajet possible est 1, 5, 2, 4, 3, 1. La distance totale parcourue, appelée longueur du trajet, vaut 12 ici. Combien y a-t-il de trajets possibles ? Montrer que tout trajet est de longueur supérieure ou égale à 2(n - 1). Combien y a-t-il de trajets de longueur minimale ? Dans les cas n = 5 et n = 6, déterminer la longueur maximale d'un trajet et donner un exemple de trajet de longueur maximale.