From 0576179cde426fd3b2c674bb1f68782e1454e4a7 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 4 Apr 2019 16:07:07 +0200 Subject: Continue writing exam. --- controle-20190408.tex | 114 ++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 111 insertions(+), 3 deletions(-) diff --git a/controle-20190408.tex b/controle-20190408.tex index 65e25a0..1a9e36d 100644 --- a/controle-20190408.tex +++ b/controle-20190408.tex @@ -206,7 +206,7 @@ ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de type $n-1$. Par exemple, on peut remplacer un jeton de type $1729$ par $42$ jetons de type $1728$ ; on peut aussi le retirer sans remplacement.)\quad(a) Dans ces conditions, que vaut $\gr J(n)$ ? (On -pourra par exemple commencer par calculer $gr J(n)$ pour $n=0,1,2,3$, +pourra par exemple commencer par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule générale, et la démontrer par récurrence sur $n$.)\quad(b) Exprimer de façon simple la stratégie gagnante du jeu considéré dans cette question. @@ -223,7 +223,7 @@ type $k\leq n-1$. Par exemple, on peut remplacer un jeton de type $1729$ par $42$ jetons de type $1728$ ou $1728$ jetons de type $42$ ; on peut aussi le retirer sans remplacement.) Dans ces conditions, que vaut $\gr J(n)$ ? (On pourra par exemple commencer -par calculer $gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule +par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule générale, et la démontrer par récurrence sur $n$.) \medskip @@ -237,12 +237,120 @@ n'importe quels types $ \cdots > \gamma_r$ sont des ordinaux en ordre strictement +décroissant et $n_1,\ldots,n_r$ des entiers naturels non nuls ; +c'est-à-dire qu'il s'agit de la forme normale de Cantor de $\alpha$) +alors on a $\alpha = (\omega^{\gamma_1} \boxdot n_1) \boxplus \cdots +\boxplus (\omega^{\gamma_r} \boxdot n_r)$. + +\emph{Indication :} On imitera de près la démonstration du fait donné +en cours que si $\alpha = 2^{\gamma_1} + \cdots + 2^{\gamma_r}$ (où +$\gamma_1 > \cdots > \gamma_r$ sont des ordinaux en ordre strictement +décroissant ; c'est-à-dire qu'il s'agit de la l'écriture binaire +de $\alpha$) alors on a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus +2^{\gamma_r}$. Il n'y a pas grand-chose à modifier à part remplacer +$\mex$ par $\sup^+$ aux endroits utiles. (Cette question est un peu +longue, mais il est possible de traiter la suite en l'admettant.) + +\medskip + +(4)(a) En déduire la manière dont on calcule $\alpha\boxplus\beta$ à +partir des formes normales de Cantor de +$\alpha$ et $\beta$.\quad(b) En particulier, calculer +$(\omega+1)\boxplus(\omega+1)$, et comparer avec $(\omega+1) + +(\omega+1)$. + +\medskip + +(5) On considère le jeu à deux joueurs suivant : les deux joueurs +s'appellent Blaise et Roxane, et ils jouent tour à tour (on ne précise +pas qui commence) ; l'état du jeu est défini par trois ordinaux, qu'on +notera $(\alpha,\beta,\rho)$, et il est visible de tous ; les coups +possibles de Blaise consistent à diminuer strictement soit l'ordinal +$\alpha$ soit l'ordinal $\beta$ (c'est-à-dire passer de +$(\alpha,\beta,\rho)$ à $(\alpha',\beta,\rho)$ avec $\alpha'<\alpha$ +ou à $(\alpha,\beta',\rho)$ avec $\beta'<\beta$), tandis que les coups +possibles de Roxane consistent à diminuer strictement l'ordinal $\rho$ +(c'est-à-dire passer de $(\alpha,\beta,\rho)$ à $(\alpha,\beta,\rho')$ +avec $\rho'<\rho$) ; le joueur qui ne peut plus jouer a perdu. + +Montrer que, dans ce jeu, Blaise possède une stratégie gagnante +lorsque $\rho > \alpha\boxplus\beta$, que Roxane possède une stratégie +gagnante lorsque $\rho < \alpha\boxplus\beta$, et que le second joueur +possède une stratégie gagnante lorsque $\rho = \alpha\boxplus\beta$. + + % % % -- cgit v1.2.3