Aller au contenu

Shortlist 2022, C9

Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : U.S.A.

Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Bijections et dénombrement · Partie entière et majorations

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 40 (page 42 du PDF)

Pas encore relu

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

Énoncé

Let \(\mathbb{Z}_{\geq 0}\) be the set of non-negative integers, and let \(f : \mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}\) be a bijection such that whenever \(f(x_1, y_1) > f(x_2, y_2)\), we have \(f(x_1 + 1, y_1) > f(x_2 + 1, y_2)\) and \(f(x_1, y_1 + 1) > f(x_2, y_2 + 1)\).

Let \(N\) be the number of pairs of integers \((x, y)\), with \(0 \leq x, y < 100\), such that \(f(x, y)\) is odd. Find the smallest and largest possible value of \(N\).

Indices : les idées clés
  • Réponse : \(2500 \leq N \leq 7500\), et les deux bornes sont atteintes.
  • Caractériser toutes les fonctions \(f\) : il existe \(\alpha > 0\) tel que \(f\) range les couples \((x, y)\) selon la valeur de \(x + y\alpha\) (on balaie le quadrant par une droite de pente \(-1/\alpha\)).
  • Géométrie combinatoire : pour \(\alpha\) irrationnel, \(f(a, b)\) est le nombre de points du réseau \((x, y)\), \(x, y \geq 0\), tels que \(x + y\alpha < a + b\alpha\).
  • Bijections et dénombrement : en comparant ces ensembles de points (décalage \(b \mapsto b - 1\)), on obtient \(f(x,y) + f(x+1,y+1) = f(x+1,y) + f(x,y+1) + 1\) ; chaque carré \(2 \times 2\) contient donc \(1\) ou \(3\) valeurs impaires.
  • Partie entière et majorations : pour les constructions, on compte les entiers \(x < m\alpha\) avec \(\alpha\) très proche de \(200\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2022 (une solution, accompagnée de remarques communes).

Remarques communes du livret.

  • Dans la solution de l'auteur, une formule exacte est démontrée lorsque \(\alpha\) est irrationnel : avec \(\mu = \frac{1}{\alpha}\) et \(\nu = \alpha\),

    \[f(a, b) = ab + \left(\lceil 1\mu \rceil + \lceil 2\mu \rceil + \cdots + \lceil a\mu \rceil\right) + \left(\lceil 1\nu \rceil + \lceil 2\nu \rceil + \cdots + \lceil b\nu \rceil\right).\]

    (Les bornes des sommes sont illisibles dans le livret ; nous les avons reconstituées et vérifiées numériquement.) L'auteur suggère que cela pourrait faire un joli problème d'olympiade : il n'est pas évident que cette \(f\) soit une bijection.

  • (Sur le choix de l'énoncé, par l'auteur.) De telles fonctions ont de nombreuses propriétés ; l'énoncé retenu exige de bien comprendre la situation : la propriété clé sert aux bornes, la formule sert aux constructions. Un énoncé plus court (prouver seulement la propriété clé) risquerait d'admettre des solutions qui « ne voient pas tout », par exemple par récurrence en examinant les positions possibles de \(n+1\) connaissant celles de \(0, \ldots, n\) ; l'énoncé actuel en admet sans doute aussi. On lui a suggéré de ne demander qu'une des deux bornes, les deux parties étant très semblables, mais il a préféré garder la symétrie.

  • (Comité de sélection.) La vraie difficulté est de comprendre toute la situation, en particulier le fonctionnement de \(f\) et le comportement du quadrant : la solution caractérise toutes les fonctions \(f\) avant même de parler de parité.

Réponse : les valeurs optimales sont \(N_{\min} = 2500\) et \(N_{\max} = 7500\).

Solution

On commence par caractériser toutes les fonctions \(f\), puis on établit une formule et une propriété clé ; on résout enfin le problème, constructions comprises.

Caractérisation. La condition peut s'écrire sous la forme plus forte

\[f(x_1, y_1) > f(x_2, y_2) \iff f(x_1 + 1, y_1) > f(x_2 + 1, y_2) \iff f(x_1, y_1 + 1) > f(x_2, y_2 + 1)\]

(car \(f\) est injective). En particulier, pour \((k, l)\) fixé, la différence \(f(x + k, y) - f(x, y + l)\) a le même signe pour tous \(x\) et \(y\).

Un vecteur non nul \((k, l) \in \mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0}\) est une aiguille si \(f(x + k, y) - f(x, y + l) > 0\) pour tous \(x, y\). On vérifie sans peine que les aiguilles et les non-aiguilles sont toutes deux stables par addition, donc aussi par division par un entier (quand le quotient est dans \(\mathbb{Z}^2\)). Un rationnel \(\frac{k}{l} > 0\) est appelé une note si \((k, l)\) est une aiguille (c'est bien défini, grâce à cette stabilité par multiples et quotients).

Précision ajoutée : \((1, 0)\) est une aiguille, c'est-à-dire \(f(x+1, y) > f(x, y)\) ; sinon on aurait \(f(0, y) > f(1, y) > f(2, y) > \cdots\), suite infinie strictement décroissante d'entiers naturels. De même, \(f(x, y+1) > f(x, y)\) : \(f\) est strictement croissante en chaque variable.

Les notes sont stables vers le haut. Soient des rationnels \(\frac{k_1}{l_1} < \frac{k_2}{l_2}\) avec \(\frac{k_1}{l_1}\) une note. Alors \((k_1, l_1)\) est une aiguille, donc \((k_1 l_2, l_1 l_2)\) aussi, donc \((k_2 l_1, l_1 l_2)\) aussi (on ajoute \((k_2 l_1 - k_1 l_2) \cdot (1, 0)\), avec \(k_2 l_1 - k_1 l_2 > 0\)). Donc \((k_2, l_2)\) est une aiguille.

Il existe une note. Sinon, aucun entier \(m \geq 1\) n'est une note : \((m, 1)\) n'est pas une aiguille, donc \(f(m, 0) < f(0, 1)\) pour tout \(m\), ce qui est impossible (une infinité de valeurs distinctes sous \(f(0,1)\)). De même, il existe \(m\) tel que \(f(1, 0) < f(0, m)\), donc \(\frac{1}{m}\) n'est pas une note pour \(m\) grand. (Le livret intervertit ici les deux inégalités ; nous donnons la version correcte.)

Ainsi, les petits rationnels positifs ne sont pas des notes, puis il y a une bascule, après laquelle tous sont des notes. Notons \(\alpha > 0\) le point de bascule, c'est-à-dire la borne inférieure des notes.

Propriété clé. Si \(x_1 + y_1\alpha > x_2 + y_2\alpha\), alors \(f(x_1, y_1) > f(x_2, y_2)\).

Preuve. Si \(x_1 \geq x_2\) et \(y_1 \geq y_2\), c'est clair (car \(f\) croît en chaque variable). Si \(x_1 \geq x_2\) et \(y_1 < y_2\), alors \(\frac{x_1 - x_2}{y_2 - y_1} > \alpha\) est une note, d'où \(f(x_1, y_1) > f(x_2, y_2)\). Si \(x_1 < x_2\) et \(y_1 > y_2\), alors \(\frac{x_2 - x_1}{y_1 - y_2} < \alpha\) n'est pas une note (le livret écrit \(u_1 - u_2\) au dénominateur), donc \(f(x_2, y_2) < f(x_1, y_1)\) (la différence a un signe constant et n'est jamais nulle). \(\square\)

On en déduit : la fonction \(f\) range les couples \((x, y)\) selon la valeur de \(x + y\alpha\). Si \(\alpha\) est rationnel, les ex aequo sont départagés selon la plus grande coordonnée \(x\) ou \(y\) (suivant que \(\alpha\) est une note ou non).

On peut se représenter cela ainsi : on place sous le premier quadrant une droite de pente \(-\frac{1}{\alpha}\), et on la fait monter parallèlement à elle-même. Elle rencontre d'abord \((0, 0)\), donc \(f(0, 0) = 0\) ; et chaque fois qu'elle rencontre un point \(p\), \(f(p)\) est le nombre de points rencontrés auparavant. Si \(\alpha \in \mathbb{Q}\), la droite peut rencontrer plusieurs points à la fois ; ils sont alors rangés selon leur abscisse ou leur ordonnée, suivant que \(\alpha\) est une note ou non.

Réduction au cas irrationnel. On s'intéresse à la région \(A = \{(x, y) \in \mathbb{Z}_{\geq 0}^2 \mid x < 100,\ y < 100\}\). On peut supposer \(\alpha\) irrationnel : en modifiant légèrement \(\alpha\) dans le bon sens, le comportement et les valeurs de \(f\) sur \(A\) ne changent pas. Pour \(\alpha\) irrationnel, on a alors

\[f(a, b) = \#\left\{(x, y) \in \mathbb{Z}_{\geq 0}^2 \mid x + y\alpha < a + b\alpha\right\}\]

(points du réseau sous une droite).

Affirmation. \(f(x, y) + f(x+1, y+1) = f(x+1, y) + f(x, y+1) + 1\).

Preuve. On décompose selon que \(b > 0\) ou \(b = 0\), et on décale \(b \mapsto b - 1\) dans le premier ensemble (bijection) :

\[\begin{aligned} f(x+1, y+1) - f(x, y+1) &= \#\{(a, b) \in \mathbb{Z}_{\geq 0}^2 \mid x + (y+1)\alpha \leq a + b\alpha < (x+1) + (y+1)\alpha\} \\ &= \#\{(a, b) \in \mathbb{Z}_{\geq 0} \times \mathbb{Z}_{> 0} \mid x + (y+1)\alpha \leq a + b\alpha < (x+1) + (y+1)\alpha\} \\ &\quad + \#\{a \in \mathbb{Z}_{\geq 0} \mid x + (y+1)\alpha \leq a < (x+1) + (y+1)\alpha\} \\ &= \#\{(a, b) \in \mathbb{Z}_{\geq 0}^2 \mid x + y\alpha \leq a + b\alpha < (x+1) + y\alpha\} + 1 \\ &= f(x+1, y) - f(x, y). \end{aligned}\]

(Le second ensemble contient exactement un entier, car c'est un intervalle semi-ouvert de longueur \(1\) ; le livret écrit \((x+1) + y\alpha\) comme borne inférieure de cet intervalle, il faut lire \(x + (y+1)\alpha\).) \(\square\)

Les bornes. D'après l'affirmation, la somme \(f(x,y) + f(x+1,y) + f(x,y+1) + f(x+1,y+1) = 2\left(f(x+1,y) + f(x,y+1)\right) + 1\) est impaire : tout carré \(2 \times 2\) contient \(1\) ou \(3\) valeurs impaires. En découpant \(A\) en \(2500\) carrés \(2 \times 2\) disjoints, on obtient \(2500 \leq N \leq 7500\). (Le livret dit seulement que les bornes découlent « immédiatement » de l'affirmation.) Montrons que ces bornes sont atteintes.

Par l'affirmation, modulo \(2\), toutes les valeurs sur \(A\) sont déterminées par la ligne \(f(\cdot, 0)\) et la colonne \(f(0, \cdot)\).

Construction pour \(7500\). On choisit \(\alpha\) irrationnel avec \(\alpha \approx 200{,}001\). Alors :

  1. \(f(m, 0) = m\) pour \(0 \leq m \leq 100\) ;
  2. \(f(0, k) \equiv k \pmod 2\) pour \(0 \leq k \leq 100\).

Preuve. 1. \(f(m, 0) = \#\{(x, y) \mid x + y\alpha < m\} = m\), car \(y \geq 1\) donne \(x + y\alpha > 200 > m\).

  1. On compte ligne par ligne (partie entière) :

    \[f(0, k) = \#\{(x, y) \mid x + y\alpha < k\alpha\} = \sum_{l=0}^{k-1} \#\{x \mid x < (k - l)\alpha\} = \sum_{l=0}^{k-1} \left(200(k-l) + 1\right) = 200A + k\]

    pour un certain entier \(A\) (car \(200(k-l) < (k-l)\alpha < 200(k-l) + 1\)). \(\square\)

À l'aide de l'affirmation, on en déduit que, modulo \(2\), la région \(A\) a l'allure suivante : dans les lignes d'indice pair \(y = 2y'\), les restes modulo \(2\) alternent (\(0, 1, 0, 1, \ldots\)), tandis que les lignes d'indice impair ne contiennent que des nombres impairs. Cela donne \(50 \cdot 50 + 50 \cdot 100 = 7500\) valeurs impaires.

Construction pour \(2500\). On choisit \(\alpha\) irrationnel avec \(\alpha \approx 199{,}999\). Alors :

  1. \(f(m, 0) = m\) pour \(0 \leq m \leq 100\) (comme ci-dessus) ;

  2. \(f(0, k) \equiv 0 \pmod 2\) pour \(0 \leq k \leq 100\), car

    \[f(0, k) = \sum_{l=0}^{k-1} \#\{x \mid x < (k - l)\alpha\} = \sum_{l=0}^{k-1} 200(k-l) = 200A\]

    pour un certain entier \(A\) (car \(200(k-l) - 1 < (k-l)\alpha < 200(k-l)\)).

De même, modulo \(2\), les lignes d'indice pair alternent, tandis que les lignes d'indice impair ne contiennent que des nombres pairs, ce qui donne \(50 \cdot 50 = 2500\) valeurs impaires.

(Le livret associe \(\alpha \approx 199{,}999\) à la construction pour \(7500\), avec la somme \(\sum (200(k-l) - 1)\), et \(\alpha \approx 200{,}001\) à celle pour \(2500\). Le décompte des entiers \(x < (k-l)\alpha\) montre qu'il faut les échanger ; nous l'avons vérifié par calcul exact, qui donne bien \(N = 7500\) pour \(\alpha \approx 200{,}001\) et \(N = 2500\) pour \(\alpha \approx 199{,}999\).) \(\blacksquare\)