Shortlist 2025, C2¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Colombia
Concepts : Valuations p-adiques et lemme LTE · Invariants et monovariants
Solution officielle : Shortlist officielle 2025 (avec solutions), section C2 (livret PDF)
Énoncé¶
There is a row of \(n\) paddocks, labelled from left to right with the integers \(1\) to \(n\), where \(n \geq 3\). Skippy the Kangaroo grazes in the paddocks according to the following rule:
If Skippy is grazing in paddock \(k\), then she makes a sequence of \(k\) hops from a paddock to an adjacent paddock. The first of the \(k\) hops is always to the right, unless Skippy is in paddock \(n\), in which case it is to the left. Each of the following \(k - 1\) hops is in the same direction as the previous hop, unless Skippy is in paddock \(1\) or \(n\). Skippy grazes in the paddock that she is in after the \(k\)-th hop.
For example, if \(n = 8\) and Skippy is grazing in paddock \(3\), then the next four paddocks she grazes in are \(6\), \(4\), \(8\) and \(2\), in this order.
Skippy continues grazing in this way indefinitely. A paddock is overgrazed if Skippy eventually grazes in it, regardless of the paddock that she starts in. Determine all \(n \geq 3\) for which there is exactly one overgrazed paddock.
Indices : les idées clés
- Formule explicite : le prochain enclos est \(f(k) = 2k\), \(2(n-k)\) ou \(2\) selon la position de \(k\) ; il y a un unique enclos surpâturé si et seulement si \(f\) a un unique point périodique, qui est alors un point fixe.
- Le point fixe \(q = \frac{2n}{3}\) : il n'existe que si \(3 \mid n\).
- Puissances de 2 qui divisent (solution 1) : si \(2^t \mid k\) avec \(2^t \mid n\), alors \(2^{t+1} \mid f(k)\) ; la divisibilité par \(2\) « progresse » le long d'une orbite.
- Ensemble stable (solution 1, preuve 2) : un nombre premier impair \(p \mid n\) ne divise jamais les itérés de \(1\).
- Réduction \(n = 2m \to m\) (solution 2) : les orbites périodiques de \(f_{2m}\) correspondent bijectivement à celles de \(f_m\) ; pour \(n\) impair, \(f\) permute les enclos pairs.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions et une remarque).
Réponse : il y a exactement un enclos surpâturé si et seulement si \(n = 3 \cdot 2^s\) pour un entier \(s \geq 0\).
Solution 1¶
Préliminaires (communs aux deux solutions). Notons \([n] = \{1, 2, \ldots, n\}\) et disons que \(n\) est convergent s'il y a exactement un enclos surpâturé. Si Skippy broute dans l'enclos \(k\) :
- si \(k \leq n/2\), elle fait \(k\) sauts vers la droite et broute ensuite dans l'enclos \(2k\) ;
- si \(n/2 < k \leq n-1\), elle fait \(n - k\) sauts vers la droite puis \(k - (n-k) = 2k - n\) sauts vers la gauche, et broute ensuite dans l'enclos \(n - (2k - n) = 2(n-k)\) ;
- si \(k = n\), elle fait \(n - 1\) sauts vers la gauche puis un saut vers la droite, et broute ensuite dans l'enclos \(2\).
Ainsi, si \(f : [n] \to [n]\) désigne la fonction telle que Skippy broute dans l'enclos \(f(k)\) juste après l'enclos \(k\),
Si Skippy part de l'enclos \(a\), la suite des enclos où elle broute est l'orbite \(a, f(a), f^2(a), \ldots\). Comme \(f^t(a)\) ne prend qu'un nombre fini de valeurs, toute orbite est périodique à partir d'un certain rang. Il existe donc un enclos surpâturé si et seulement si \(f\) a une unique orbite périodique. De plus, dans ce cas, tout élément de cette orbite est surpâturé ; il y a donc un unique enclos surpâturé si et seulement si l'unique orbite périodique est un point fixe. En résumé, \(n\) est convergent si et seulement si \(f\) a un unique point périodique.
Lemme 1. Écrivons \(n = 2^s x\) avec \(x\) impair, et soit \(k < n\). Si \(2^t\) divise \(k\) avec \(t \leq s\), alors \(2^{t+1}\) divise \(f(k)\).
Preuve. Écrivons \(k = 2^t y\). Si \(k \leq n/2\), alors \(f(k) = 2k = 2^{t+1}y\). Si \(k > n/2\), alors \(f(k) = 2(n-k) = 2(2^s x - 2^t y) = 2^{t+1}(2^{s-t}x - y)\). Dans les deux cas, \(2^{t+1} \mid f(k)\) (puissances de 2 qui divisent). \(\square\)
Affirmation 1.1. \(f\) a un point fixe si et seulement si \(3 \mid n\) ; dans ce cas, \(q = \frac{2n}{3}\) est l'unique point fixe de \(f\).
Preuve. Soit \(q\) un point fixe de \(f\). Alors \(q > n/2\) car \(2q \neq q\), et \(q \neq n\) car \(f(n) = 2 \neq n\). Donc \(n/2 < q \leq n-1\) et \(f(q) = 2(n - q) = q\), ce qui donne \(q = \frac{2n}{3}\). Ainsi \(3 \mid n\) et le point fixe est unique. Réciproquement, pour \(n = 3m\), \(q = 2m\) vérifie bien \(f(q) = 2(3m - 2m) = q\). \(\square\)
En particulier, si \(3 \nmid n\), \(f\) n'a pas de point fixe et \(n\) n'est pas convergent. On suppose désormais \(3 \mid n\) et on pose \(q = \frac{2n}{3}\).
Affirmation 1.2. Si \(n = 3 \cdot 2^s\), l'orbite de tout \(a \in [n]\) contient \(q\) ; donc \(n\) est convergent.
Preuve. Ici \(q = 2^{s+1}\). Écrivons \(a = 2^t y\) avec \(y\) impair ; comme \(a \leq 3 \cdot 2^s\), on a \(t \leq s+1\). Si \(t < s\), le lemme 1 donne \(2^{t+1} \mid f(a)\), et en itérant on conclut que l'orbite de \(a\) contient un élément \(a' = 2^s z\), multiple de \(2^s\), donc avec \(z \in \{1, 2, 3\}\) (car \(a' \leq n = 3 \cdot 2^s\)). Si \(z = 2\), alors \(a' = q\) ; si \(z = 1\), alors \(f(a') = 2^{s+1} = q\). Sinon \(a' = n\), donc \(f(a') = 2\), puis \(f^s(2) = 2^{s+1} = q\) (les itérés \(2, 4, \ldots, 2^s\) sont tous \(\leq n/2\) et sont doublés). Dans tous les cas, l'orbite de \(a\) contient \(q\), donc \(q\) est l'unique point périodique. \(\square\)
Affirmation 1.3. Si \(n\) n'est pas de la forme \(3 \cdot 2^s\), il existe une orbite de \(f\) qui ne contient pas \(q\) ; donc \(n\) n'est pas convergent.
Preuve 1. Écrivons \(n = 3 \cdot 2^s x\) avec \(x > 1\) impair. Alors \(q = 2^{s+1}x\). Si \(f(k) = q\), alors soit \(2k = q\), donc \(k = q/2 = 2^s x\) ; soit \(2(n-k) = q\), donc \(k = n - q/2 = q\). Ainsi, pour \(a \neq q\), l'orbite de \(a\) contient \(q\) si et seulement si elle contient \(q/2 = 2^s x\).
Considérons \(a = 2^{s+1} < n\) (et \(a \neq q\) car \(x > 1\)). Par le lemme 1 avec \(t = s\), tous les itérés de \(a\) sont divisibles par \(2^{s+1}\) (aucun n'est égal à \(n\), qui n'est divisible que par \(2^s\)). Donc l'orbite de \(a\) ne contient pas \(q/2\), ni par conséquent \(q\). \(\square\)
Preuve 2. Comme \(n\) n'est pas de la forme \(3 \cdot 2^s\), \(q\) a un facteur premier impair \(p\) (qui divise aussi \(n\)). Soit \(k \in [n]\) non divisible par \(p\). Alors \(k \neq n\) puisque \(p \mid n\), donc \(f(k) = 2k\) ou \(f(k) = 2n - 2k\). Comme \(p\) divise \(n\) mais ne divise ni \(2\) ni \(k\), \(p\) ne divise pas \(f(k)\). L'ensemble des entiers non divisibles par \(p\) est donc stable par \(f\) ; comme \(p\) divise le point fixe \(q\), l'orbite de \(1\) ne contient pas \(q\). \(\square\)
Les affirmations 1.1 à 1.3 montrent que \(n\) est convergent si et seulement si \(n = 3 \cdot 2^s\). \(\blacksquare\)
Solution 2¶
On reprend les préliminaires de la solution 1. On utilise le lemme 2 ci-dessous pour se ramener au cas où \(n = 2\) ou \(n\) est impair. Pour tout \(n \geq 2\), notons \(f_n\) la fonction \(f\) de \((*)\) pour cette valeur de \(n\), et
Lemme 2. Si \(k < n\), alors \(f_{2n}(2k) = 2f_n(k)\).
Preuve. Si \(k \leq n/2\), alors \(f_{2n}(2k) = 2(2k) = 2f_n(k)\) ; si \(n/2 < k\), alors \(f_{2n}(2k) = 2(2n - 2k) = 2 \cdot 2(n-k) = 2f_n(k)\). \(\square\)
Affirmation 2.1. Soit \(n = 2m \geq 4\) et soit \(O = (a_1, a_2, \ldots, a_r)\) une orbite périodique de \(f_m\). Si \(O\) ne passe pas par \(m\), posons
si \(O\) passe par \(m\), avec \(a_r = m\), posons
Alors \(O'\) est une orbite périodique de \(f_n\), et l'application \(O \mapsto O'\) est une bijection entre les orbites périodiques de \(f_m\) et celles de \(f_n\).
Preuve. Si \(O\) ne passe pas par \(m\), le fait que \(O'\) soit une orbite périodique de \(f_n\) découle immédiatement du lemme 2. Supposons \(a_r = m\) et écrivons \(O' = (a'_0, a'_1, \ldots, a'_r) = (2, 2a_1, \ldots, 2a_r)\). On a \(a_1 = f_m(m) = 2\), donc \(f_n(a'_r) = f_n(n) = 2 = a'_0\) et \(f_n(a'_0) = f_n(2) = 4 = 2a_1 = a'_1\) (car \(n \geq 4\)). Pour les autres termes, \(f_n(a'_i) = a'_{i+1}\) découle du lemme 2. Donc \(O'\) est une orbite périodique de \(f_n\).
Comme \(O'\) passe par \(n\) si et seulement si \(O\) passe par \(m\), on voit que \(O \mapsto O'\) est injective sur l'ensemble des orbites périodiques de \(f_m\). Soit maintenant \(O'\) une orbite périodique de \(f_n\). D'après \((*)\), \(f(k)\) est toujours pair, donc les orbites périodiques de \(f_n\) sont contenues dans \(E_n\). En divisant chaque terme de \(O'\) par \(2\) et en supprimant \(1\) s'il apparaît, on obtient une orbite périodique \(O\) de \(f_m\) dont l'image est \(O'\). \(\square\)
Soit \(n = 2m \geq 4\). D'après l'affirmation 2.1, \(f_n\) a une unique orbite périodique si et seulement si \(f_m\) en a une ; et si \(q\) est un point fixe de \(f_m\), alors \(2q\) est un point fixe de \(f_n\), sauf si \(q = m\) (auquel cas l'orbite correspondante \((2, 2m)\) a deux éléments). Il s'ensuit que \(n = 2m\) est convergent si et seulement si \(m\) est convergent et l'unique point périodique de \(f_m\) n'est pas \(m\) (pour \(m = 2\), on parle ici de \(f_2\), même si l'énoncé suppose \(n \geq 3\)).
Il suffit donc d'étudier les cas \(n = 2\) et \(n\) impair.
- Pour \(n = 2\), on voit facilement que \((2)\) est l'unique orbite périodique de \(f_2\) ; comme ce point périodique est \(m = 2\), \(n = 4\) n'est pas convergent, et par récurrence aucune puissance de \(2\) supérieure à \(3\) n'est convergente.
- Pour \(n = 3\), on voit facilement que \((2)\) est l'unique orbite périodique de \(f_3\) ; comme \(2 \neq 3\), \(6\) est convergent, de point fixe \(4 \neq 6\), et ainsi de suite : par récurrence, tout \(n\) de la forme \(3 \cdot 2^s\) est convergent.
- Pour \(n \geq 5\) impair, l'affirmation 2.2 ci-dessous montre que tout élément de \(E_n\) est périodique ; donc \(n\) n'est pas convergent car \(|E_n| \geq 2\), et, d'après l'équivalence précédente, aucun \(2^s n\) (\(s \geq 1\)) ne l'est non plus.
Affirmation 2.2. Si \(n\) est impair, la restriction de \(f_n\) à \(E_n\) est une bijection de \(E_n\) sur \(E_n\).
Preuve. La restriction de \(f_n\) à \(E_n\) envoie \(E_n\) dans lui-même car \(f(k)\) est toujours pair. Comme \(E_n\) est fini, il suffit de montrer qu'elle est surjective. Soit \(a = 2b \in E_n\). Si \(b = 2c\) est pair, alors \(b \in E_n\) et \(f_n(b) = a\) (car \(b \leq n/2\)). Si \(b\) est impair, posons \(k = n - b = n - a/2 > n - n/2 = n/2\). Alors \(k\) est pair, car \(n\) et \(b\) sont impairs, et \(f_n(k) = 2(n - k) = 2b = a\). \(\square\)
Ceci conclut : \(n\) est convergent si et seulement si \(n = 3 \cdot 2^s\). \(\blacksquare\)
Remarques¶
Remarque 1. Pour \(n = 2^s x\) avec \(x\) impair, posons \(E^*_n = \{\ell \in [n] : 2^{s+1} \mid \ell\}\). D'après le lemme 1 avec \(t = s\), \(f\) envoie \(E^*_n\) dans \(E^*_n\), et la preuve de l'affirmation 2.2 s'adapte pour montrer que la restriction de \(f\) à \(E^*_n\) est une bijection. Tout élément de \(E^*_n\) est donc périodique, ce qui donne une troisième preuve de l'affirmation 1.3.