From 4ef57916cfabdc8d3078bfecbf120f48d988b742 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 11 Apr 2023 17:09:36 +0200 Subject: Start writing test for 2023 (first exercise on nim positions). --- controle-20230417.tex | 267 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 267 insertions(+) create mode 100644 controle-20230417.tex (limited to 'controle-20230417.tex') diff --git a/controle-20230417.tex b/controle-20230417.tex new file mode 100644 index 0000000..e7fcdcf --- /dev/null +++ b/controle-20230417.tex @@ -0,0 +1,267 @@ +%% 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} -- cgit v1.2.3