Les grenouilles

Deux rangées de grenouilles se font face, séparées par un nénuphar libre ; elles avancent ou sautent par-dessus une adversaire, sans jamais reculer. Il faut les échanger. Un double comptage montre que toute solution a exactement $nm + n + m$ coups.

Sur une file de $n + m + 1$ nénuphars, $n$ grenouilles bleues à gauche et $m$ orange à droite, de $1$ à $6$ par couleur, doivent échanger leurs places. Une grenouille avance d'un nénuphar s'il est libre, ou saute par-dessus une seule grenouille de l'autre couleur ; elle ne recule jamais. La page signale l'impasse quand plus rien ne bouge, permet d'annuler, et peut jouer un bon coup sur demande.

Ce que cela signifie : chaque bleue doit croiser chaque orange, et un croisement est un saut, donc toute solution compte exactement $nm$ sauts. La distance totale à parcourir est $n(m+1) + m(n+1) = 2nm + n + m$, dont les sauts couvrent $2nm$ : il reste $n + m$ pas. Toute solution a donc $nm + n + m$ coups, soit $15$ pour trois grenouilles de chaque couleur. Par parcours exhaustif, la page trouve pour ce cas $72$ positions accessibles, dont $13$ impasses, et exactement deux solutions, comme pour toutes les tailles où chaque couleur compte au moins deux grenouilles.

Le piège le plus courant est de chercher une solution plus courte : il n'y en a pas, toutes ont la même longueur. La difficulté est de ne pas se bloquer.