%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{ucs} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} \usepackage{hyperref} % %\externaldocument{notes-mitro206}[notes-mitro206.pdf] % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\thingy{% \refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% \refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} \renewcommand{\qedsymbol}{\smiley} % \newcommand{\outnb}{\operatorname{outnb}} \newcommand{\downstr}{\operatorname{downstr}} \newcommand{\precs}{\operatorname{precs}} \newcommand{\mex}{\operatorname{mex}} \newcommand{\id}{\operatorname{id}} \newcommand{\limp}{\Longrightarrow} \newcommand{\gr}{\operatorname{gr}} \newcommand{\rk}{\operatorname{rk}} \newcommand{\fuzzy}{\mathrel{\|}} % \DeclareUnicodeCharacter{00A0}{~} % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} % \DeclareFontFamily{U}{manual}{} \DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} \newcommand{\manfntsymbol}[1]{% {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} \newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped \newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% \hbox to0pt{\hskip-\hangindent\dbend\hfill}} % \newcommand{\spaceout}{\hskip1emplus2emminus.5em} \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\par\smallbreak\else\egroup\par\fi} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} \date{13 avril 2022} \maketitle \pretolerance=8000 \tolerance=50000 \vskip1truein\relax \noindent\textbf{Consignes.} Les exercices sont totalement indépendants. Ils pourront être traités dans un ordre quelconque, mais on demande de faire apparaître de façon très visible dans les copies où commence chaque exercice. \medbreak L'usage de tous les documents (notes de cours manuscrites ou imprimées, feuilles d'exercices, livres) est autorisé. L'usage des appareils électroniques est interdit. \medbreak Durée : 2h Barème \emph{indicatif} : \textcolor{red}{XXX}. \ifcorrige Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse). \else Cet énoncé comporte \textcolor{red}{XXX} pages (page de garde incluse). \fi \vfill {\noindent\tiny \immediate\write18{sh ./vc > vcline.tex} Git: \input{vcline.tex} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pagebreak % % % \exercice On considère le jeu de nim éventuellement transfini. (On rappelle qu'il est défini de la manière suivante : une position du jeu est un tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a « $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à décroître strictement \emph{un et un seul} des $\alpha_i$, autrement dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers $(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis à la place de $\alpha_i$.) Pour chacune des positions suivantes, dire si c'est une position P (c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N (c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce dernier cas, donner un coup gagnant possible pour le joueur en question. (a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne avec $2$, et une ligne avec $3$) \begin{corrige} On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la position est $0$, et c'est donc une position P. \end{corrige} (b) $(3,6,9)$ \begin{corrige} On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus 2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6 \oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de la position est $12$, et c'est donc une position N. Pour trouver un coup gagnant, c'est-à-dire un coup vers une position P, on cherche à annuler la valeur de Grundy : autrement dit, on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n \oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus 12 < n$. On vérifie facilement que la seule possibilité est de réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$ bâtonnets. Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$. \end{corrige} (c) $(\omega,\omega2,\omega3)$ \begin{corrige} En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 = 2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de Grundy de la position est $0$, et c'est donc une position P. \end{corrige} (d) $(\omega,\omega^2,\omega^3)$ \begin{corrige} En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 = 2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc $\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} + 2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de Grundy de la position est $\gamma \neq 0$, et c'est cdonc une position N. Comme dans la question (b), on cherche à annuler la valeur de Grundy, autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 + \omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2} \oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit. On vérifie facilement que la seule possibilité est de réduire la ligne ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 + \omega$ bâtonnets. Bref, le seul coup gagnant est $(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$. \end{corrige} (e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$ \begin{corrige} En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a $\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} = 2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega} = 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} = 2^{\omega^\omega}$. Le raisonnement est alors exactement analogue à la question (d) (car la seule chose qui importe dans cette question ait qu'on ait affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} + 2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega + \omega \neq 0$ donc c'est une position N, et le seul coup gagnant est $(\omega,\omega^\omega,\omega^{\omega^\omega}) \to (\omega,\omega^\omega,\omega^\omega + \omega)$. \end{corrige} (f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0 < \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme la limite, c'est-à-dire la borne supérieure, de la suite $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 = (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1 = \omega^{(\varepsilon_n) + 1}$ et $u_2 = \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas besoin de ce fait.} vérifiant $\varepsilon = \omega^\varepsilon$. \begin{corrige} Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a $\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} = 2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} = 2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} = 2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$). Le raisonnement est alors exactement analogue aux questions (d) et (e) (car la seule chose qui importe dans ces questions ait qu'on ait affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} + 2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq 0$ donc c'est une position N, et le seul coup gagnant est $(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1, \varepsilon_2, \varepsilon_2 + \varepsilon_1)$. \end{corrige} (g) Donner un exemple de position N du jeu de nim (de préférence fini) avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les $\alpha_i$ sont deux à deux distincts), où il existe strictement plus qu'un coup gagnant pour le joueur qui doit jouer. (Pour indication, ceci est possible à partir de trois lignes de bâtonnets.) \begin{corrige} On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus n_3$ et de façon analogue pour les trois autres. On cherche donc, par exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$. Ceci n'est pas difficile en prenant par exemple pour $n_1$ une puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et de $n_3$ mais telle qu'en enlevant on obtient des nombres strictement plus petits. Par exemple, la position $(2,6,7)$ (de valeur de Grundy $2\oplus 6\oplus 7 = 3 =: g$) admet des coups gagnants vers $(2,5,7)$ ou $(2,6,4)$ ou même $(1,6,7)$. \end{corrige} % % % \end{document}