From 22eb7dff95df44c039be489dc37a7d4c90863541 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 12 Apr 2016 15:52:58 +0200
Subject: Finish writing answer to last exercise.

---
 notes-mitro206.tex | 31 ++++++++++++++++++++++++++++++-
 1 file changed, 30 insertions(+), 1 deletion(-)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index eea7e7e..d4fe987 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -6935,7 +6935,36 @@ $n-1$ et/ou de $f_2(n)$, on constate expérimentalement que (A) les
 valeurs $f_2(n)$ pour $n>0$ ont un nombre impair de $1$ dans leur
 écriture binaire, et sont même exactement tous ces nombres rangés par
 ordre croissant, et (B) $f_2(n)$ vaut $2(n-1)$ ou $2(n-1)+1$ selon que
-$n-1$ a un nombre impair ou pair de $1$ dans son écriture binaire.
+$n-1$ a un nombre impair ou pair de $1$ dans son écriture binaire.  Il
+est facile de voir que ces affirmations sont équivalentes : les
+nombres ayant un nombre impair de $1$ dans leur écriture binaire
+s'obtiennent, dans l'ordre, en prenant les écritures binaires des
+entiers (ici $n-1$) et en ajoutant le bit $0$ ou $1$ à la fin
+(c'est-à-dire en calculant $2(n-1)$ ou $2(n-1)+1$) pour que le nombre
+total de bits $1$ soit impair, ce qui donne l'équivalence entre
+(A) et (B).
+
+(Note : certains appellent « odieux » — un jeu de mot sur « odd » en
+anglais — les entiers naturels ayant un nombre impair de $1$ dans leur
+écriture binaire : voir par exemple \url{http://oeis.org/A000069}
+trouvé en entrant les premières valeurs de $f_2(n)$ dans l'OEIS.)
+
+Montrons les affirmations (A) et (B) conjecturées ci-dessus, en
+procédant par récurrence sur $n$, autrement dit, montrons par
+récurrence sur $n>0$ que $f_2(n)$ parcourt dans l'ordre tous les
+nombres, dits « odieux », ayant un nombre impair de $1$ dans leur
+écriture binaire.  On a remarqué ci-dessus que $f_2(n)$ est le plus
+petit entier naturel non nul qui n'est pas ni sous la forme $f_2(n')$
+pour $0<n'<n$ ni sous la forme $f_2(n_1) \oplus f_2(n_2)$ pour
+$0<n_1<n_2<n$.  Pour montrer que $f_2(n)$ est le plus petit nombre
+odieux $m$ strictement supérieur aux $f_2(n')$ pour $n'<n$, il suffit
+donc de montrer que (a) les $f_2(n_1) \oplus f_2(n_2)$ ne sont jamais
+odieux, et (b) ils parcourent au moins tous les nombres non-odieux
+inférieurs à $m$.  Autrement dit, il suffit de montrer que : (a) la
+somme de nim de deux nombres odieux n'est pas odieuse, et que (b) tout
+nombre qui n'est pas odieux est la somme de nim de deux nombres odieux
+plus petits que lui.  Or ces deux affirmations sont claires sur la
+représentation binaire.  Ceci démontre donc la conjecture.
 \end{corrige}
 
 
-- 
cgit v1.2.3