summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-04-12 13:52:58 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-04-12 13:52:58 (GMT)
commit22eb7dff95df44c039be489dc37a7d4c90863541 (patch)
tree3a2f1f545185da62751e07d5f784f5eba6390ebe
parente1a506c2b7868936f22782b64b3ab08d295e885a (diff)
downloadmitro206-22eb7dff95df44c039be489dc37a7d4c90863541.zip
mitro206-22eb7dff95df44c039be489dc37a7d4c90863541.tar.gz
mitro206-22eb7dff95df44c039be489dc37a7d4c90863541.tar.bz2
Finish writing answer to last exercise.
-rw-r--r--notes-mitro206.tex31
1 files changed, 30 insertions, 1 deletions
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}