\documentclass[documents]{monexamen}
%\documentclass[documents]{monexamen}
%\setlength{\parindent}{0pt}

\usepackage{graphicx}
\usepackage{a4wide,amssymb,frenchle}
\usepackage[latin1]{inputenc} %% entr\'ee 8 bits iso-latin1
\usepackage[T1]{fontenc}      %% encodage 8 bits des fontes utilis\'ees

\newcommand{\f}{\ensuremath{\uparrow}}


\newcommand{\f}{\ensuremath{\uparrow}}


\begin{document}

\entete{Polytech' Nice Sophia}
{ }{05}{06}{Math\'{e}matiques  Discr\`{e}tes\\ du 12 Octobre 2005}{Dur\'{e}e : 60  minutes}% \
%{Probabilit\'{e}s}{02}{03}{du 1er Avril  2003 }
\\
\addtolength{\evensidemargin}{-1cm}
\addtolength{\oddsidemargin}{-1cm}
\reversemarginpar{ 

\begin{tabular}{l|l}
1 &  \ \  \\\hline
2 &   \\\hline
3 &   \\\hline
4 &   \\\hline
5 &   \\\hline
6 &   \\\hline
7 &   \\

\end{tabular}
}
\\

Toutes vos r\'{e}ponses doivent \^{e}tre justifi\'{e}es par une d\'{e}monstration ou un contre-exemple.

Aucun document autorisé

\section {R\'{e}currence simple}
Montrer par récurrence que 
la somme des $n-1$ premiers entiers multiples de trois et impairs est egal à$n^3$
\begin{copie}
  \lignes{14}
\end{copie}


\section {Plus petit élément}

\begin{copie}
  \lignes{20}
\end{copie}

\section { Ordre bien fondé}
Une relation d'ordre est telle que pour tout élément $x$, il existe un nombre fini d'éléments inférieurs à $x$, cette relation est elle bien fondée

\begin{copie}
  \lignes{12}
\end{copie}


\section {Ordre ?}
Donner la définition d'une relation d'ordre et donner un exemple de relation d'ordre (différent de ceux vus en cours/TD).

\begin{copie}
  \lignes{17}
\end{copie}

\section {Ordre strict?}
Sur l'ensemble des cyclistes professionnels, on considère la relation {\em est meilleur que} définie par {$x$ est meilleur que $y$} si $x$ est arrivé devant $y$ à toutes les courses de l'UCI pro-tour où l'un et l'autre ont couru, autrement dit dès que $x$ et $y$ courent ensemble $x$ arrive devant $y$.\\ Il n'y a aucun ex eaquo dans le système de classement UCI.
Est-ce une relation d'ordre  strict ? \\
Même question si l'on suppose en outre que tous les coureurs participent à toutes les courses.

\begin{copie}
  \lignes{30}
\end{copie}




\section {Ordre d'ainesse}
On considère $E$ l'ensemble des SI1 et des MAM1.Soient $a$ et $b$ deux éléments de $E$, on dit que $a R b$ si et seulement si $a$  n'est pas né plus tard que  $b$.  La relation $R$ est elle un ordre ? Pour chacune des propriétés d'une relation d'ordre dire si $R$ vérifie la propriété. Si $R$ est une relation d'ordre est ce un ordre total ou partiel ? 


\begin{copie}
  \lignes{30}
\end{copie}

\section {Calculateur prodige (d'après un problème du journal {\em Le Monde}}
Un magicien demande à un spectateur de choisir 2 nombres, et de les écrire sur une feuille l'un en dessous de l'autre, puis d'en faire la somme et de l'écrire en dessous du dernier nombre écrit, puis de faire la somme du nombre obtenu et du nombre précédent et de l'écrire en dessous du dernier nombre écrit, puis de recommencer autant de fois qu'il veut. Le magicien lui demande ensuite le {\bf deuxième} nombre choisi ainsi que les 2 derniers nombres qu'il a écrit, et après invocation d'une formule magique (!), lui donne la somme de tous les nombres que le spectateur a écrit. Quelle est la formule magique du magicien ?

En notant $f_n$ le $n^{ieme}$ nombre écrit par le spectateur, on a pour entier $n$, la relation $f_{n+2} = f_{n+1} + f_n$ (suites dites de Fibonacci). Il s'agit donc de trouver un formule pour calculer la somme des termes d'une suite de Fibonacci, $S_n = \sum _{i=1}^{n} f_i$. En sommant les égalités $f_{i+2} = f_{i+1} + f_i$, pour tous les $i$ variant de $1$ à $n$, on trouve après simplications que $f_{n+2} = f_{2} + S_n$, soit $S_n = f_{n+2} - f_{2}$. Cette égalité peut être trouvée ou devinée par tout autre moyen (par exemple, en regardant ce qui se passe pour quelques termes), puis démontrée facilement par récurrence.

Si on revient au magicien, il cherche à calculer $S_n$, pour cela il demande $f_{n}$ et $f_{n-1}$ qui lui permettent de calculer $f_{n+2} = f_{n+1} + f_n = 2f_n + f_{n-1}$, auquel il soustrait le deuxième nombre écrit $f_2$ (et non le premier comme indiqué par erreur dans l'énoncé original).




\end{document}