Exercice 1 — Saute grenouille

Sujet

Soient \(m\) et \(n\) deux entiers naturels non nuls donnés. On considère une ligne de \(m+n+1\) cases dans lesquelles on place \(m\) crapauds et \(n\) grenouilles selon la disposition initiale suivante :

• les \(m\) crapauds sont placés dans les \(m\) cases les plus à gauche ;
• les \(n\) grenouilles sont placées dans les \(n\) cases les plus à droite;
• une case est laissée vide.

L'objectif est que les \(m\) crapauds se déplacent vers les \(m\) cases les plus à droite et les \(n\) grenouilles vers les \(n\) cases les plus à gauche. Pour cela, deux types de déplacements sont autorisés :

• un crapaud ou une grenouille peut avancer sur une case immédiatement voisine.
• un crapaud ou une grenouille peut sauter par dessus un animal de l'autre espèce (et un seul à la fois). De plus, les crapauds se déplacent toujours de gauche à droite et les grenouilles de droite à gauche.

Autrement dit, les animaux ne peuvent pas « revenir en arrière ».

Dans tous les cas, il ne peut y avoir deux animaux dans la même case.

Exemple. Par exemple, si \(m=1\) et \(n=2\), il y a \(1+2+1\) cases avec un crapeau à gauche et 2 grenouilles à droite, séparés par une case; on note \(\boldsymbol{C}\) le crapaud et \(\boldsymbol{G}_{1}\) et \(\boldsymbol{G}_{2}\) les deux grenouilles.

Configuration initiale :

\(C\)

\(G_{1}\)

\(G_{2}\)

Configuration finale :

\(G_{1}\)

\(G_{2}\)

\(C\)

Pour passer de l'une à l'autre, une réponse au problème est donnée par la succession d'étapes suivante :

Configuration initiale :

\(C\)

\(G_{1}\)

\(G_{2}\)

\(C\)

\(G_{1}\)

\(G_{2}\)

\(\boldsymbol{C}\) avance d'une case

\(G_{1}\)

\(C\)

\(G_{2}\)

\(\boldsymbol{G}_{1}\) saute par dessus \(\boldsymbol{C}\)

\(G_{1}\)

\(C\)

\(G_{2}\)

\(\boldsymbol{C}\) avance d'une case

\(G_{1}\)

\(G_{2}\)

\(C\)

\(G_{2}\) saute par dessus \(C\)

Configuration finale :

\(G_{1}\)

\(G_{2}\)

\(C\)

1. a) Apporter une réponse au problème lorsque \(m=n=1\).
   b) Apporter une réponse au problème lorsque \(m=n=2\).
   c) Apporter une réponse au problème lorsque \(m=2\) et \(n=3\).