\documentclass{article}
\usepackage{amssymb}
\usepackage{upsnum}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[francais,english]{babel}
\usepackage{latexsym}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Mon Jan 17 20:51:39 2000}
%TCIDATA{LastRevised=Sun Feb 25 18:06:03 2001}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{CSTFile=article.cst}
\setlength{\textwidth}{520 pt}
\setlength{\textheight}{710 pt}
\setlength{\oddsidemargin}{-40 pt}
\setlength{\topmargin}{-60 pt}
\setlength{\parindent}{0 pt}
\input{tcilatex}
\begin{document}
\begin{center}
\underline{\underline{{\LARGE INFORMATIQUE - Concours Polytechnique 2000}}}
\end{center}
\bigskip
\begin{center}
{\large Premi\`{e}re partie. Parties d'un ensemble}
\bigskip
\end{center}
\QTP{Body Math}
\textbf{Question 1.}
\begin{verbatim}
let rec card = function [] -> 0 |i::q -> 1 + card q;;
\end{verbatim}
\QTP{Body Math}
\textbf{Question 2.} \textbf{\ }
\begin{verbatim}
let rec delta p1 p2 =
match p1,p2 with
[],_ -> p2
|_,[] -> p1
|i1::q1,i2::q2 when i1 = i2 -> delta q1 q2
|i1::q1,i2::_ when i1 < i2 -> i1::delta q1 p2
|_,i2::q2 -> i2::delta p1 q2;;
\end{verbatim}
\QTP{Body Math}
La fonction delta parcourt simultan\'{e}ment les deux parties et
s'arr\^{e}te d\`{e}s que l'une des deux est enti\`{e}rement parcourue. Dans
le pire des cas, les deux parties sont parcourues enti\`{e}rement, et on a
donc bien une complexit\'{e} born\'{e}e par la somme des cardinaux de ces
parties.\newline
A chaque \'{e}tape, les deux \'{e}l\'{e}ments les plus petits (en t\^{e}te
des listes) sont compar\'{e}s. S'ils sont \'{e}gaux, ils n'apparaissent pas
dans la diff\'{e}rence sym\'{e}trique des parties. Sinon, le plus petit ne
peut pas appara\^{i}tre dans l'autre partie, et doit donc \^{e}tre
ajout\'{e} \`{a} la diff\'{e}rence sym\'{e}trique.\newline
Dans tous les cas, on enl\`{e}ve un \'{e}l\'{e}ment \`{a} au moins l'une des
parties, et on l'ajoute \`{a} la diff\'{e}rence sym\'{e}trique des reliquats.%
\newline
\newline
On peut remarquer \`{a} propos de la loi $\Delta $ qu'elle est associative,
commutative, d'\'{e}l\'{e}ment neutre $\emptyset $ , et que chaque ensemble
est son propre sym\'{e}trique, de telle sorte qu'elle munit l'ensemble des
parties d'un ensemble d'une structure de groupe ab\'{e}lien. Ces
propri\'{e}t\'{e}s seront utilis\'{e}es dans les questions suivantes.
\begin{verbatim}
\end{verbatim}
\QTP{Body Math}
\textbf{Question 3.} \textbf{\ }
\begin{verbatim}
let test p1 p2 =
let rec imprime_partie = function
[] -> print_newline()
|i::q -> printf__printf ''%d '' i; imprime_partie q
in imprime_partie (delta p1 p2);;
\end{verbatim}
\QTP{Body Math}
Il s'agit d'un banal parcours de la partie, en imprimant tour \`{a} tour
tous ses \'{e}l\'{e}ments, appliqu\'{e} ensuite \`{a} la diff\'{e}rence
sym\'{e}trique des parties en argument. On aurait aussi pu utiliser
directement la fonction de biblioth\`{e}que do\_list.
\bigskip
\pagebreak
\begin{center}
{\large Deuxi\`{e}me partie. Enum\'{e}ration des parties par incr\'{e}ment}
\end{center}
\QTP{Body Math}
\textbf{Question 4.} \textbf{\ }
\begin{verbatim}
let succ p =
let rec insere j = function
[] -> [j] |i::q when j < i -> j::i::q |i::q -> insere (j+1) q
in insere 0 p;;
\end{verbatim}
\QTP{Body Math}
On utilise le principe de l'addition d'une puissance de 2 \`{a} un nombre
\'{e}crit en base 2.\newline
Si l'exposant de cette puissance ne figure pas dans la liste des exposants
non nuls de la d\'{e}composition du nombre, il suffit de l'ins\'{e}rer dans
la liste sans modifier les autres termes. Sinon, on la supprime, et on ins%
\`{e}re la puissance d'exposant imm\'{e}diatement sup\'{e}rieur. Au d\'{e}%
part, on ajoute 1, donc on ins\`{e}re 0, puis on proc\`{e}de r\'{e}%
cursivement en fonction de la pr\'{e}sence ou non d'une retenue.
\QTP{Body Math}
$\bigskip $\newline
\textbf{Question 5.a)}
\QTP{Body Math}
%\newline
\begin{verbatim}
let test_incr N =
let p1 = ref [] and p2 = ref []
in
while card !p1 <> N do
p2 := succ !p1;
test !p1 !p2;
print_newline ();
p1 := !p2
done;
test !p1 [];;
\end{verbatim}
\QTP{Body Math}
$\bigskip $
\QTP{Body Math}
On r\'{e}alise une boucle dont chaque tour traite le passage au successeur
de la partie courante.\newline
On commence \'{e}videmment avec la partie vide, mais il faut s'arr\^{e}ter
lorqu'on a atteint $I_{N}$, ce qu'on peut tester en calculant le cardinal de
la partie courante, qui vaut alors $N$ pour la premi\`{e}re fois.
\QTP{Body Math}
$\bigskip $
\QTP{Body Math}
\textbf{Question 5.b)}
\QTP{Body Math}
Appelons $x_{n}$ le nombre d'interrupteurs \`{a} commuter pour r\'{e}aliser
le test sur $n$ interrupteurs.\newline
Pour r\'{e}aliser ce test sur $n+1$ interrupteurs, on laisse lev\'{e} le $%
(n+1)$-i\`{e}me d'entre eux, et on r\'{e}alise le test sur les $n$ premiers
dans cette configuration (soit $x_{n}$ commutations), puis on abaisse le $%
(n+1)$-i\`{e}me ($1$ commutation), et on remet \c{c}a avec les $n$ premiers (%
$x_{n}$ commutations). Enfin on rel\`{e}ve le dernier ($1$ commutation). En
d\'{e}finitive, on a donc $x_{n+1}=2x_{n}+2$, ce qui se r\'{e}sout en $%
x_{n}+2=2^{n}\left( x_{0}+2\right) $.\newline
Comme $x_{0}=0$, on obtient finalement:
\begin{center}
\underline{Le nombre d'interrupteurs \`{a} commuter pour r\'{e}aliser ce
test sur $N$ interrupteurs est $2^{N+1}-2$}
%\\[0pt]
\end{center}
\bigskip
\pagebreak
\begin{center}
{\large Troisi\`{e}me partie. Enum\'{e}ration des parties par un code de Gray%
}
\end{center}
\QTP{Body Math}
$\bigskip $
\QTP{Body Math}
\textbf{Question 6.a)}
\QTP{Body Math}
$\newline
T\left( 4\right) =$ $<0,1,0,2,0,1,0,3,0,1,0,2,0,1,0>$
\QTP{Body Math}
$\bigskip $\newline
\textbf{Question 6.b)}
\QTP{Body Math}
%\newline
$S_{0}=\{\}\qquad S_{1}=\{0\}\qquad S_{2}=\{0,1\}\qquad S_{3}=\{1\}\qquad
S_{4}=\{1,2\}\qquad S_{5}=\{0,1,2\}$
\QTP{Body Math}
$S_{6}=\{0,2\}\qquad S_{7}=\{2\}\qquad S_{8}=\{2,3\}\qquad
S_{9}=\{0,2,3\}\qquad S_{10}=\{0,1,2,3\}$
\QTP{Body Math}
$S_{11}=\{1,2,3\}\qquad S_{12}=\{1,3\}\qquad S_{13}=\{0,1,3\}\qquad
S_{14}=\{0,3\}\qquad S_{15}=\{3\}$\newline
\QTP{Body Math}
$\newline
$\textbf{Question 7.a)}
\QTP{Body Math}
%\newline
On peut facilement montrer par r\'{e}currence sur $n\geq 1$ que la suite $%
T\left( n\right) $ contient $2^{n}-1$ termes, dont chaque valeur figure un
nombre pair de fois, sauf la valeur centrale $n-1$ qui ne figure qu'une fois.%
\newline
Mais par associativit\'{e} et commutativit\'{e}, $S_{2^{n}-1}=S_{0}%
\bigtriangleup \left\{ t_{0}\right\} \bigtriangleup ..\bigtriangleup \left\{
t_{2^{n}-1}\right\} $ peut se r\'{e}ordonner en regroupant les parties
\'{e}gales entre elles. Comme la diff\'{e}rence sym\'{e}trique de deux
parties \'{e}gales est vide, il ne reste plus que la partie $\left\{
n-1\right\} $ \`{a} ne pas \^{e}tre simplifi\'{e}e. En conclusion:
\begin{center}
\underline{$S_{2^{n}-1}=\left\{ n-1\right\} $}
\end{center}
\QTP{Body Math}
$\newline
$\textbf{Question 7.b)}
\QTP{Body Math}
%\newline
Si $0\leq i<2^{n},S_{2^{n}+i}=S_{2^{n}-1}\Delta \left\{ t_{2^{n}-1}\right\}
\Delta \left\{ t_{2^{n}}\right\} \Delta \left\{ t_{2^{n}+1}\right\} \Delta
...\Delta \left\{ t_{2^{n}+i}\right\} $.\newline
Or il est clair que $t_{2^{n}+i}=t_{i}$. Donc $\left\{ t_{2^{n}}\right\}
\Delta \left\{ t_{2^{n}+1}\right\} \Delta ...\Delta \left\{
t_{2^{n}+i}\right\} =S_{i}$. De plus $t_{2^{n}-1}=n$.\newline
Enfin, d'apr\`{e}s 7.a), on a $S_{2^{n}-1}=\left\{ n-1\right\} $.\newline
En d\'{e}finitive, on a donc $S_{2^{n}+i}=\left\{ n-1\right\} \Delta \left\{
n\right\} \Delta S_{i}=\left\{ n-1,n\right\} \Delta S_{i}$.
\begin{center}
\underline{$S_{2^{n}+i}=\left\{ n-1,n\right\} \Delta S_{i}$}
\end{center}
\QTP{Body Math}
$\newline
$
\QTP{Body Math}
$\bigskip $\pagebreak
\QTP{Body Math}
\textbf{Question 7.c)}
\QTP{Body Math}
%\newline
Montrons par r\'{e}currence sur $n$ que $\left\{
S_{0},...,S_{2^{n}-1}\right\} $ est l'ensemble $P_{n}$ des parties de $I_{n}$%
.
\begin{itemize}
\item Pour $n=0$, c'est \'{e}vident car $\left\{ S_{0}\right\} =\left\{
\emptyset \right\} =P_{0}$.
\item D'apr\`{e}s 7.b), $\left\{ S_{0},...,S_{2^{n+1}-1}\right\} =\left\{
S_{0},...,S_{2^{n}-1}\right\} \cup \left\{ \left\{ n-1,n\right\} \Delta
S_{0},...,\left\{ n-1,n\right\} \Delta S_{2^{n}-1}\right\} $.\newline
Cette r\'{e}union est disjointe, car $\forall i<2^{n},n\notin
S_{i}\Longleftrightarrow \forall i<2^{n},n\in \left\{ n-1,n\right\} \Delta
S_{i}$.\newline
Par hypoth\`{e}se de r\'{e}currence, $\left\{ S_{0},...,S_{2^{n}-1}\right\}
=P_{n}=\left\{ q\in P_{n+1},n\notin q\right\} $.\newline
D'autre part, la loi $\Delta $ \'{e}tant une loi de groupe sur $P_{n}$,
l'application $\Phi :p\mapsto \left\{ n-1\right\} \Delta p$ est une
bijection de $P_{n}$ sur lui-m\^{e}me.\newline
Il en r\'{e}sulte que $\left\{ \left\{ n-1,n\right\} \Delta
S_{0},...,\left\{ n-1,n\right\} \Delta S_{2^{n}-1}\right\} =\left\{ \left\{
n\right\} \Delta p,p\in P_{n}\right\} =\left\{ q\in P_{n+1},n\in q\right\} $.%
\newline
En effectuant la r\'{e}union de $\left\{ S_{0},...,S_{2^{n}-1}\right\} $ et
de $\left\{ \left\{ n-1,n\right\} \Delta S_{0},...,\left\{ n-1,n\right\}
\Delta S_{2^{n}-1}\right\} $, on trouve bien $P_{n+1}$.
\end{itemize}
\begin{center}
\underline{$\forall n\in \mathbb{N},\left\{ S_{0},...,S_{2^{n}-1}\right\}
=P_{n}$}
\end{center}
\QTP{Body Math}
$\newline
$\textbf{Question 8.a)}
\begin{verbatim}
let test_gray N =
let rec T n =
match n with
0 -> []
|_ -> let l = T (n-1) in l@((n-1)::l)
in
let f i = printf__printf ''%d '' i; print_newline()
in
do_list f (T N);
printf__printf ''%d '' (N-1);print_newline();;
\end{verbatim}
\QTP{Body Math}
$\bigskip $\newline
Le principe de cet algorithme est de parcourir les sous-ensembles de $I_{N}$
dans l'ordre des $S_{i}$.\newline
Mais dans ce cas, $S_{i}\Delta S_{i+1}=S_{i}\Delta S_{i}\Delta \left\{
t_{i}\right\} =\left\{ t_{i}\right\} $. Il suffit donc d'afficher la liste
des $\left( t_{i}\right) _{0\leq i\leq 2^{N}-2}$, puis d'afficher le dernier
commutateur \`{a} relever pour revenir \`{a} la situation initiale, soit $%
N-1 $.\newline
Etant donn\'{e} $N$, on construit d'abord $T\left( N\right) $ \`{a} l'aide
d'une fonction r\'{e}cursive, puis on en affiche les \'{e}l\'{e}ments.
\QTP{Body Math}
$\newline
$\textbf{Question 8.b)}
\QTP{Body Math}
$\newline
$L'explication de la question pr\'{e}c\'{e}dente montre qu'il y a exactement
$2^{N}-1+1$ interrupteurs \`{a} commuter.
\begin{center}
\underline{Il y a exactement $2^{N}$ interrupteurs \`{a} commuter par cette
m\'{e}thode}
\end{center}
\QTP{Body Math}
%\newline
\underline{On ne peut pas faire mieux}, car il y a exactement $2^{N}$
configurations \`{a} tester, correspondant toutes \`{a} une configuration
distincte des interrupteurs, et exigeant par cons\'{e}quent la commutation
d'au moins $1$ interrupteur pour passer de l'une \`{a} l'autre.\newline
$\newline
$\textbf{Question 9.a)}
\QTP{Body Math}
$\newline
$Montrons par r\'{e}currence sur $n$ que $\forall i\in \left[ 2^{n},2^{n+1}-1%
\right] ,i$ impair $\Longrightarrow t_{i}=1+\min \left( S_{i}\right) $.
\begin{itemize}
\item Pour $n=0$, on a bien $t_{1}=1=1+0$ et $S_{1}=\{0\}$.
\item Supposons la propri\'{e}t\'{e} vraie jusqu'au rang $n$. Soit $i$
impair \'{e}l\'{e}ment de $\left[ 2^{n+1},2^{n+2}-1\right] $.\newline
- Si $i=2^{n+2}-1$, alors $S_{i}=\left\{ n+1\right\} $ (question 7.a)),
tandis que $t_{i}=n+2=1+\min \left( S_{i}\right) $.\newline
- Supposons maintenant $i<2^{n+2}-1$. Alors $\forall j\in S_{i},j\leq n$.%
\newline
D'apr\`{e}s la question 7.b), on a $S_{i}=S_{i-2^{n+1}}\Delta \left\{
n,n+1\right\} $.\newline
Or $i-2^{n+1}$ est impair, et appartient \`{a} $\left[ 0,2^{n+1}-2\right] $.%
\newline
Par hypoth\`{e}se de r\'{e}currence, on a $t_{i-2^{n+1}}=1+\min \left(
S_{i-2^{n+1}}\right) $. Mais on sait que $t_{i-2^{n+1}}=t_{i}$ (voir
question 7.b)).\newline
Il reste donc \`{a} prouver que $\min \left( S_{i}\right) =\min \left(
S_{i-2^{n+1}}\right) $. Or $S_{i}=S_{i-2^{n+1}}\Delta \left\{ n,n+1\right\} $%
.\newline
Comme $S_{i-2^{n+1}}\neq \left\{ n\right\} $ (puisque $i\neq
2^{n+2}-1\Longrightarrow i-2^{n+1}\neq 2^{n+1}-1$), on a d'abord $%
S_{i-2^{n+1}}\Delta \left\{ n\right\} \neq \emptyset $.\newline
Ensuite, $\forall j\in S_{i-2^{n+1}},j\leq n\Longrightarrow \min \left(
S_{i-2^{n+1}}\Delta \left\{ n\right\} \right) =\min \left(
S_{i-2^{n+1}}\right) $.\newline
Enfin $\min \left( S_{i-2^{n+1}}\Delta \left\{ n,n+1\right\} \right) =\min
\left( S_{i-2^{n+1}}\Delta \left\{ n\right\} \right) $, ce qui ach\`{e}ve la
preuve.
\end{itemize}
\begin{center}
\underline{$\forall i>0,t_{i}$ impair $\Longrightarrow t_{i}=1+\min \left(
S_{i}\right) $}
\end{center}
\QTP{Body Math}
$\newline
$\textbf{Question 9.b)}
\QTP{Body Math}
$\bigskip $
\begin{verbatim}
let rec gray = function
[] -> [0]
|p -> if (card p) mod 2 = 0 then delta p [0] else delta p [1 + hd p];;
\end{verbatim}
\QTP{Body Math}
$\bigskip $
\QTP{Body Math}
On calcule la parit\'{e} de l'indice correspondant \`{a} la partie $S_{i}$
en argument gr\^{a}ce \`{a} son cardinal. En effet, comme le passage d'une
partie \`{a} la suivante se fait par diff\'{e}rence sym\'{e}trique avec un
singleton, il y a ou adjonction, ou suppression de l'\'{e}l\'{e}ment
correspondant, et donc inversion de la parit\'{e}.\newline
Ensuite, si $i$ est pair, c'est que $t_{i}$ est nul, et alors on sait
calculer le successeur par diff\'{e}rence sym\'{e}trique avec $\left\{
0\right\} $. Sinon, la question 9.a) permet de calculer $t_{i}$ \`{a} partir
de $S_{i}$, ce qui permet aussi de calculer $S_{i+1}$.
\begin{center}
{\large Quatri\`{e}me partie. Enum\'{e}ration des parties par un code de Gray%
}
\end{center}
\QTP{Body Math}
$\bigskip $
\QTP{Body Math}
\textbf{Question 10.}
\begin{verbatim}
let rec test_sur p1 p2 =
match p1,p2 with
[],_ -> do_list (printf__printf ''%d '') p2
|_,[] -> do_list (printf__printf ''%d '') p1
|i1::q1,i2::_ when i1 < i2 -> printf__printf ''%d '' i1;
test_sur q1 p2
|i1::q1,i2::q2 when i1 = i2 -> test_sur q1 q2
|i1::q1,i2::q2 -> test_sur p1 q2;$_{{}}$
printf__printf ''%d '' i2;;
\end{verbatim}
\QTP{Body Math}
%\newline
On parcourt simultan\'{e}ment les deux parties dans le m\^{e}me esprit que
pour le programme de la fonction delta, afin de n'imprimer que les
interrupteurs pr\'{e}sents dans l'une seulement des deux parties, mais en
adoptant la strat\'{e}gie suivante: d\`{e}s qu'on rencontre un interrupteur
\`{a} commuter dans la partie p1, on l'imprime (ce qui revient \`{a} le
relever). Si par contre on rencontre un interrupteur \`{a} commuter dans la
partie p2, on le laisse en attente et on examine les suivants (ce qui
revient \`{a} diff\'{e}rer son abaissement).\newline
De ce fait tous les interrupteurs \`{a} relever dans la partie de d\'{e}part
seront relev\'{e}s avant qu'on ne commence \`{a} abaisser ceux qui doivent l'%
\^{e}tre pour atteindre la partie cible.\pagebreak
\QTP{Body Math}
\textbf{Question 11.a)}
\QTP{Body Math}
%\newline
Il est clair que la suite $l_{n,k}$ est d\'{e}finie par les relations
suivantes:
\begin{equation*}
\forall n,k\geq 1,\left\{
\begin{tabular}{l}
$\left( 1\right) :l_{1,k}=1$ \\
$\left( 2\right) :l_{n+1,1}=l_{n,k}+2$ \\
$\left( 3\right) :l_{n+1,k+1}=l_{n,k+1}+l_{n,k}+1$%
\end{tabular}
\right.
\end{equation*}
\newline
Or, en posant $C_{n}^{j}=0$ si $n [0]
|_,1 -> (T (n-1) 1) @ [n - 2;n - 1]
|_ -> (T (n-1) k) @ [n - 1] @ (rev (T (n - 1) (k - 1)))
in
do_list (printf__printf ''%d '') (T N K);
printf__printf ''%d '' (N - 1);;
\end{verbatim}
\QTP{Body Math}
$\newline
$\textbf{Question 13.}\newline
\newline
La solution de cette question est de Gilbert Primet.
\QTP{Body Math}
Le test des configurations d'au plus $k$ interrupteurs baiss\'{e}s parmi $n$
n\'{e}cessite que toutes les configurations soient test\'{e}es au moins une
fois, soit au moins $s_{n,k}$ configurations correspondant \`{a} tous les
sous-ensembles d'au plus $k$ \'{e}l\'{e}ments dans un ensemble \`{a} $n$
\'{e}l\'{e}ments.
\QTP{Body Math}
De plus, comme on part de l'ensemble vide et qu'on aboutit \`{a} l'ensemble
vide en modifiant \`{a} chaque nouvelle configuration un seul
\'{e}l\'{e}ment \`{a} la fois, il y a lors du test autant de configurations
\`{a} nombre pair d'interrupteurs baiss\'{e}s que de configurations \`{a}
nombre impair d'interrupteurs baiss\'{e}s. Il faut donc ajouter \`{a} $%
s_{n,k}$ la valeur absolue de la diff\'{e}rence du nombre de parties de
cardinal pair et du nombre de parties de cardinal impair parmi les parties
\`{a} au plus $k$ \'{e}l\'{e}ments dans un ensemble \`{a} $n$
\'{e}l\'{e}ments, soit $\left| \sum\limits_{j=0}^{j=k}\left( -1\right)
^{j}C_{n}^{j}\right| $.
\QTP{Body Math}
Mais on montre facilement, par r\'{e}currence sur $k$ et \`{a} l'aide la
relation de Pascal, que $\sum\limits_{j=0}^{j=k}\left( -1\right)
^{j}C_{n}^{j}=\left( -1\right) ^{k}C_{n-1}^{k}$, d'o\`{u} \underline{le
nombre minimal de configurations \`{a} tester: $%
s_{n,k}+C_{n-1}^{k}=l_{n,k}+1 $}.
\end{document}