Trois étages d'attracteur

Le calcul, étage par étage.

$A_{0} = {t}$ .
$A_{1}$ : $b$ est à $J_{2}$ et son unique coup mène à $t$ ; le $\forall$ est satisfait, donc $b \in A_{1}$ .
$A_{2}$ : $c$ est à $J_{1}$ et l'un de ses coups mène à $b \in A_{1}$ ; le $\exists$ suffit, donc $c \in A_{2}$ .
$A_{3}$ : $e$ est à $J_{2}$ , et ses deux coups mènent dans $A$ ( $c$ et $b$ ) : $e \in A_{3}$ .
$A_{4}$ : $a$ est à $J_{1}$ et peut jouer vers $e$ : $a \in A_{4}$ .
Et l'on s'arrête : $A_{5} = A_{4}$ .

Restent $g$ et $h$ , hors de l'attracteur. $h$ est à $J_{2}$ : il a bien un coup vers $c \in A$ , mais il en a un autre, vers $g$ , et $J_{2}$ prendra celui-là — le $\forall$ échoue. Et $g$ , à $J_{1}$ , n'a que $h$ pour successeur : il y est forcé. Les deux positions forment un cycle $g \leftrightarrow h$ dans lequel $J_{2}$ peut enfermer la partie indéfiniment.

La stratégie gagnante de $J_{1}$ , lue directement dans les étages :

position de $J_{1}$	étage	coup à jouer
$a$	$4$	vers $e$ (étage $3$ )
$c$	$2$	vers $b$ (étage $1$ )

Elle est sans mémoire — un tableau indexé par les positions — et sa correction tient en un variant, au sens du chapitre chap:algo-prog : l'étage décroît strictement à chaque coup. Depuis une position de $J_{1}$ d'étage $k$ , la stratégie descend à un étage $< k$ ; depuis une position de $J_{2}$ d'étage $k$ , tous les coups descendent, puisque c'est la condition même de son entrée dans $A_{k}$ . Un entier positif qui décroît strictement ne le fait qu'un nombre fini de fois : la cible est atteinte en au plus $4$ coups depuis $a$ .

L'erreur à ne pas commettre : croire que $h \in / A$ parce que $c \in A$ « ne suffit pas ». Ce n'est pas une question de quantité, c'est le quantificateur qui change. Sur une position de $J_{2}$ , un seul coup d'évasion annule tous les autres.

Énoncé

Corrigé

Exercices semblables