diff options
| -rw-r--r-- | notes-mitro206.tex | 31 |
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} |