\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc} % encodage du fichier source
\usepackage[T1]{fontenc} % utilisation des polices vectorielles dans le pdf (copier-coller)
\usepackage{lmodern} %plus joli 
%\usepackage[urw-garamond]{mathdesign}
%\usepackage{pifont} %ciseau, telephone ...
%\usepackage{multirow}% pour grouper des lignes dans un tableaux
%\usepackage{eurosym} %pour \euro

% --- graphiques pstricks et images 
\usepackage{pst-all,pst-3dplot,pst-eucl}
\usepackage{graphicx}

% ===== doubler l'interligne ======
\usepackage{setspace}          
%	\doublespacing 
\onehalfspacing						

% --- mise en page
\usepackage{geometry}  
\setlength{\headsep}{10pt}
\setlength{\parindent}{0pt} % pas d'intentation des paragraphes
%\usepackage{lscape} permet d'utiliser \begin{landscape}... : pour une seule page en paysage


% --- pour les guillemets francais \og \fg ... http://daniel.flipo.free.fr/frenchb/frenchb2-doc.pdf
\usepackage[frenchb]{babel}
\frenchbsetup{CompactItemize=false,ReduceListSpacing=false}
%\renewcommand{\labelitemi}{\textbullet} % a placer apres \begin{document}


% --- pour les formules
\usepackage{amsmath} % symboles mathematiques et outils (exemple \text)
\usepackage{amssymb} % autres symboles, par exemple \geqslant
\usepackage{dsfont,mathrsfs} %pour les ensembles \N etc et les  cursives
\usepackage{stmaryrd} % \llbracket, \rrbracket et \sslash (parallele)
\newcommand{\R}{\mathds{R}}
\newcommand{\N}{\mathds{N}}
\newcommand{\Z}{\mathds{Z}}
\newcommand{\T}{\textrm}
\newcommand{\e}{\T{e}}
\renewcommand{\S}{\mathscr}
\newcommand{\V}[1]{\overrightarrow{ \T{#1} } }
%\renewcommand{\i}{\,\T i} vient trop tot voir la fin 
\everymath{\displaystyle} % sinon formules rabougries
\usepackage{cancel} % pour la commande \cancel{} qui barre en mode maths 

% --- en-tete et pied de page
\usepackage{lastpage} % pour compter le nombre de pages, 2 compilations necessaires
\usepackage{fancyhdr} % gestion de l'en-tete et pied de page


% --- pour le titre de la fenetre de l'afficheur pdf
\usepackage[dvips,ps2pdf,colorlinks=true]{hyperref}
%\usepackage[a4paper=true,ps2pdf=true,pagebackref=true]{hyperref}
\hypersetup{ % Modifiez la valeur des champs suivants
%    pdfauthor   = {Fran\c{c}ois Couloigner},%
    pdftitle    = {}
}
\renewcommand{\i}{\,\T{i}} % a placer apres hyperref

% --- numerotation des sections
%\renewcommand{\thesection}{\Roman{section}} 
% --- numerotation des enumeration
%\renewcommand{\theenumi}{\textbf{\arabic{enumi}}}
%\renewcommand{\theenumi}{\textbf{\Roman{enumi}}}
%\renewcommand{\theenumi}{\textbf{\alph{enumi}}}
%\renewcommand{\labelenumi}{\textbf{\theenumi.}}
%\renewcommand{\theenumi}{\textbf{\Alph{enumi}}}
%\renewcommand{\theenumii}{\textbf{\arabic{enumii}}}
%\renewcommand{\labelenumii}{\textbf{\theenumii.}}
%\renewcommand{\theenumiii}{\textbf{\alph{enumiii}}}
%\renewcommand{\labelenumiii}{\textbf{\theenumiii.}}

%-----Document de plusieurs colonnes
\usepackage{multicol}
%\setlength{\columnsep}{3em}
%\setlength{\columnseprule}{1pt}

%\usepackage{tabvar}
%\usepackage{variations}

%-----Pas de numerotation
%\pagestyle{empty}
%\thispagestyle{empty}

%\usepackage{tabularx}

% exemple de nouvelle commande : \exercice{} avec titre et numerotation automatique
\newcounter{numeroexo}
\newcommand{\exercice}[1]{\vspace{1cm} \par\noindent\refstepcounter{numeroexo}
	\textbf{\begin{large}Exercice \thenumeroexo\end{large} \hspace{0.4cm} #1}\quad}

\geometry{margin=1.5cm} %dvips,landscape,margin=,top=,left=,bottom=,right=
\pagestyle{fancy}
%\lhead{}%tapez un titre
%\lfoot{\}
\cfoot{}
\rhead{\thepage/\pageref*{LastPage}}
\renewcommand \headrulewidth{0pt}%
\begin{document}\label{document}
\renewcommand{\labelitemi}{\textbullet} % a placer apres \begin{document}
cg2018 : pb 3\bigskip

\textbf{Partie A : les entiers naturels sont en or}\bigskip

\begin{enumerate}
\item Les séquences 100 et 011 sont équivalentes car

$\forall k \in \Z$ , $ \varphi^{k+2}+0\,\varphi^{k+1}+0\,\varphi^k=\varphi^k(\varphi^2)=\varphi^k(\varphi+1)= 0\,\varphi^{k+2}+1\,\varphi^{k+1}+1\,\varphi^k$
\item La propriété est vraie pour $n=0$ ou $1$ (pas de répétition du 1). Ensuite\dots

\begin{itemize}
\item $011\triangleright 100$
\item $0111\triangleright 1001$
\item $01111\triangleright 10011 \triangleright  10100$
\item $011111\triangleright 101001$
\item $0111111\triangleright 1010011 \triangleright 1010100$
\end{itemize}
les transformations successives $011111\dots 1\triangleright 100111\dots 1\triangleright 101001\dots 1$ ne modifient pas le nombre de chiffres et aboutissent à 
\begin{itemize}
\item $\overset{n'\T{ répétitions de }10 }{\overbrace{101010\dots1010}}0$ si $n=2n'$ est pair, 
\item $\overset{n'\T{ répétitions de }10 }{\overbrace{101010\dots1010}}01$ si $n=2n'+1$ est impair.
\end{itemize}
\item \begin{itemize}
\item De $\varphi^2=\varphi+1$ on déduit $1=\varphi^{-1}+\varphi^{-2}$ cad $1\triangleright 0,11$ et donc $2\triangleright 1,11$
\item  $2\triangleright 1,11\triangleright 01,11\triangleright 10,01$ donc $3 \triangleright 11,01$
\end{itemize}
\item Je démontre que si \boldmath $x$ est en or, alors $x+1$ aussi
\begin{itemize}
\item $x$ \unboldmath \textbf{a une écriture en or sans répétition de 1}

En effet, à toute répétition de $1$ dans l'écriture de $x$ on peut substituer l'écriture décrite dans 2.

Dans cette première réécriture, toute terminaison en $001$ peut être suivie d'un 1 mais dans ce cas 0011 sera réécrit 0100
\item $1\triangleright 0,11\triangleright 0,1011\triangleright 0,101011\triangleright 0,10101011 \triangleright \dots$ 

\begin{itemize}
\item Si, dans l'écriture sans répétition de 1 de $x$, il y a un 0 devant la virgule, le remplacer par 1 revient à ajouter 1 à $x$
\item sinon cette écriture est de la forme $\dots1,010101\overset{\T{première paire de 0  après la virgule}}{1010101\dots\dots\overbrace{00}\dots\dots~~~~~~}$ : on peut lui ajouter une écriture de 1  
\end{itemize}
\end{itemize}
\end{enumerate}

\textbf{Partie B : représentation en or pur}\bigskip

\begin{enumerate}
\item $2\triangleright 10,01$ , $3\triangleright 100,01$ , $4\triangleright 101,01$ et $5\triangleright 101,1111\triangleright 110,0111\triangleright 1000,1001$
 \item \begin{enumerate}
 \item  $\varphi >1$ donc $\varphi^k$ croît avec $k$ sur $\Z$.
 
 Soit une représentation en or pur de teneur $n$ d'un nombre $x$ et $p$ le nombre de 1 dans cette représentation :
 
$x = \varphi^n +\varphi^{n_1}+\varphi^{n_2}+\varphi^{n_3}+\dots+\varphi^{n_{p-1}}$ où les exposants sont des entiers diminuant avec un pas $<-2$.\medskip

D'une part $x \geqslant \varphi^n$, d'autre part\dots

$x \leqslant \varphi^n +\varphi^{n-2}+\varphi^{n-4}+\varphi^{n-6}+\dots+\varphi^{n-2(p-1)}=\varphi^n\,\frac{1-\varphi^{-2p}}{1-\varphi^{-2}} < \varphi^n\,\frac{1}{1-\varphi^{-2}}
=\frac{\varphi^n}{\varphi^{-1}}=\varphi^{n+1}$
\item La teneur de $x$ est l'unique $n$ vérifiant $\varphi^n \leqslant x < \varphi^{n+1}$, je la note $t(x)$

Dans la représentation en or pur $x = \varphi^n +\varphi^{n_1}+\varphi^{n_2}+\varphi^{n_3}+\dots+\varphi^{n_{p-1}}$ on a :

$n=t(x)$ , $n_1= t\left(x-\varphi^n\right)$ , $n_2= t\left(x-\varphi^n-\varphi^{n_1}\right)$ \dots

Cette liste est donc unique 
 \end{enumerate}

\item 
\begin{enumerate}
\item $\varphi^n \leqslant x < \varphi^{n+1} \Longrightarrow n\,\ln \varphi \leqslant \ln x < (n+1)\ln \varphi \Longrightarrow  n \leqslant \frac{\ln x}{\,\ln \varphi} < n+1
 \Longrightarrow n= E\left(\frac{\ln x}{\,\ln \varphi}\right)$
\item On peut par exemple consigner les positions des 1 dans une liste \texttt{L} :

%\begin{multicols}{2}}
\begin{ttfamily}
\begin{tabular}[t]{|l|}
\hline
phi = (1+racine(5))/2\\
L est une liste vide\\
tant que x>0 :\\
\hspace{1cm}n = E( ln(x) / ln(phi) )\\
\hspace{1cm}ajouter n à la liste L \\
\hspace{1cm}x = x -phi\textasciicircum n\\
fin de tant que\\
\hline
\end{tabular}
\end{ttfamily}\bigskip
\item 
Avec une casio graph 35 : ~ 
\begin{ttfamily}
\begin{tabular}[t]{|l}
(1+$\sqrt{\;}$\,5) $\div$ 2\\
? $\rightarrow$ X\\
While X>0 \\
Intg(  ln(X) $\div$ ln(P) )$\rightarrow$ N \pspolygon[fillstyle=solid,fillcolor=black](0,0)(0.2,0)(0.2,0.2)\\
X $-$ P\textasciicircum N\\
WhileEnd\\
\end{tabular}
\end{ttfamily}
\bigskip

Cà marche mal, la partie entière est très sensible aux erreurs d'arrondis. 

Après quelques essais, en remplaçant \texttt{Intg(ln(X)$\div$ ln(P))} par  \texttt{Intg(ln(X)$\div$ ln(P) + 10\textasciicircum(-6))} on obtient la liste $15,13,10,4,2,-2,-4,-11,-16$
\end{enumerate}
\item Déjà utilisé dans la partie A
\item On peut chercher des situations où l'algorithme précédent est sans fin, 

par exemple $x\in ]1\, ,\varphi[$ tel que  
$x-1=\frac{x}{\varphi^{n}} \iff x=\frac{1}{1-\varphi^{-n}}$

$\frac{1}{1-\varphi^{-n}}<\varphi \iff 1-\varphi^{-n}>\varphi^{-1} \iff \varphi^{-n}<1-\varphi^{-1}=\varphi^{-2} \iff n >2$

Le plus simple est de choisir $n=3$ auquel cas $x=\frac{1}{1-\varphi^{-3}}=\dots=\frac{\varphi^2}{2}\triangleright 1,001001001001001\dots$
\end{enumerate} 

\end{document}



