Shortlist 2025, A7¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Thailand
Concepts : Partie entière et majorations · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2025 (avec solutions), section A7 (livret PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
For each integer \(k \geq 3\), prove that there exists a unique tuple \((x_1, x_2, \ldots, x_k)\) of positive real numbers such that \(x_1 \geq x_2 \geq \cdots \geq x_k\) and
for every integer \(n\).
Here \(\lfloor z \rfloor\) denotes the greatest integer less than or equal to \(z\). For example, \(\lfloor -\pi \rfloor = -4\) and \(\lfloor 2 \rfloor = \lfloor 2.9 \rfloor = 2\).
Indices : les idées clés
- Partie entière et majorations : l'identité \(\lfloor x + \frac{1}{2} \rfloor = \lfloor 2x \rfloor - \lfloor x \rfloor\) rend la somme télescopique pour le bon \(k\)-uplet, et diviser par \(n\) puis faire \(n \to \infty\) donne \(x_1 + \cdots + x_k = 1\).
- Développement binaire (solution 1) : \(\lfloor x + \frac{1}{2} \rfloor - \lfloor x \rfloor\) est le premier chiffre binaire de \(\{x\}\) ; la condition dit qu'à chaque rang exactement un des \(x_i\) a un chiffre \(1\), et une sous-additivité \(c_{m+n} \leq c_m + c_n\) force la structure périodique des chiffres.
- Boules et seaux (solution 2) : on lâche des boules aux points \(a / x_i\), \(a \in \mathbb{Z} + \frac{1}{2}\) ; la condition équivaut à « une boule exactement par seau », et deux fenêtres de même longueur contiennent presque le même nombre de boules de chaque couleur.
- Récurrence et constructions récursives (solution 2) : la suite des couleurs commence par \(T_j = T_{j-1} * j * T_{j-1}\), ce qu'on prouve par une double récurrence.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions et une remarque).
Solution 1¶
Observations. Pour tout réel \(x\),
Si \((x_1, \ldots, x_k)\) convient, comme \(nx - \frac{1}{2} < \lfloor nx + \frac{1}{2} \rfloor \leq nx + \frac{1}{2}\), en divisant l'égalité par \(n\) et en faisant tendre \(n\) vers l'infini, on obtient
en particulier tous les \(x_i\) sont dans \(]0, 1[\). Inspiré par (1), on écrit la partie fractionnaire en base \(2\) :
où \(\langle x \rangle_i \in \{0, 1\}\) est le \(i\)-ème chiffre binaire. On a
Existence. Le \(k\)-uplet cherché a la propriété suivante : pour tout \(i \geq 1\), il existe un unique \(j\) tel que \(\langle x_j \rangle_i = 1\) ; plus précisément, \(x_1\) a ses chiffres \(1\) aux rangs \(1, k+1, 2k+1, \ldots\), \(x_2\) aux rangs \(2, k+2, \ldots\), et ainsi de suite jusqu'à \(x_k\) aux rangs \(k, 2k, \ldots\). Autrement dit, on affirme que
convient. En effet, avec (1) et \(x_i = 2x_{i+1}\), la somme télescope :
Unicité. Soit \((x_1, \ldots, x_k)\) un \(k\)-uplet qui convient ; on sait que \(x_1 + \cdots + x_k = 1\) et que tous les \(x_i\) sont dans \(]0, 1[\). Première étape : montrer que pour tout rang \(r \geq 1\), il existe un unique \(j\) avec \(\langle x_j \rangle_r = 1\).
Pour \(n, r \geq 1\), posons
Comme \(\langle x \rangle_r = \langle 2^{r-1}x \rangle_1\), on a \(c(n, r) = c(n 2^{r-1}, 1)\).
Affirmation 1.1. \(c(n, r)\) ne dépend pas de \(r\).
Preuve. En combinant (1) et (2),
En sommant (4) pour \(x = nx_1, \ldots, nx_k\), le membre de gauche vaut \(2n - 2n = 0\), d'où \(c(2n, 1) = c(n, 1)\). Avec \(c(n, r) = c(n 2^{r-1}, 1)\), on conclut. \(\square\)
On note \(c_n\) la valeur commune des \(c(n, r)\) ; on a vu que \(c_{2n} = c_n\).
Affirmation 1.2. \(c_1 = 1\) et \(c_{m+n} \leq c_m + c_n\) pour tous \(m, n \geq 1\). De plus, si \(c_{m+n} = c_m + c_n\), alors \(\langle mx_i \rangle_r + \langle nx_i \rangle_r \leq 1\) pour tous \(i\) et \(r\).
Preuve. En sommant (2) pour \(nx_1, \ldots, nx_k\),
Comme les \(x_i\) sont \(< 1\), \(c_1 = 1\). Avec (5) et \(\lfloor mx_i \rfloor + \lfloor nx_i \rfloor \leq \lfloor (m+n)x_i \rfloor\), on obtient \(c_{m+n} \leq c_m + c_n\). Si \(c_{m+n} = c_m + c_n\), alors \(c_{m2^r + n2^r} = c_{m2^r} + c_{n2^r}\) pour tout \(r \geq 0\) (car \(c_{2n} = c_n\)), donc on a l'égalité
pour tous \(i\) et \(r \geq 0\) (chaque terme de la somme vérifiant déjà l'inégalité \(\leq\)). L'égalité (6) entraîne \(\langle mx_i \rangle_r + \langle nx_i \rangle_r \leq 1\). \(\square\)
L'égalité \(c_1 = 1\) signifie que pour tout \(r \geq 1\),
c'est-à-dire qu'il existe un unique indice \(a_r \in \{1, \ldots, k\}\) tel que \(\langle x_{a_r} \rangle_r = 1\). C'est la première étape. Il reste à prouver que \(a_r\) est l'unique élément de \(\{1, \ldots, k\}\) congru à \(r\) modulo \(k\), ce qui donnera le \(k\)-uplet (3).
On regroupe les termes consécutifs égaux de la suite \(a_1, a_2, \ldots\) en segments, notés \((\nu, t, \ell)\) : \(\nu\) est la valeur répétée (la valeur du segment), \(t\) l'indice de début et \(\ell\) la longueur. Par exemple, les trois premiers segments de \(3, 1, 2, 2, 2, 2, 3, \ldots\) sont \((3, 1, 1)\), \((1, 2, 1)\) et \((2, 3, 4)\).
Affirmation 1.3. Hormis le premier segment, tous les segments de valeur \(\nu\) sont précédés par des segments d'une même valeur.
Preuve. Supposons qu'il existe deux segments \((\nu, t_1, \ell_1)\) et \((\nu, t_2, \ell_2)\) avec \(1 < t_1 < t_2\), précédés de segments de valeurs \(\nu_1 \neq \nu_2\) ; en particulier \(\nu_1, \nu_2 \neq \nu\). Les chiffres binaires de rangs \(t_1 - 1\), \(t_1\) (resp. \(t_2 - 1\), \(t_2\)) donnent un encadrement de \(\{2^{t_1 - 2}x\}\) (resp. \(\{2^{t_2 - 2}x\}\)), qui s'écrit en binaire \(0{,}\langle x \rangle_{t_1 - 1}\langle x \rangle_{t_1}\ldots\) :
| \(x\) | \(\langle x \rangle_{t_1-1}\), \(\langle x \rangle_{t_1}\) | \(\{2^{t_1-2}x\}\) dans | \(\langle x \rangle_{t_2-1}\), \(\langle x \rangle_{t_2}\) | \(\{2^{t_2-2}x\}\) dans |
|---|---|---|---|---|
| \(x_\nu\) | \(0, 1\) | \([1/4, 1/2[\) | \(0, 1\) | \([1/4, 1/2[\) |
| \(x_{\nu_1}\) | \(1, 0\) | \([1/2, 3/4[\) | \(0, 0\) | \([0, 1/4[\) |
| \(x_{\nu_2}\) | \(0, 0\) | \([0, 1/4[\) | \(1, 0\) | \([1/2, 3/4[\) |
Avec \(n = 2^{t_1 - 2} + 2^{t_2 - 2}\), on obtient \(\frac{1}{2} \leq \{nx_i\} < 1\) pour \(i \in \{\nu, \nu_1, \nu_2\}\), donc \(\langle nx_i \rangle_1 = 1\) pour ces trois indices, et \(c_n \geq 3\). Mais d'après l'affirmation 1.2, \(c_n \leq c_{2^{t_1-2}} + c_{2^{t_2-2}} = c_1 + c_1 = 2\) : contradiction. \(\square\)
Comme \(0 < x_i < 1\) pour tout \(i\), chaque valeur \(\nu \in \{1, \ldots, k\}\) est la valeur d'au moins un segment. D'après l'affirmation 1.3, chaque valeur détermine la valeur qui la précède. Donc les valeurs des \(k\) premiers segments forment une permutation de \(\{1, \ldots, k\}\), qui se répète ensuite périodiquement.
Affirmation 1.4. Tous les segments, sauf peut-être le premier, ont la même longueur \(\ell\), et le premier a une longueur au plus \(\ell\).
Preuve. Soit \(\ell\) la longueur minimale d'un segment non initial, et \((\nu, t, \ell)\) un segment non initial de cette longueur, précédé du segment \((\nu_0, t_0, \ell_0)\). Chaque segment ayant une longueur au moins \(\ell\) et \(k \geq 3\), deux segments de même valeur sont séparés par au moins \(2\ell\) termes. On lit les chiffres de \(x_\nu\) et \(x_{\nu_0}\) à partir du rang \(t - 1\), puis à partir du rang \(t + \ell - 1\) :
| \(x\) | chiffres à partir du rang \(t-1\) | \(\{2^{t-2}x\}\) dans |
|---|---|---|
| \(x_\nu\) | \(0\,\underbrace{1 \cdots 1}_{\ell}\,\underbrace{0 \cdots 0}_{2\ell}\) | \([1/4,\ 1/2 - 2^{-\ell-1} + 2^{-3\ell-1}[\) |
| \(x_{\nu_0}\) | \(1\,0 \cdots\) | \([1/2,\ 3/4[\) |
| \(x\) | chiffres à partir du rang \(t+\ell-1\) | \(\{2^{t+\ell-2}x\}\) dans |
|---|---|---|
| \(x_\nu\) | \(1\,\underbrace{0 \cdots 0}_{2\ell}\) | \([1/2,\ 1/2 + 2^{-2\ell-1}[\) |
| \(x_{\nu_0}\) | \(\underbrace{0 \cdots 0}_{\ell+1}\) | \([0,\ 2^{-\ell-1}[\) |
Posons \(n = 2^{t-2} + 2^{t+\ell-2}\). Comme \(\ell \geq 1\), \(\left(\frac{1}{2} - 2^{-\ell-1} + 2^{-3\ell-1}\right) + \left(\frac{1}{2} + 2^{-2\ell-1}\right) < 1\). Donc \(\frac{1}{2} \leq \{nx_\nu\}, \{nx_{\nu_0}\} < 1\) et \(\langle nx_\nu \rangle_1 = \langle nx_{\nu_0} \rangle_1 = 1\). On obtient l'égalité serrée
S'il existait un segment \((\nu', t', \ell')\) avec \(\ell' > \ell\), on aurait \(\langle x_{\nu'} \rangle_{t'} = \langle 2^\ell x_{\nu'} \rangle_{t'} = 1\), ce qui contredit le cas d'égalité de l'affirmation 1.2 pour \(c_{2^\ell + 1} = c_{2^\ell} + c_1\). \(\square\)
Conclusion : \(\ell = 1\). Soit \(\lambda\) la longueur du premier segment. D'après les affirmations 1.3 et 1.4, les nombres \(\{2^\lambda x_1\}, \ldots, \{2^\lambda x_k\}\) sont, à l'ordre près,
Le développement binaire de \(\frac{(2^{\ell+1} - 1)(2^\ell - 1)}{2^{k\ell} - 1}\) est périodique de période \(k\ell\), et la somme des chiffres binaires du bloc répété \((2^{\ell+1} - 1)(2^\ell - 1)\) vaut \(\ell + 1\) ; ainsi
Avec \(n = 2^\lambda(2^{\ell+1} - 1)\), on obtient donc
qui n'est entier que pour \(\ell = 1\) (le livret omet le facteur \(\frac{1}{k\ell}\) devant la double somme ; il est nécessaire pour obtenir \(\frac{k(\ell+1)}{k\ell}\)). D'après l'affirmation 1.4, \(\lambda = 1\) aussi, et (avec \(x_1 \geq \cdots \geq x_k\))
Solution 2¶
Notons \(\mathbb{Z} + \frac{1}{2} = \{\ldots, -\frac{3}{2}, -\frac{1}{2}, \frac{1}{2}, \frac{3}{2}, \ldots\}\). Pour tout réel \(x\),
En sommant pour \(x = nx_1, \ldots, nx_k\) (le total vaut \(n + (-n) = 0\)), on obtient \(nx_i \notin \mathbb{Z} + \frac{1}{2}\) pour tous \(n\) et \(i\) : \(\frac{a}{x_i}\) n'est jamais entier pour \(a \in \mathbb{Z} + \frac{1}{2}\).
Le procédé. Pour chaque entier \(N\), on place un seau sur l'intervalle \(]N, N+1[\). Pour chaque \(a \in \mathbb{Z} + \frac{1}{2}\) et chaque \(i\), on lâche une boule de couleur \(i\) au point \(\frac{a}{x_i}\) ; elle tombe dans le seau de l'intervalle qui le contient. Par construction, la configuration est symétrique par rapport à \(0\).
Lemme 1. Supposons \(mx_i \notin \mathbb{Z} + \frac{1}{2}\) pour tous \(m \in \mathbb{Z}\) et \(i\). Alors chaque seau contient exactement une boule si et seulement si \(\sum_{i=1}^{k} \lfloor nx_i + \frac{1}{2} \rfloor = n\) pour tout \(n \in \mathbb{Z}\).
Preuve. Par symétrie, chaque seau contient exactement une boule si et seulement si exactement \(n\) boules tombent dans \(]0, n[\) pour tout \(n \geq 1\). De même, d'après l'identité ci-dessus, l'égalité \(\sum_i \lfloor nx_i + \frac{1}{2} \rfloor = n\) est vraie pour tout \(n \in \mathbb{Z}\) si et seulement si elle l'est pour tout \(n \geq 1\). Une boule de couleur \(i\) tombe dans \(]0, n[\) si et seulement si elle a été lâchée en \(\frac{a}{x_i}\) avec \(a \in \mathbb{Z} + \frac{1}{2}\) et \(0 < a < nx_i\) ; leur nombre est le plus grand entier strictement inférieur à \(nx_i + \frac{1}{2}\), qui vaut \(\lfloor nx_i + \frac{1}{2} \rfloor\) puisque \(nx_i \notin \mathbb{Z} + \frac{1}{2}\). On somme sur les couleurs. \(\square\)
Chaque seau contenant exactement une boule, on considère la suite des couleurs \(\ldots, C_{-3/2}, C_{-1/2}, C_{1/2}, C_{3/2}, \ldots\) (la suite complète), où \(C_{N + 1/2}\) est la couleur de la boule du seau \(]N, N+1[\), et la suite positive \(C_{1/2}, C_{3/2}, \ldots\). Par symétrie, \(C_a = C_{-a}\) pour tout \(a \in \mathbb{Z} + \frac{1}{2}\). Un bloc de couleur \(i\) est une sous-suite consécutive maximale formée uniquement de \(i\), et un trou de couleur \(i\) une sous-suite consécutive maximale ne contenant aucun \(i\).
Lemme 2. Pour tous \(y, z \in \mathbb{Z} + \frac{1}{2}\), tout \(\ell \geq 1\) et toute couleur \(i\), les nombres d'occurrences de \(i\) dans \(C_{y+1}, \ldots, C_{y+\ell}\) et dans \(C_{z+1}, \ldots, C_{z+\ell}\) diffèrent d'au plus \(1\). Par conséquent, deux blocs de \(i\) ont des longueurs qui diffèrent d'au plus \(1\), et de même pour deux trous de \(i\).
Preuve. Le nombre d'occurrences de \(i\) dans \(C_{y+1}, \ldots, C_{y+\ell}\) est le nombre de boules de couleur \(i\) tombées dans \(]y + \frac{1}{2}, y + \ell + \frac{1}{2}[\), c'est-à-dire le nombre de multiples de \(\frac{1}{x_i}\) dans \(]y + \frac{1}{2} + \frac{1}{2x_i}, y + \ell + \frac{1}{2} + \frac{1}{2x_i}[\). De même pour \(z\). Ces deux intervalles ont la même longueur, donc contiennent des nombres de multiples de \(\frac{1}{x_i}\) qui diffèrent d'au plus \(1\). \(\square\)
Dans la suite positive, les premières occurrences des couleurs apparaissent dans l'ordre \(1, 2, \ldots, k\), car \(x_1 \geq x_2 \geq \cdots \geq x_k\). En particulier \(C_{1/2} = 1\), donc \(C_{-1/2} = 1\), et par le lemme 2 (la fenêtre \(C_{-1/2}, C_{1/2}\) contient deux \(1\)), on a \(1 \in \{C_a, C_{a+1}\}\) pour tout \(a \in \mathbb{Z} + \frac{1}{2}\).
On note \(S_1 * S_2\) la concaténation de deux suites, et l'on définit récursivement \(T_1 = 1\) et \(T_j = T_{j-1} * j * T_{j-1}\). La suite \(T_j\) a pour longueur \(2^j - 1\) et contient \(2^{j-1}\) fois le \(1\). On montre par récurrence sur \(j \leq k\) les deux énoncés :
- \(A(j)\) : la suite positive commence par \(T_j\) ;
- \(B(j)\) : pour tout \(\ell > j\), toute occurrence de \(\ell\) dans la suite est précédée et suivie de \(T_j\).
On a déjà prouvé \(A(1)\) et \(B(1)\).
Affirmation 2.1. \(A(2)\) est vraie.
Preuve. Supposons que, dans la suite positive, la première occurrence de \(2\) arrive après \(r\) occurrences de \(1\). Par symétrie, les \(2r + 2\) termes centraux de la suite complète sont \(2\,1 \cdots 1\,2\) : la couleur \(1\) a un bloc de longueur \(2r\) et la couleur \(2\) un trou de longueur \(2r\). Considérons la première occurrence de \(3\) dans la suite positive ; elle est précédée et suivie de \(1\). Comme les blocs de \(1\) ont une longueur au moins \(2r - 1\) (lemme 2), il existe une sous-suite \(1 \cdots 1\,3\,1 \cdots 1\) de longueur \(4r - 1\). Comme les trous de \(2\) ont une longueur au plus \(2r + 1\), on a \(2r + 1 \geq 4r - 1\), donc \(r \leq 1\) et \(C_{3/2} = 2\). Il en découle \(C_{5/2} = 1\), d'où \(A(2)\). \(\square\)
Affirmation 2.2. Pour \(2 \leq j < k\), \(B(j-1)\) et \(A(j)\) entraînent \(B(j)\). (Notons que \(B(k)\) est trivialement vraie.)
Preuve. Par \(A(j)\), le milieu de la suite complète est \(T_j * T_j = T_{j-1} * j * T_{j-1} * T_{j-1} * j * T_{j-1}\), qui contient un trou \(T_{j-1} * T_{j-1}\) de \(j\) de longueur \(2^j - 2\). Par \(B(j-1)\), toute occurrence de \(\ell > j\) est contenue dans une sous-suite \(T_{j-1} * \ell * T_{j-1}\), de longueur \(2^j - 1\) et sans \(j\). Comme les trous de \(j\) ont une longueur au plus \(2^j - 1\) (lemme 2), cette sous-suite est précédée et suivie de \(j\). En appliquant \(B(j-1)\) à ces deux occurrences de \(j\), la sous-suite \(j * T_{j-1} * \ell * T_{j-1} * j\) est contenue dans \(T_{j-1} * j * T_{j-1} * \ell * T_{j-1} * j * T_{j-1} = T_j * \ell * T_j\), d'où \(B(j)\). \(\square\)
Affirmation 2.3. Pour \(2 \leq j < k\), \(A(j)\) et \(B(j)\) entraînent \(A(j+1)\).
Preuve. Comme \(j + 1 \leq k\), la couleur \(j + 1\) apparaît dans la suite complète et, par \(B(j)\), elle est précédée et suivie de \(T_j\) : \(T_j * (j+1) * T_j\) apparaît dans la suite complète. En particulier, pour tout \(i \leq j\), il existe un trou \(T_{i-1} * (j+1) * T_{i-1}\) de \(i\), de longueur \(2^i - 1\).
Par \(A(j)\), la suite positive commence par \(T_j\) ; regardons le terme suivant \(C_{2^j - 1/2}\). Si \(C_{2^j - 1/2} = i\) avec \(2 \leq i \leq j\), alors \(T_j * i\) se termine par \(i * T_{i-1} * i\), qui contient un trou \(T_{i-1}\) de \(i\) de longueur \(2^{i-1} - 1\) ; cela contredit le lemme 2, car \(|(2^{i-1} - 1) - (2^i - 1)| > 1\). Comme \(j + 1\) n'est pas encore apparu, on a \(C_{2^j - 1/2} = 1\) ou \(C_{2^j - 1/2} = j + 1\). Si c'était \(1\), la sous-suite \(C_{-1/2}, \ldots, C_{2^j - 1/2}\) serait \(1 * T_j * 1\), de longueur \(2^j + 1\) et contenant \(2^{j-1} + 2\) fois le \(1\). Or \(T_j * (j+1) * T_j\) apparaît quelque part ; elle contient \(2 * 1 * (j+1) * T_j\), et en retirant le dernier terme on obtient une sous-suite de longueur \(2^j + 1\) contenant \(2^{j-1}\) fois le \(1\). Cela contredit le lemme 2. Donc \(C_{2^j - 1/2} = j + 1\) ; par \(B(j)\), ce terme est suivi de \(T_j\), et la suite positive commence par \(T_j * (j+1) * T_j = T_{j+1}\). \(\square\)
Périodicité. Montrons que la suite positive est \(T_k * T_k * \cdots\). Par \(A(k)\), elle commence par \(T_k\), donc le milieu de la suite complète est \(T_k * T_k\), qui contient un trou de \(k\) de longueur \(2^k - 2\) ; les trous de \(k\) ont donc une longueur dans \(\{2^k - 3, 2^k - 2, 2^k - 1\}\). D'après les arguments de la preuve de l'affirmation 2.3, une occurrence de \(T_{k-1}\) ne peut être suivie que de \(1\) ou de \(k\). Cela exclut les trous de \(k\) de longueur \(2^k - 3\) : les deux \(T_{k-1}\) entourant ce trou se chevaucheraient d'un terme, et le \(T_{k-1}\) qui suit le premier \(k\) serait suivi d'un \(2\) (pour \(k = 3\), on aurait \(\cdots 3\,1\,2\,1\,2\,1\,3 \cdots\)). Cela exclut aussi les trous de longueur \(2^k - 1\), qui seraient \(T_{k-1} * 1 * T_{k-1}\) et contiendraient en leur milieu un bloc de \(1\) de longueur \(3\) (précision ajoutée : alors qu'il existe des blocs de \(1\) de longueur \(1\), par exemple dans \(T_k\), ce qui contredit le lemme 2). Tous les trous de \(k\) ont donc la longueur \(2^k - 2\), et la suite positive est \(T_k * T_k * \cdots\).
Calcul des \(x_i\). Dans \(T_k\), la couleur \(i\) apparaît \(2^{k-i}\) fois. Donc \(M 2^{k-i}\) boules de couleur \(i\) tombent dans \(]0, M(2^k - 1)[\), pour tout \(M\). Or le nombre de boules de couleur \(i\) tombées dans \(]0, N[\), divisé par \(N\), tend vers \(x_i\) quand \(N \to \infty\). Ainsi
Vérification. D'après le lemme 1, il suffit de montrer qu'il tombe exactement une boule dans chaque seau. La boule \(\frac{a}{x_i}\) tombe dans \(]N - 1, N[\) si et seulement si la boule \(\frac{a + 2^{k-i}}{x_i}\) tombe dans \(]N + (2^k - 1) - 1, N + (2^k - 1)[\). Il suffit donc de le vérifier pour les seaux \(]0, 1[, ]1, 2[, \ldots, ]2^k - 2, 2^k - 1[\). Comme \((2^k - 1)x_i = 2^{k-i}\), les boules de couleur \(i\) tombées dans \(]0, 2^k - 1[\) sont les \(\frac{a}{x_i}\) avec \(a \in (\mathbb{Z} + \frac{1}{2}) \cap\, ]0, 2^{k-i}[\). Pour \(a = m - \frac{1}{2}\), \(1 \leq m \leq 2^{k-i}\), la boule est en
Les boules de couleur \(i\) tombent donc dans les seaux \(]N - 1, N[\) avec \(N \leq 2^k - 1\) et \(v_2(N) = i - 1\). Toutes couleurs confondues, chacun des seaux \(]0, 1[, \ldots, ]2^k - 2, 2^k - 1[\) contient exactement une boule. \(\blacksquare\)
Remarques¶
Remarque 1 (petits \(k\)). Pour \(k = 1\), \(x_1 = 1\) est l'unique solution. Pour \(k = 2\), l'unicité tombe en défaut : les solutions sont \((x_1, x_2) = (a, 1 - a)\) avec \(a \in\, ]0, \frac{1}{2}[\) qui n'est pas de la forme \(\frac{p}{q}\) avec \(p\) impair et \(q\) pair, ce qui revient essentiellement à \(mx_1, mx_2 \notin \mathbb{Z} + \frac{1}{2}\) pour tout \(m \in \mathbb{Z}\). (Précision ajoutée : le livret décrit ces couples sans tenir compte de l'ordre ; avec la contrainte \(x_1 \geq x_2\) de l'énoncé, ce sont les couples \((1 - a, a)\).) Dans ce cas, le fait que chaque seau contienne exactement une boule est lié au théorème de Beatty sur les suites de Beatty complémentaires ; mais ce théorème ne semble pas aider pour \(k \geq 3\).