Accéder à mon compte > Accéder à ma feuille d'exercices >

Oraux de concours : Arithmétique

Centrale MP

Exercice 1 - Coefficients binomiaux pairs (d'après Oral Centrale MP) ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

Enoncé

Pour $n \in \mathbb{N}^*$ dont l'écriture en binaire est donnée par \[ n = \sum_{k=0}^{p} e_k 2^k \] on pose $s(n) = e_0 + \dots + e_p$ et $v(n) = \min \{k \in \{0, \dots, p\} \mid e_k \neq 0\}$.

Écrire des fonctions $\verb+s(n)+$ et $\verb+v(n)+$ qui renvoient respectivement $s(n)$ et $v(n)$.
Montrer que $v(mn) = v(m) + v(n)$ pour tous $m, n \in \mathbb{N}^*$.
Démontrer la relation $v(n) = s(n - 1) - s(n) + 1$ pour $n\geq 2$.
Calculer $v(k!)$ pour $k \in \mathbb{N}^*$.
Montrer l'équivalence entre les assertions suivantes :
1. $n$ est une puissance de $2$ ;
2. pour tout $k \in \{1, \dots, n - 1\}$, le coefficient binomial $\dbinom{n}{k}$ est pair.

Indication

Corrigé

Voici deux fonctions :

def s(n):
    a=0
    while (n>0):
        a+=(n%2)
        n=n//2
    return a

def v(n):
    k=0
    while (n%2==0):
        k=k+1
        n=n//2
    return k

Il faut d'abord comprendre ce que signifie $v(n)$ : on peut écrire $$n=2^{v(n)}+\sum_{k=v(n)+1}^p e_k 2^k.$$ Ceci signifie que $2^{v(n)}$ divise $n$, mais $2^{v(n)+1}$ ne divise pas $n.$ Ainsi, $v(n)$ est la valuation $2$-adique de $n$, c'est-à-dire le terme qui apparait en exposant de $2$ dans la décomposition en facteurs premiers de $n$. On peut donc écrire $n=2^{v(n)}n'$ ou $n'\wedge 2=1$ et $m=2^{v(m)}m'$ où $m'\wedge 2=1.$ En effectuant le produit, on obtient $$nm=2^{v(n)+v(m)}(n'm')$$ et on a $(n'm')\wedge 2=1.$ Ainsi, on a bien prouvé que $v(nm)=v(n)+v(m).$
Il s'agit d'étudier comment déduire l'écrire en base $2$ de $n$ à partir de celle de $n-1.$ Il faut étudier essentiellement où apparaît la retenue. Pour cela, on écrit $$n-1=\overline{a_p\cdots a_q01\dots1}.$$ On a alors $$n=\overline{a_p\cdots a_q10\dots0}$$ et donc le premier chiffre $1$ (en partant de la droite) est en position $v(n)+1$ ($v(n)$ vaut le nombre de zéros consécutifs à droite dans l'écriture de $n$). On en déduit que $$s(n-1)=a_p+\cdots+a_q+v(n)$$ et $$s(n)=a_p+\cdots+a_q+1$$ d'où l'on tire $$s(n-1)-s(n)=v(n)-1.$$
La question "calculer $v(k!)$" semble mal posée, puisqu'on va simplement exprimer $v(k!)$ en fonction de $s(k)$, et qu'il est difficile d'aller plus loin. D'après la question 2., on a $$v(k!)=\sum_{j=1}^k v(j)=v(1)+\sum_{j=2}^k v(j).$$ Il est clair que $v(1)=0$ et pour le reste, on applique la relation trouvée à la question précédente, puis on reconnait une somme télescopique : \begin{eqnarray*} v(k!)&=&0+\sum_{j=2}^k \big(s(j-1)-s(j)+1\big)\\ &=&(k-1)+s(1)-s(k)\\ &=&k-s(k). \end{eqnarray*}
Écrivons, pour $k=1,\dots,n-1,$ $$\binom nk=\frac{n!}{k!(n-k)!}.$$ Ceci est pair si et seulement si l'exposant $2$-adique du numérateur est strictement plus grand que l'exposant $2$-adique du dénominateur, donc si et seulement si $$v(n!)>v(k!)+v((n-k)!).$$ En utilisant le résultat de la question précédente, on doit donc déterminer les entiers $n\geq 2$ tels que, pour tout $k\in\{1,\dots,n-1\},$ $$s(n)<s(k)+s(n-k).$$ D'une part, si $n$ est une puissance de $2,$ alors $s(n)=1$ et comme $s(k),s(n-k)\geq 1,$ la relation est bien vérifiée pour tout $k\in\{1,\dots,n-1\}.$
Réciproquement, si $n$ n'est pas une puissance de $2,$ alors son écriture en base $2$ admet au moins deux chiffres $1$ et on peut écrire $n$ sous la forme $$n=\overline{a_p\dots a_q10\dots0}.$$ Posons alors $$k=\overline{10\dots0}$$ avec le même nombre de zéros à droite que $n,$ de sorte que l'on a bien $1\leq k\leq n-1$ et $$n-k=\overline{a_p\dots a_q00\dots0}.$$ On a donc $$s(n)=a_p+\cdots+a_q+1,\ s(k)=1,\ s(n-k)=a_p+\cdots+a_q$$ d'où $s(n)=s(k)+s(n-k).$ La relation $s(n)<s(k)+s(n-k)$ n'est pas vérifiée, et le coefficient binomial $\binom nk$ n'est pas pair.

Arithmétique

Cours

Méthodes