Shortlist 2013, N7¶

Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : U.S.A.

Concepts : Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · Partie entière et majorations · Récurrence et constructions récursives · Bijections et dénombrement

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 65 (page 65 du PDF)

Figures reprises du livret officiel de la Shortlist.

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé¶

Let $\nu$ be an irrational positive number, and let $m$ be a positive integer. A pair $(a, b)$ of positive integers is called good if

\[a \lceil b\nu \rceil - b \lfloor a\nu \rfloor = m. \tag{$\ast$}\]

A good pair $(a, b)$ is called excellent if neither of the pairs $(a - b, b)$ and $(a, b - a)$ is good. (As usual, by $\lfloor x \rfloor$ and $\lceil x \rceil$ we denote the integer numbers such that $x - 1 < \lfloor x \rfloor \leq x$ and $x \leq \lceil x \rceil < x + 1$.)

Prove that the number of excellent pairs is equal to the sum of the positive divisors of $m$.

Indices : les idées clés

Partie entière : avec $f(a, b) = a\lceil b\nu \rceil - b\lfloor a\nu \rfloor$, l'un des « enfants » $(a + b, b)$, $(a, b + a)$ garde la valeur $f(a, b)$ et l'autre l'augmente de $b$ ou de $a$, selon que $\{a\nu\} + \{b\nu\} < 1$ ou non.
Arbre des paires : chaque paire $(a, b)$ avec $a \neq b$ a un unique ancêtre de la forme $(x, x)$ ; on montre par récurrence que le nombre de descendants $m$-excellents de $(a, b)$ est le nombre d'écritures $m - f(a, b) = ka + \ell b$ avec $k, \ell \geq 0$ (bijection).
Somme des diviseurs : depuis $(x, x)$, il y a $\frac{m}{x}$ telles écritures si $x \mid m$, et $0$ sinon ; avec la paire $(m, m)$, le total vaut $\sigma(m)$.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2013 (une solution et une remarque).

Solution¶

Pour des entiers $a, b \geq 1$, posons

\[f(a, b) = a \lceil b\nu \rceil - b \lfloor a\nu \rfloor.\]

Comme on va considérer plusieurs valeurs de $m$, on dira qu'une paire $(a, b)$ est $m$-bonne ou $m$-excellente si les conditions correspondantes sont vérifiées.

Étudions d'abord le lien entre $f(a + b, b)$, $f(a, b + a)$ et $f(a, b)$. Si $\{a\nu\} + \{b\nu\} < 1$, alors $\lfloor (a + b)\nu \rfloor = \lfloor a\nu \rfloor + \lfloor b\nu \rfloor$ et $\lceil (a + b)\nu \rceil = \lceil a\nu \rceil + \lceil b\nu \rceil - 1$, donc

\[f(a + b, b) = (a + b)\lceil b\nu \rceil - b\big(\lfloor a\nu \rfloor + \lfloor b\nu \rfloor\big) = f(a, b) + b\big(\lceil b\nu \rceil - \lfloor b\nu \rfloor\big) = f(a, b) + b\]

et

\[f(a, b + a) = a\big(\lceil b\nu \rceil + \lceil a\nu \rceil - 1\big) - (b + a)\lfloor a\nu \rfloor = f(a, b) + a\big(\lceil a\nu \rceil - 1 - \lfloor a\nu \rfloor\big) = f(a, b).\]

De même, si $\{a\nu\} + \{b\nu\} \geq 1$, on obtient

\[f(a + b, b) = f(a, b) \quad \text{et} \quad f(a, b + a) = f(a, b) + a.\]

Dans les deux cas, l'un des nombres $f(a + b, b)$ et $f(a, b + a)$ est égal à $f(a, b)$, tandis que l'autre le dépasse de $a$ ou de $b$. Ainsi, exactement l'une des paires $(a + b, b)$ et $(a, b + a)$ est excellente (pour une valeur convenable de $m$).

Disons que les paires $(a + b, b)$ et $(a, b + a)$ sont les enfants de la paire $(a, b)$, et que celle-ci est leur parent. Si une paire $(c, d)$ s'obtient à partir de $(a, b)$ en passant plusieurs fois d'un parent à un enfant, on dit que $(c, d)$ est un descendant de $(a, b)$, et $(a, b)$ un ancêtre de $(c, d)$ (une paire n'est ni son propre ancêtre ni son propre descendant). Chaque paire $(a, b)$ a deux enfants ; elle a un unique parent si $a \neq b$, et aucun sinon. Toute paire d'entiers distincts a donc un unique ancêtre de la forme $(a, a)$ ; il s'agit maintenant de compter les descendants $m$-excellents de chacune de ces paires.

Remarquons que si une paire $(a, b)$ est $m$-excellente, alors $\min\{a, b\} \leq m$. En effet, si $a = b$, alors $f(a, a) = a = m$. Sinon, la paire $(a, b)$ est un enfant d'une paire $(a', b')$. Si $b = b'$ et $a = a' + b'$, on doit avoir $m = f(a, b) = f(a', b') + b'$, donc $b = b' = m - f(a', b') < m$. De même, si $a = a'$ et $b = b' + a'$, alors $a < m$.

Considérons l'ensemble $S_m$ de toutes les paires $(a, b)$ telles que $f(a, b) \leq m$ et $\min\{a, b\} \leq m$. Tous les ancêtres des éléments de $S_m$ sont encore dans $S_m$, et chaque élément de $S_m$ est soit de la forme $(a, a)$ avec $a \leq m$, soit a un unique ancêtre de cette forme. D'après ce qui précède, toutes les paires $m$-excellentes sont dans $S_m$.

Montrons que $S_m$ est fini. Supposons par exemple qu'il contienne une infinité de paires $(c, d)$ avec $d > 2m$. Une telle paire est nécessairement un enfant de $(c, d - c)$, donc un descendant d'une paire $(c, d')$ avec $m < d' \leq 2m$. L'une des paires $(a, b) \in S_m$ avec $m < b \leq 2m$ a donc une infinité de descendants dans $S_m$, tous de la forme $(a, b + ka)$ avec $k \geq 1$ entier. Comme $f(a, b + ka)$ ne décroît pas quand $k$ augmente, elle devient constante pour $k \geq k_0$. Cela signifie que $\{a\nu\} + \{(b + ka)\nu\} < 1$ pour tout $k \geq k_0$. Mais alors $1 > \{(b + ka)\nu\} = \{(b + k_0 a)\nu\} + (k - k_0)\{a\nu\}$ pour tout $k > k_0$, ce qui est absurde. On montre de même que $S_m$ contient un nombre fini de paires $(c, d)$ avec $c > 2m$ ; il est donc fini.

On peut maintenant prouver le lemme essentiel.

Lemme. Soit $(a, b)$ une paire avec $f(a, b) \neq m$. Le nombre $g(a, b)$ de ses descendants $m$-excellents est égal au nombre $h(a, b)$ d'écritures de $t = m - f(a, b)$ sous la forme $t = ka + \ell b$ avec $k$ et $\ell$ entiers positifs ou nuls.

Preuve. Par récurrence sur le nombre $N$ de descendants de $(a, b)$ dans $S_m$. Si $N = 0$, alors clairement $g(a, b) = 0$. Supposons $h(a, b) > 0$, et sans perte de généralité $a \leq b$. Alors $m - f(a, b) \geq a$, donc $f(a, b + a) \leq f(a, b) + a \leq m$ et $a \leq m$, d'où $(a, b + a) \in S_m$, ce qui est impossible. Dans le cas initial, on a donc $g(a, b) = h(a, b) = 0$, comme voulu.

Soit maintenant $N > 0$. Supposons $f(a + b, b) = f(a, b) + b$ et $f(a, b + a) = f(a, b)$ (l'autre cas est analogue). Si $f(a, b) + b \neq m$, l'hypothèse de récurrence donne

\[g(a, b) = g(a + b, b) + g(a, b + a) = h(a + b, b) + h(a, b + a).\]

(Les paires $(a + b, b)$ et $(a, b + a)$ sont des descendants de $(a, b)$, donc chacune a strictement moins de descendants dans $S_m$ que $(a, b)$.)

Ensuite, chacune des $h(a + b, b)$ écritures de $m - f(a + b, b) = m - b - f(a, b)$ sous la forme $k'(a + b) + \ell' b$ fournit l'écriture $m - f(a, b) = ka + \ell b$ avec $k = k' < k' + \ell' + 1 = \ell$. De même, chacune des $h(a, b + a)$ écritures de $m - f(a, b + a) = m - f(a, b)$ sous la forme $k'a + \ell'(b + a)$ fournit l'écriture $m - f(a, b) = ka + \ell b$ avec $k = k' + \ell' \geq \ell' = \ell$. Cette correspondance est évidemment bijective, donc

\[h(a, b) = h(a + b, b) + h(a, b + a) = g(a, b),\]

comme voulu.

Enfin, si $f(a, b) + b = m$, alors $(a + b, b)$ est $m$-excellente, donc $g(a, b) = 1 + g(a, b + a) = 1 + h(a, b + a)$ par hypothèse de récurrence. D'autre part, le nombre $m - f(a, b) = b$ a l'écriture $0 \cdot a + 1 \cdot b$, et parfois une écriture de plus de la forme $ka + 0 \cdot b$ ; cette dernière existe en même temps que l'écriture $m - f(a, b + a) = ka + 0 \cdot (b + a)$, donc $h(a, b) = 1 + h(a, b + a)$ aussi. L'hérédité est donc prouvée dans ce cas aussi. $\square$

On termine facilement. Il existe une unique paire $m$-excellente de la forme $(a, a)$, et toute autre paire $m$-excellente $(a, b)$ a un unique ancêtre de la forme $(x, x)$ avec $x < m$. Par le lemme, pour tout $x < m$, le nombre de ses descendants $m$-excellents est $h(x, x)$, c'est-à-dire le nombre d'écritures de $m - f(x, x) = m - x$ sous la forme $kx + \ell x$ (avec $k$, $\ell$ entiers positifs ou nuls). Ce nombre vaut $0$ si $x \nmid m$, et $\frac{m}{x}$ sinon. Le nombre total de paires excellentes est donc

\[1 + \sum_{x \mid m, \; x < m} \frac{m}{x} = 1 + \sum_{d \mid m, \; d > 1} d = \sum_{d \mid m} d,\]

comme voulu. $\blacksquare$

Remarque¶

Esquissons le plan d'une autre solution. L'idée est de vérifier que le nombre de paires excellentes ne dépend pas du nombre irrationnel $\nu$, puis de le calculer pour une valeur commode de $\nu$. On introduit pour cela un langage géométrique, et l'on ne traite que les paires excellentes $(a, b)$ avec $a \neq b$.

Partie I. Pour $\nu$ irrationnel positif et tout entier $n \geq 1$, on introduit les points entiers $F_\nu(n) = (n, \lfloor n\nu \rfloor)$ et $C_\nu(n) = (n, \lceil n\nu \rceil)$ du plan. La condition $(\ast)$ s'écrit $[O F_\nu(a) C_\nu(b)] = \frac{m}{2}$, où $[\cdot]$ désigne l'aire algébrique. Soient $\ell_\nu$, $\ell_\nu^+$ et $\ell_\nu^-$ les droites d'équations $y = \nu x$, $y = \nu x + 1$ et $y = \nu x - 1$.

a) Considérons d'abord les paires excellentes $(a, b)$ avec $a < b$. Pour $a$ donné, tous les points $C$ tels que $[O F_\nu(a) C] = \frac{m}{2}$ sont sur une droite $f_\nu(a)$ ; s'il existe des paires bonnes $(a, b)$, cette droite contient au moins un point entier, ce qui arrive exactement quand $\operatorname{pgcd}(a, \lfloor a\nu \rfloor) \mid m$. Soit $P_\nu(a)$ l'intersection de $\ell_\nu^+$ et $f_\nu(a)$, et $p_\nu(a)$ son abscisse (irrationnelle si elle est non nulle). Si $(a, b)$ est bonne, le point $C_\nu(b)$ est sur $f_\nu(a)$, donc le point de $f_\nu(a)$ d'abscisse $b$ est entre $\ell_\nu$ et $\ell_\nu^+$ et il est entier. Si de plus $(a, b - a)$ n'est pas bonne, le point de $f_\nu(a)$ d'abscisse $b - a$ est au-dessus de $\ell_\nu^+$ (figure 1). Ainsi, la paire $(a, b)$ avec $b > a$ est excellente exactement quand $p_\nu(a)$ est entre $b - a$ et $b$ et que le point de $f_\nu(a)$ d'abscisse $b$ est entier (c'est alors $C_\nu(b)$). Si $p_\nu(a) > a$, le nombre de paires excellentes de la forme $(a, b)$ avec $b > a$ est donc $\operatorname{pgcd}(a, \lfloor a\nu \rfloor)$.

Figure (remarques)

b) De même, pour les paires $(a, b)$ avec $a > b$, on fixe $b$, on introduit la droite $c_\nu(b)$ des points $F$ tels que $[O F C_\nu(b)] = \frac{m}{2}$, on suppose qu'elle contient un point entier (c'est-à-dire $\operatorname{pgcd}(b, \lceil b\nu \rceil) \mid m$), et l'on note $Q_\nu(b)$ le point commun de $c_\nu(b)$ et $\ell_\nu^-$, d'abscisse $q_\nu(b)$. Comme précédemment, la paire $(a, b)$ est excellente exactement quand $q_\nu(b)$ est entre $a - b$ et $a$ (le livret écrit $q_\nu(a)$ ; il faut lire $q_\nu(b)$) et que le point de $c_\nu(b)$ d'abscisse $a$ est entier (figure 2). Si $q_\nu(b) > b$, le nombre de paires excellentes de la forme $(a, b)$ avec $a > b$ est $\operatorname{pgcd}(b, \lceil b\nu \rceil)$.

Partie II, esquissée. Une fois cette description obtenue, on peut étudier comment le nombre de paires excellentes varie quand $\nu$ augmente, puis le calculer pour une valeur commode de $\nu$ ; par exemple, le calcul est assez facile pour $\nu \in \left(1, 1 + \frac{1}{m}\right)$.

Considérons, pour la valeur initiale de $\nu$, une paire excellente $(a, t)$ avec $a > t$. Quand $\nu$ augmente, cette paire finit par ne plus être excellente ; cela arrive quand le point $Q_\nu(t)$ passe par $F_\nu(a)$. Au même moment, la paire $(a + t, t)$ devient excellente à sa place. Ce processus s'arrête quand le point $Q_\nu(t)$ disparaît, c'est-à-dire quand $\nu$ franchit le rapport des coordonnées du point $T = C_\nu(t)$ ; le point $T$ est ensuite vu comme $F_\nu(t)$. Toutes les anciennes paires excellentes de la forme $(a, t)$ avec $a > t$ disparaissent, mais le même nombre de paires excellentes de premier élément $t$ apparaissent.

De même, si une paire $(t, b)$ avec $t < b$ est initialement excellente, elle cesse de l'être quand $P_\nu(t)$ passe par $C_\nu(b)$ ; au même moment, la paire $(t, b - t)$ devient excellente. Ce processus s'arrête quand $b - t < t$. À ce moment, le second élément de la paire se fixe, et le premier commence à augmenter.

On peut rendre ces idées assez précises pour montrer que le nombre de paires excellentes ne change pas. Prévenons toutefois que la mise en forme rigoureuse de la partie II est assez technique, surtout parce que l'ensemble des instants où la collection des paires excellentes change est infini. Il faut être particulièrement prudent avec les points d'accumulation de cet ensemble, qui sont exactement les instants où la droite $\ell_\nu$ passe par un point de la forme $C_\nu(b)$. Les mêmes idées peuvent s'exprimer en langage algébrique, avec les mêmes difficultés techniques.