Aller au contenu

Shortlist 2007, C3

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Netherlands

Concepts : Double comptage · Équations diophantiennes : factorisation et encadrement

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 30 (page 31 du PDF)

Énoncé

Find all positive integers \(n\), for which the numbers in the set \(S = \{1, 2, \ldots, n\}\) can be colored red and blue, with the following condition being satisfied: the set \(S \times S \times S\) contains exactly \(2007\) ordered triples \((x, y, z)\) such that (i) \(x, y, z\) are of the same color and (ii) \(x + y + z\) is divisible by \(n\).

Indices : les idées clés
  • Triplets divisibles : il y en a exactement \(n^2\), puisque \(x\) et \(y\) déterminent \(z\).
  • Double comptage : chaque triplet bicolore divisible contient exactement une paire de \(R \times B\) (dans l'ordre cyclique), et chaque paire de \(R \times B\) apparaît dans exactement \(3\) triplets ; il y a donc \(n^2 - 3rb = r^2 - rb + b^2\) triplets monochromes.
  • Équation diophantienne \(r^2 - rb + b^2 = 2007\) : on montre \(3 \mid r\) et \(3 \mid b\), puis on encadre, d'où \(n = 69\) ou \(n = 84\).
Solutions

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

Solution

Réponse : \(n = 69\) et \(n = 84\).

Supposons que les nombres \(1, 2, \ldots, n\) soient coloriés en rouge et en bleu. Notons \(R\) et \(B\) les ensembles des nombres rouges et bleus respectivement ; soient \(\lvert R \rvert = r\) et \(\lvert B \rvert = b = n - r\). Un triplet \((x, y, z) \in S \times S \times S\) est dit monochrome si \(x\), \(y\), \(z\) ont la même couleur, et bicolore sinon. Un triplet \((x, y, z)\) est dit divisible si \(x + y + z\) est divisible par \(n\). Montrons qu'il y a exactement \(r^2 - rb + b^2\) triplets monochromes divisibles.

Pour tout couple \((x, y) \in S \times S\), il existe un unique \(z_{x,y} \in S\) tel que le triplet \((x, y, z_{x,y})\) soit divisible ; il y a donc exactement \(n^2\) triplets divisibles. De plus, si un triplet divisible \((x, y, z)\) est bicolore, alors parmi \(x\), \(y\), \(z\) il y a soit un nombre bleu et deux rouges, soit l'inverse. Dans les deux cas, exactement l'un des couples \((x, y)\), \((y, z)\) et \((z, x)\) appartient à l'ensemble \(R \times B\). On associe ce couple au triplet \((x, y, z)\).

Réciproquement, considérons un couple quelconque \((x, y) \in R \times B\), et posons \(z = z_{x,y}\). Comme \(x \neq y\), les triplets \((x, y, z)\), \((y, z, x)\) et \((z, x, y)\) sont distincts, et \((x, y)\) est associé à chacun d'eux. D'autre part, si \((x, y)\) est associé à un triplet, ce triplet est évidemment l'un de ceux mentionnés ci-dessus. Chaque couple de \(R \times B\) est donc associé exactement trois fois.

Ainsi, le nombre de triplets divisibles bicolores est le triple du nombre d'éléments de \(R \times B\), et le nombre de triplets divisibles monochromes est \(n^2 - 3rb = (r + b)^2 - 3rb = r^2 - rb + b^2\), comme annoncé.

Pour trouver toutes les valeurs de \(n\) pour lesquelles le coloriage voulu est possible, il faut donc trouver tous les \(n\) pour lesquels il existe une décomposition \(n = r + b\) avec \(r^2 - rb + b^2 = 2007\). Alors \(9 \mid r^2 - rb + b^2 = (r + b)^2 - 3rb\). Il s'ensuit successivement que \(3 \mid r + b\), \(3 \mid rb\), puis \(3 \mid r\), \(3 \mid b\). Posons \(r = 3s\), \(b = 3c\). On peut supposer \(s \geq c\). On a \(s^2 - sc + c^2 = 223\).

De plus,

\[892 = 4(s^2 - sc + c^2) = (2c - s)^2 + 3s^2 \geq 3s^2 \geq 3s^2 - 3c(s - c) = 3(s^2 - sc + c^2) = 669,\]

donc \(297 \geq s^2 \geq 223\) et \(17 \geq s \geq 15\). Si \(s = 15\), alors

\[c(15 - c) = c(s - c) = s^2 - (s^2 - sc + c^2) = 15^2 - 223 = 2,\]

ce qui est impossible pour un entier \(c\). De même, si \(s = 16\), alors \(c(16 - c) = 33\), ce qui est aussi impossible. Enfin, si \(s = 17\), alors \(c(17 - c) = 66\), et les solutions sont \(c = 6\) et \(c = 11\). Donc \((r, b) = (51, 18)\) ou \((r, b) = (51, 33)\), et les valeurs possibles de \(n\) sont \(n = 51 + 18 = 69\) et \(n = 51 + 33 = 84\). \(\blacksquare\)

Remarque

Une fois trouvée la formule du nombre de triplets monochromes divisibles, la solution peut se terminer de diverses façons. Celle présentée ici vise à réduire le nombre de cas à considérer.