\documentclass[11pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}
\usepackage{pst-all}
\usepackage[a4paper]{geometry}

\input{symboles.sty}
\geometry{hmargin=1cm, tmargin=-0.5cm, bmargin=1.5cm}

\title{
DUT d'informatique. Partiel de mathématiques discrètes.\\  
Semestre 1 (Décembre 2013). Durée 1h30.}

\date{}

\begin{document}
\maketitle

\vspace{-3em}
\noindent Seule une fiche manuscrite de format A5 est autorisée.
Tous les moyens de communications sont interdits. 
Tous les exercices de ce sujet sont indépendants les uns des autres. 
Dans tout ce qui suit, on considère une algèbre de Boole
munie des opérateurs classiques ``+'', ``.'', 
``$\overline{\begin{array}{l}~\end{array}}$'' et des variables booléennes 
$a$, $b$, $c$, $d$.


\vspace{-1em}
\section{( pts) Algèbre de Boole }
On cherche à  analyser les codes binaires sur 4 bits. 


\begin{enumerate}
\item Dans cette question, un code est correct s'il contient au
plus deux 1 consécutifs. Par exemple $1010$ est dit correct  
(il ne contient pas de 1 consécutifs) tandis 
$0111$ ne l'est pas  (il contient trois 1 consécutifs).
Le but de cette question est de concevoir la fonction $F$  qui renvoie 1 
si le code de 4 bits $abcd$ est correct et 0 sinon.
\begin{enumerate}
\item Écrire la table de vérité de cet analyseur dans une table de Karnaugh.
\item Donner l'expression la plus simplifiée de la fonction $F$.
\end{enumerate}

\begin{enumerate}
\item Dans cette question, un code est correct 
s'il ne contient pas de 0 consécutifs (par exemple $1011$).
Le but de cette question est de concevoir la fonction $G$  qui renvoie 1 
si le code de 4 bits $abcd$ est correct et 0 sinon.
\begin{enumerate}
\item Écrire la table de vérité de cet analyseur dans une table de Karnaugh.
\item Donner l'expression la plus simplifiée de la fonction $G$.
\end{enumerate}
\item Dans cette question,  code est correct 
s'il vérifie les deux contraintes précédentes.
Le but de cette question est de concevoir la fonction $H$  qui renvoie 1 
si le code de 4 bits $abcd$ est correct et 0 sinon.
\begin{enumerate}
\item Sans utiliser de table de Karnaugh, résoudre algébrique de ce 
problème.
\item Exprimer $H$ sous la forme d'une somme de trois monômes.
\item Comment pourrait-on vérifier le résultat sur les tables de Karnaugh
remplies aux deux premières questions.  
\end{enumerate} 
\end{enumerate}

\vspace{-1em}
\section{( pts) Relations binaires entre ensembles}


\begin{enumerate}
\item 
Soit $P^*$ l'ensemble des nombres premiers supérieurs à 2. On considère 
la relation $\mathcal{R}$ entre deux éléments de $P^*$ définie par:
$$
p \mathcal{R} q \textrm{ si et seulement si }
\dfrac{p+q}{2} \textrm{ appartient à $P^*$.}
$$
Montrer qu'elle n'est pas transitive.

\item On considère 
la relation $\mathcal{S}$ entre deux éléments de $\mathcal{Z}$ définie par:
$$
m \mathcal{S} n \textrm{ si et seulement si }
m^2 + m = n^2 + n.
$$
\begin{enumerate}
\item Montrer que c'est une relation d'équivalence.
\item Construire la classe de 0, nommée $\dot{0}$.
\item Pour tout entier relatif $m$, construire la classe de $m$, 
  nommée $\dot{m}$.
\end{enumerate}
\end{enumerate}

\vspace{-1em}
\section{( pts) Démonstration par récurrence}
On considère la suite $(U_n)_{n \in \N}$ définie pour 
tout $n \in \N$ par $U_n = 10^n.(9n-1)+1$.
\begin{enumerate}
\item Calculer $U_0$, $U_1$ et $U_2$.
\item Montrer que pour tout $n \in \N$ par 
$U_{n+1} = U_n + 9^2.10^n.(n+1)$.
\item Montrer que $U_n$ est divisible par 81 pour tout $n \in \N$.
\end{enumerate}
\end{enumerate}

\vspace{-1em}
\section{( pts) Plus Grand Commun Diviseur}
Dans ce qui suit, $n$ est un entier naturel strictement positif.
On considère trois suites 
$(U_n)_{n \in \N^*}$, $(U_n)_{n \in \N^*}$ et $(U_n)_{n \in \N^*}$
définies par
$A_n = n^2 - 2n +2$, 
$B_n = n² +2n +2$ 
 et 
$d_n= A_n \land B_n$. 

\begin{enumerate}
\item Calculer $A_1$, $A_2$, $A_3$, $A_4$,  $B_1$, $B_2$, $B_3$, $B_4$,  $d_1$, $d_2$, $d_3$ et  $d_4$. Quelles intuitions avez vous à propos de $d_n$?  
\item Montrer que si un entier naturel  
  $d$ divise  à la fois $A_n$ et $n$, alors $d$ divise 2. 
\item Montrer que si un entier naturel  
  $d$ divise  à la fois $A_n$ et $B_n$, alors $d$ divise $4n$. 
\item  Dans cette question on suppose que $n$ est impair. 
\begin{enumerate}
\item  Montrer que $A_n$ et $B_n$ sont impairs. 
  En déduire que $d_n$ est impair. 
\item Montrer que $d_n$ divise $n$. 
\item En utilisant la question 1, en déduire que $d_n$ divise 2,
  puis que $A_n$ et $B_n$ sont premiers entre eux. 
\end{enumerate}
\item  On suppose maintenant que $n$ est pair. 
\begin{enumerate}
\item Montrer que $d_n$ est pair.
\item Montrer que 4 ne divise pas $A_n$. En déduire la même chose pour  $B_n$
\item Montrer que $d_n$ peut s'écrire sous la forme $d_n = 2.p$, 
  où $p$ est impair. 
\item En utilisant entre autre la question 2., en déduire 
  que $p$ divise $n$. 
\item En utilisant entre autre la question 1., en déduire que $d_n=2$. 
\end{enumerate}
\end{enumerate}



\vspace{-1em}
\section{( pts) Nombres (premiers ou pas) de Fermat}
Pour $p \in \N$, les nombres de Fermat sont ceux de la forme 
$F_p = 2^{2^p}+1$.


\begin{enumerate}
\item Question préliminaire: montrer que les deux égalités suivantes sont établies:
\begin{enumerate}
\item $x^n- 1 = (x-1)(x^{n-1}+x^{n-2}+\ldots+ x + 1)$  pour tout entier naturel $n$ strictement positif.
\end{enumerate}

\item 
Montrer que si $n$ n'est pas une puissance de 2, alors
$2^n+1$ n'est pas un nombre premier. 
On pourra se servir de l'égalité
$$
x^n+ 1 = (x+1)(x^{n-1}-x^{n-2}+\ldots - x + 1)
$$  qui est établie 
pour tout entier naturel $n$ impair.

\item Le calcul de $F_5$ donne $F_5 = 4294967297 = 6700417\times641$. Que dire de $F_5$? Est-ce contradictoire avec la question précédente?

\item Montrer que, $F_{n+1} = (F_n - 1)^2 +1$.

\item Montrer que $F_{n+1} - 2$ est divisible par $F_{n}$.

\item Montrer $F_{n+1}$ et $F_{n}$ sont premiers entre eux.

\end{enumerate}



\end{document}