Retournement de situation - Collège Jacques Prévert (Watten) Collège du Westhoek (Coudekerque Branche), École Georges Fortry (Watten)

Titre du sujet
Retournement de situation
Établissement
Collège Jacques Prévert (Watten)
Année
2019-2020
Etablissement(s) jumelé(s)
Collège du Westhoek (Coudekerque Branche)
École Georges Fortry (Watten)
Résumé
On dispose n pions verticalement. Ils sont noirs sur une face, blancs sur l’autre, et sont numérotés de
1 à n. Au début du jeu, chaque pion présente aléatoirement sa face noire ou sa face blanche. À chaque
coup, qu’on appelle une opération dans toute la suite, on retourne un des pions et tous ceux situés au
dessus. L’objectif du jeu est de trouver une séquence d’opérations telle que tous les pions montrent
leur face blanche.
1. Tester quelques exemples : en combien d’opérations peut-on atteindre l’objectif ?
2. Trouver un algorithme qui permette d’atteindre l’objectif en un minimum d’opérations. Quel est
le nombre maximal d’opérations nécessaires ?