La puce - Lycée Léonard de Vinci (Calais)

Sur chaque case d’un rectangle de taille finie m×n, une flèche indique une des quatre directions.Une puce se trouve sur une des cases. Chaque seconde, elle change de case et va sur la case voisine en suivant la direction indiquée par la flèche de la case où elle se trouve. Lorsque la puce quitte une case, la flèche de la case qu’elle vient de quitter tourne d’un quart de tour dans le sens des aiguilles d’une montre ; c’est la seule flèche qui tourne à cet instant. Il y a un mur sur les quatre côtés du damier, sauf à un endroit : une des cases du bord n’a pas de mur. Lorsque la puce est bloquée par le mur, elle ne change pas de case, mais
la flèche tourne quand même d’un quart de tour. Si la puce arrive sur la case du bord sans mur et que la flèche de la case pointe vers la sortie, elle sort.
— La puce finira-t-elle toujours par sortir ?
— Si oui, peut-on donner une majoration ne dépendant que de m et n du temps qu’il lui faudra ?
— Si non, proposer un damier, une sortie, une position de départ pour la puce et une configuration des flèches tels que la puce reste éternellement sur le damier.