Sujet
Aux échecs, un cavalier se déplace de la façon suivante :
- Sur un échiquier de dimension \(3 \times 4\), déplacer un cavalier afin qu'il parcoure l'ensemble des cases, sans repasser deux fois par la même.
- Est-il possible sur un échiquier de dimension \(3 \times 5\), que le cavalier réalise un cycle. C'est-à-dire qu'il parcoure l'ensemble des cases sans repasser deux fois par la même et en revenant à la case de départ?
- a) On joue désormais sur un échiquier \(3 \times 3\), où chaque case est numérotée de 1 à 9 comme suit :
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Au départ le cavalier se trouve sur la case 1. On place dans une urne neuf boules numérotées de 1 à 9 indiscernables au toucher. On tire ainsi au sort le numéro de la case sur laquelle le cavalier doit se rendre en un minimum de coups puis on remet la boule dans l'urne. Chaque numéro a ainsi la même probabilité de sortir. On interrompt le tirage si la case est inaccessible.
Au bout de combien de tirages dépasse-t-on \(90 \%\) de chance que la partie ait été interrompue?
- Déplacement du cavalier pour occuper toutes les cases :
| 1 | 4 | 7 | 10 |
| 8 | 11 | 2 | 5 |
| 3 | 6 | 9 | 12 |
- Lorsqu'un cavalier se déplace il change obligatoirement de couleur de case à chaque coup. Sur un damier \(3 \times 5\) il lui faut faire 15 coups pour réaliser un cycle. Or après le quinzième coup il se trouvera sur une case de couleur différente, qui ne peut donc pas être la case de départ.
- a) Seule la case 5 est inaccessible, elle a \(1 / 9\) chance de sortir. Si on note \(A n\) : «la partie a été interrompue avant le \((n+1)\)-ième tirage \(\gg\) on a \(P(A n)=1-(8 / 9) n\), et \(P(A n)>0,9\) pour \(n>19\).
b) \(\alpha\) - On entre \(8:\left|u_{8}-u_{1}\right|=|8-1|=7 ; x=\min (7 ; 8-7)=1\) et \(c=1\)
On entre \(7:\left|u_{7}-u_{8}\right|=|3-8|=5 ; x=\min (5 ; 8-5)=3\) et \(c=4\)
On entre \(3:\left|u_{3}-u_{7}\right|=|7-3|=4 ; x=\min (4 ; 8-4)=4\) et \(c=8\)
On entre \(5:\left|u_{5}-u_{3}\right|=|0-7|=7 ; x=\min (7 ; 8-7)=1\) et \(c=9\)
Sortie \(9-1=8\)
\(\beta\) - Algorithme
Variables : p,n,x,c : nombres entiers
u : liste de nombres entiers
Initialisation : Affecter à p la valeur 1
Affecter à c la valeur 0
Affecter à u la liste {1;4;7;6;0;2;3;8;5}
Traitement : Tant que p=5 Faire
Début TantQue
Demander un nombre entier de 1 à 9, l'affecter à n
Affecter à x la valeur absolue de (u[n]-u[p])
Affecter à x la valeur minimum entre x et (8-x)
Affecter à c la valeur de c+x
Affecter à p la valeur de n
Fin TantQue
Sortie : Afficher c-x
Cet algorithme indique le nombre de déplacements que doit effectuer le cavalier pour suivre le parcourt imposé en un minimum de coups.