Shortlist 2024, A4¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Thailand
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Partie entière et majorations · Récurrence et constructions récursives · Principe extrémal
Solution officielle : Shortlist officielle 2024 (avec solutions), section A4 (livret PDF)
Énoncé¶
Let \(\mathbb{Z}_{>0}\) be the set of all positive integers. Determine all subsets \(S\) of \(\{2^0, 2^1, 2^2, \ldots\}\) for which there exists a function \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) such that
Indices : les idées clés
- Unicité de l'écriture en base 2 : si \(2^a + 2^b = 2^c + 2^d\), alors \(\{a, b\} = \{c, d\}\) (multiensembles). Toutes les solutions reposent sur cette remarque.
- Équations fonctionnelles : substitutions : développer \(f(a + b + c)\) de plusieurs façons et comparer les exposants obtenus.
- Partie entière : la construction \(f(x) = (2^k - 2^\ell)\lfloor \alpha x \rfloor - 2^\ell\) utilise \(\lfloor \alpha(x+y) \rfloor - \lfloor \alpha x \rfloor - \lfloor \alpha y \rfloor \in \{0, 1\}\).
- Récurrence (solution 1) : le lemme 1, prouvé par récurrence, compare les exposants \(e(i, 1)\) sur des blocs consécutifs.
- Principe extrémal : on considère le plus petit indice où apparaît une nouvelle valeur (solutions 1 et 2) ou le plus petit \(N\) tel que \(e(a, N - a + 1) = k\) (solution 3).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (trois solutions et une remarque).
Réponse. \(S\) peut être n'importe quelle partie à \(1\) ou \(2\) éléments.
Remarques communes. Il est commode d'utiliser des multiensembles : \(\{a, b, c\}\) désigne un multiensemble, et l'inclusion est celle des multiensembles. Toutes les solutions utilisent la propriété suivante des puissances de \(2\) : si \(2^a + 2^b = 2^c + 2^d\), alors \(\{a, b\}\) et \(\{c, d\}\) sont le même multiensemble. On pose
Solution 1¶
Clairement \(S\) est non vide. Commençons par les constructions pour \(1 \leq |S| \leq 2\).
- Si \(S = \{2^k\}\), on prend \(f(x) = cx - 2^k\) pour un entier \(c > 2^k\).
- Si \(S = \{2^k, 2^\ell\}\) avec \(k > \ell\), on prend \(f(x) = (2^k - 2^\ell)\lfloor \alpha x \rfloor - 2^\ell\), où \(\alpha > 2\) n'est pas entier. Cela marche car \(\lfloor \alpha(x+y) \rfloor - \big(\lfloor \alpha x \rfloor + \lfloor \alpha y \rfloor\big) \in \{0, 1\}\) pour tous \(x, y\), et prend les deux valeurs ; la condition \(\alpha > 2\) assure que les valeurs de \(f\) sont strictement positives.
Par récurrence immédiate,
Lemme 1. Pour tous entiers strictement positifs \(n\) et \(k\),
Preuve. Par récurrence sur \(k\) ; pour \(k = 1\), le premier multiensemble est vide. Soit \(k \geq 2\), et supposons
Par définition \(f(n+k) - f(n) - f(k) = 2^{e(n,k)}\), et d'après la formule ci-dessus,
D'après l'hypothèse de récurrence, on peut écrire
pour un certain \(a\). Donc
et \(\{e(n,k), e(k-1,1)\} = \{a, e(n+k-1,1)\}\). Ainsi \(e(k-1,1) = a\) ou \(e(k-1,1) = e(n+k-1,1)\), et dans les deux cas on obtient le résultat. \(\square\)
Lemme 2. La suite \(e(1,1), e(2,1), e(3,1), \ldots\) prend au plus deux valeurs distinctes.
Preuve. Supposons par l'absurde que \(k \geq 2\) est le plus petit indice tel que \(e(k,1) \neq e(1,1)\), et qu'il existe \(\ell > k\) avec \(e(\ell,1) \notin \{e(k,1), e(1,1)\}\). D'après le lemme 1, tout bloc de \(k\) valeurs consécutives de la suite contient au moins \(k - 1\) valeurs égales à \(e(1,1)\). Cela force
et
Mais alors le bloc \(e(\ell-1,1), e(\ell,1), e(\ell+1,1), \ldots, e(\ell+(k-1),1)\), de longueur \(k+1\), ne contient pas la valeur \(e(k,1)\), ce qui contredit le lemme 1 (appliqué avec \(k+1\)). \(\square\)
Conclusion. Pour tous \(a\) et \(b\),
pour un certain \(a \leq i \leq a + b - 1\) (lemme 1). Avec le lemme 2, \(|S| \leq 2\). \(\blacksquare\)
Solution 2¶
Les parties à \(1\) ou \(2\) éléments s'obtiennent comme dans la solution 1, et \(S\) est non vide. Supposons \(|S| \geq 3\) (avec une fonction \(f\) associée) et cherchons une contradiction. On va relier les \(e(a,b)\) aux valeurs \(e(c,1)\) avec \(c + 1 < a + b\), ce qui donne une preuve du lemme 2 de la solution 1 indépendante du lemme 1.
Relation de base. Soit \(a > 1\). On a \(f(a+b) - f(a) - f(b) = 2^{e(a,b)}\) et \(f(a) - f(a-1) - f(1) = 2^{e(a-1,1)}\), donc
De même \(f(a+b) - f(a-1) - f(b+1) = 2^{e(a-1,b+1)}\) et \(f(b+1) - f(1) - f(b) = 2^{e(b,1)}\), donc
Par unicité de l'écriture binaire, on a donc
Valeurs sur une diagonale \(a + b = n\). Fixons \(n \geq 4\) et notons \(u_a = e(a, n-a)\) pour \(1 \leq a \leq n-1\) et \(v_c = e(c, 1)\). La relation de base (avec \(c = a - 1\)) dit : si \(v_c = v_{n-1-c}\), alors \(u_{c+1} = u_c\) ; si \(v_c \neq v_{n-1-c}\), alors \(u_c = v_c\) et \(u_{c+1} = v_{n-1-c}\).
- Si \(v_c = v_{n-1-c}\) pour tout \(c\) (c'est-à-dire \(e(c,1) = e(d,1)\) pour tous \(c + d = n-1\)), alors tous les \(e(a,b)\) avec \(a + b = n\) sont égaux, et les équations ne disent pas si cette valeur coïncide avec un \(e(c,1)\), \(c + 1 < n\).
- Sinon, les valeurs \(u_a\) sont entièrement déterminées par les \(v_c\) tels que \(v_c \neq v_{n-1-c}\), et ne sont pas toutes égales. Précisément, si \(e(c,1) = j\) et \(e(n-1-c,1) = k\) avec \(j \neq k\), alors \(e(c, n-c) = j = e(n-c, c)\) et \(e(c+1, n-c-1) = k = e(n-c-1, c+1)\). Entre deux tels indices consécutifs \(c < c'\), la règle « \(u_{a} = u_{a-1}\) si \(v_{a-1} = v_{n-a}\) » recopie la valeur : \(u_{c+1} = u_{c+2} = \cdots = u_{c'}\), ce qui donne une contradiction si \(e(n-c-1,1) \neq e(c',1)\) (y compris dans le cas dégénéré \(c' = c+1\)). Avant le plus petit tel indice \(c\), les \(u_a\) (\(a < c\)) sont égaux à \(e(c, n-c)\), et de même au-delà de \(n - c\).
Autrement dit, en listant les \(u_a\) par \(a\) croissant, les « trous » entre valeurs déterminées sont remplis par copie, et deux valeurs différentes de part et d'autre d'un trou donnent une contradiction. En particulier, toute valeur \(e(a,b)\) est une valeur \(e(c,1)\) pour un certain \(c\) avec \(c + 1 \leq a + b\).
Conclusion. Si \(|S| \geq 3\), la suite \(e(c,1)\) prend au moins trois valeurs distinctes. Soit \(m\) tel que \(e(m,1)\) soit différent de tous les \(e(c,1)\) pour \(c < m\), ceux-ci prenant exactement deux valeurs distinctes (donc \(m \geq 3\)) ; c'est le premier indice où apparaît une troisième valeur.
Comme \(e(m,1)\) ne coïncide avec aucun \(e(c,1)\), \(c < m\), tous les \(e(a,b)\) avec \(a + b = m+1\) sont égaux (sinon \(e(m,1) = u_m\) serait l'une des valeurs \(v_c\), \(c \leq m-1\)), et \(e(c,1) = e(d,1)\) pour tous \(c + d = m\).
Considérons les valeurs \(e(a,b)\) avec \(a + b = m + 2\). Comme \(e(m,1) \neq e(1,1)\), on a \(e(1, m+1) = e(1,1)\) et \(e(2, m) = e(m,1)\). S'il existait un autre indice \(d\) avec \(e(d,1) \neq e(m+1-d,1)\), prenons le plus petit \(d > 1\) : la règle de copie donnerait \(e(d, m+2-d) = e(2, m) = e(m,1)\), alors que \(e(d, m+2-d) = e(d,1) \neq e(m,1)\) puisque \(d < m\) ; contradiction. Donc \(e(c,1) = e(d,1)\) pour tous \(c + d = m + 1\), sauf pour la paire \(\{1, m\}\). Mais ces égalités, avec celles pour \(c + d = m\), forment une chaîne reliant tous les \(e(c,1)\), \(c < m\) :
ce qui contredit le fait que les \(e(c,1)\), \(c < m\), prennent exactement deux valeurs. \(\blacksquare\)
Précision ajoutée : la solution 2 du livret est rédigée de façon très condensée ; on a introduit les notations \(u_a\), \(v_c\) pour la lisibilité, sans changer l'argument.
Solution 3¶
Les constructions pour \(1 \leq |S| \leq 2\) sont celles de la solution 1, et \(S\) est non vide. On suppose \(|S| \geq 3\) pour aboutir à une contradiction.
Affirmation 1. Les nombres \(e(a,b)\), \(e(b,c)\) et \(e(a,c)\) prennent au plus deux valeurs distinctes.
Preuve. En développant \(f(a+b+c)\) de trois façons, on obtient
Le résultat découle de l'égalité des trois multiensembles d'exposants : un multiensemble à deux éléments ne peut pas contenir trois valeurs distinctes. \(\square\)
Pour les affirmations 2 à 4, on fixe \(k\) (avec \(2^k \in S\)) et l'on note \(N\) le plus petit entier tel que \(e(a, N - a + 1) = k\) pour un certain \(a \leq N\).
Affirmation 2. Pour tout \(b \leq N\), \(e(b, N - b + 1) = k\).
Preuve. Supposons \(e(a, N-a+1) = k\) et \(a < b\). En développant \(f\big(a + (b-a) + (N-b+1)\big)\) de deux façons,
Par minimalité de \(N\), \(e(a, b-a) \neq k\) et \(e(N-b+1, b-a) \neq k\) (sommes des arguments \(\leq N\)), donc \(e(b, N-b+1) = e(N-a+1, a) = k\). Le cas \(a > b\) s'obtient en remplaçant \(a\) et \(b\) par \(N - a + 1\) et \(N - b + 1\). \(\square\)
Affirmation 3. \(e(a,1) = e(N-a+1,1)\) pour tout \(a\) tel que \(1 < a < N\).
Preuve. D'après l'affirmation 2, \(e(a, N-a+1) = k\). D'après l'affirmation 1, \(e(a, N-a+1)\), \(e(a,1)\) et \(e(N-a+1,1)\) prennent au plus deux valeurs. Par minimalité de \(N\), \(e(a, N-a+1) \neq e(a,1)\) et \(e(a, N-a+1) \neq e(N-a+1,1)\) ; donc \(e(a,1) = e(N-a+1,1)\). \(\square\)
Affirmation 4. \(e(a,1) = e(N-a,1)\) pour tout \(a\) tel que \(1 \leq a < N\).
Preuve. D'après l'affirmation 2, \(e(a, N-a+1) = e(a+1, N-a) = k\). En développant \(f\big(1 + a + (N-a)\big)\) de deux façons,
Donc \(e(1,a) = e(1, N-a)\). \(\square\)
Conclusion. Si \(|S| \geq 3\), il existe \(k \neq \ell\) avec \(1 < N_k < N_\ell\), où \(N_k\) et \(N_\ell\) sont les valeurs minimales correspondantes. Les affirmations 3 et 4 (pour \(N_\ell\)) impliquent que \(e(a,1)\) est constant pour \(1 \leq a < N_\ell\), ce qui est une contradiction. \(\blacksquare\)
Précision ajoutée : en combinant les affirmations 4 et 3, \(e(a,1) = e(N_\ell - a, 1) = e(a+1, 1)\) pour \(1 \leq a \leq N_\ell - 2\) ; or \(e(N_k, 1) = k\) (affirmation 2 pour \(N_k\), avec \(b = N_k\)) tandis que \(e(1,1) \neq k\) par minimalité de \(N_k > 1\), ce qui contredit la constance.
Remarques¶
Remarque (sur la construction). Dans la construction de la solution 1, la condition \(\alpha > 2\) n'est nécessaire que si \(k = \ell + 1\), pour garantir \(f(1) \neq 0\). Sinon, tout \(\alpha > 1\) non entier convient.