\documentclass[11pt]{article} \usepackage{fullpage,french,epsf,fancyheadings} \pagestyle{fancy} \lhead{Partitions d'entiers} \rhead{Jean-Christophe Filliâtre} \newcommand{\Caml}{Caml Light} \newtheorem{defi}{Définition} \reversemarginpar \newcommand{\question}{\marginpar{\hfill$\Box$}} \begin{document} \begin{center} {\Large\bf Devoir surveillé} \\[1em] {\huge\bf Partitions d'entiers} \\[0.5em] {\normalsize\em d'après un sujet de l'E.N.S.} \\[1em] {\normalsize 10 décembre 1996 -- 2 heures} \end{center} \noindent Une partition d'un entier positif $n$ est une suite $a = (n_1,\ldots,n_s)$ d'entiers tels que $n_1 \ge \ldots \ge n_s > 0$ et $n_1 + \cdots + n_s = n$. Chaque $n_i$ ($1 \le i \le s$) est une {\em part} de $a$, et $s$ est le {\em nombre de parts} de la partition. \smallskip\noindent Les partitions d'un entier $n$ sont ordonnées comme suit : si $a = (n_1,\ldots,n_s)$ et $a' = (n'_1,\ldots,n'_{s'})$ sont deux partitions de $n$, on pose $a < a'$ si et seulement s'il existe un entier $i \le s,s'$ tel que $n_j = n'_j$ pour $j = 1\ldots i-1$ et $n_i < n'_i$ (ordre lexicographique). \section{Questions préliminaires} \noindent Ecrire \question une fonction {\tt affiche\_list : int liste ->~unit} qui affiche une liste d'entiers, séparés deux à deux par un espace, et suivie d'un retour à la ligne, {\em en respectant l'ordre des éléments dans la liste}. \medskip\noindent Ecrire \question une fonction {\tt affiche\_rev : int list ->~unit} affichant les éléments d'une liste d'entiers de la même manière, {\em mais dans l'ordre inverse}. La liste ne sera parcourue qu'une seule fois (et donc en particulier on n'utilisera pas la fonction précédente combinée avec la fonction \verb!rev! !). \section{Enumérations des partitions} \noindent Ecrire \question une fonction {\tt partitions\_m : int ->~int ->~unit} qui prend en argument deux entiers positifs $n$ et $m$ et qui affiche en ordre décroissant toutes les partitions de $n$ dont toutes les parts sont inférieures ou égales à $m$ (on pourra supposer $n \le 20$). \medskip\noindent Exemple \question numérique : $n = 9, m = 4$. \medskip\noindent Ecrire \question une fonction {\tt partitions : int ->~unit} qui prend en argument un entiers positif $n$ et qui affiche en ordre décroissant toutes les partitions de $n$. \medskip\noindent Exemple \question numérique : $n = 6$. \paragraph{Dénombrement.} On note $p(n)$ le nombre de partitions de $n > 0$ et on pose $p(0) = 1$. Pour $m > 0$ et $n > 0$, on note $p_m(n)$ le nombre de partitions de $n$ en parts inférieures ou égales à $m$, et on pose $p_m(0) = 1$. \medskip\noindent Démontrer \question que $$ p_m(n) = \left\{ \begin{array}{l@{\mbox{~~~si~}}l} p_{m-1}(n) & m > n \\ p_{m-1}(n) + p_m(n-m) & n \ge m > 1 \end{array} \right. $$ \medskip\noindent Ecrire \question une fonction {\tt p\_n : int ->~int} qui prend en argument $n$ et qui calcule $p(n)$. \medskip\noindent Exemple \question numérique : $n = 60$. \medskip\noindent Démontrer \question que $p_m(n)$ est égal au nombre de partitions de $n$ en au plus $m$ parts. \subsection*{Enumérations particulières} \noindent Ecrire \question une fonction {\tt parts\_distinctes : int ->~unit} qui affiche en ordre décroissant toutes les partitions de $n$ en parts distinctes. \medskip\noindent Exemple \question numérique : $n = 11$. \medskip\noindent Ecrire \question une fonction {\tt parts\_distinctes\_impaires : int ->~unit} qui affiche en ordre décroissant toutes les partitions de $n$ en parts distinctes et toutes impaires. \medskip\noindent Exemple \question numérique : $n = 30$. \section{Application : comment rendre la monnaie} \noindent On considère un appareil qui doit rendre la monnaie. Supposons, pour fixer les idées, que cet appareil contient des pièces de 10, 5, 2 et 1 francs. Si on considère dans un premier temps que cet appareil possède une infinité de pièces de chaque sorte, alors rendre une monnaie de $n$ francs, c'est trouver une partition de $n$ dont les parts sont dans l'ensemble $\{ 10, 5, 2, 1 \}$. \medskip\noindent Ecrire \question une fonction {\tt parts\_dans\_l : int ->~int liste ->~unit} qui affiche en ordre décroissant toutes les partitions de $n$ dont les parts appartiennent à une liste $l$ donnée en argument. On supposera que la liste $l$ est triée par ordre décroissant. {\bf Attention :} on écrira une solution qui ne teste que des parts appartenant à la liste $l$. \medskip\noindent Exemple \question numérique : donner toutes les fa\c cons de rendre 11 francs avec l'appareil ci-dessus. \medskip\noindent On ne suppose plus que l'appareil possède une infinité de pièces de chaque sorte mais au contraire que ces pièces sont des ressources épuisables. Pour cela, si les pièces de valeur $v$ disponibles sont en nombre $r_v$, alors une telle ressource est représentée par le couple $(v,r_v)$ et la totalité des ressources de l'appareil est représentée par la liste de ces tels couples. Ainsi, si on dispose de 2 pièces de 10 francs, 3 de 5 francs, 1 de 2 francs et 3 de 1 franc, alors ces ressources sont représentées par la liste \begin{center} {\tt [ (10,2) ; (5,3) ; (2,1) ; (1,3) ]} \end{center} \medskip\noindent Ecrire \question une fonction {\tt monnaie : int ->~(int*int) liste ->~unit} qui affiche en ordre décroissant toutes les fa\c cons de rendre $n$ francs en disposant des ressources représentée par une liste $l$ donnée en argument. On supposera que la liste $l$ est triée par ordre décroissant des premières projections de ses éléments. \medskip\noindent Exemple \question numérique : donner toutes les fa\c cons de rendre 17 francs avec 2 pièces de 10 francs, 3 de 5 francs, 1 de 2 francs et 3 de 1 franc. \end{document}