Solution au problème de septembre 2012

Le problème:
	$N$ est un ensemble de nombres compris entre 1 et 15 (inclusivement) tel q'aucun produit de trois nombres distincts de $N$ n'est un carré parfait. Par exemple, si $N$ contient 2 et 6, alors il ne contient pas 12, parce que $2\cdot 6 \cdot 12 = 144$, un carré parfait. Quelle est la cardinalité maximale possible de $N$?

$N$ contient au plus dix nombres.

Nous avons reçu les solutions correctes de

Ce problème a presque été sélectionné pour la 35-ième Olympiade Internationale de Mathématiques de Hong Kong en 1994. Il admet une jolie solution courte, mais qui peut prendre du temps à trouver, alors que plusieurs pistes qui semblent prometteuses mènent à des dédales. Cet aspect le rend peut-être inadéquat pour une olympiade mathématique.

Nous reproduisons la solution de Benoît Humbert.

"Appelons « trio carré » un ensemble de trois nombres dont le produit est un carré. Appelons $n$ le plus grand cardinal possible de $N$.

Réponse : $n = 10$

Démonstration:

Montrons que $n \leq 10$ :

Les quatre trios suivants sont disjoints et carrés : $\{1, 4, 9\}, \{7, 8, 14\}, \{3, 5, 15\}, \{2, 6, 12\}$. Il est donc nécessaire d’écarter l’un des nombres contenus dans chacun de ces trios. On a donc $n \leq 11$. Supposons que $n = 11$, c’est-à-dire qu’on puisse trouver un ensemble convenable en éliminant seulement un nombre dans chacun des trios ci-dessus. En particulier, $10$ est conservé.

Il faut éliminer $2$ ou $5$, car $2 \cdot 5 \cdot 10 = 10^2$.

Il faut éliminer $6$ ou $15$, car $6 \cdot 15 \cdot 10 = 30^2$.

Comme on n’élimine qu’un seul nombre par trio, il faut donc soit éliminer $2$ et $15$, soit $5$ et $6$. Dans les deux cas, $3$ et $12$ sont conservés. Or ces deux nombres forment un trio carré avec n’importe lequel des nombres restants dans le trio $\{1, 4, 9\}$. Contradiction !

Donc $n \leq 10$.

Montrons que $n \geq 10$ :

Éliminons $2, 8, 9, 12$ et $15$, et montrons que l’ensemble $N$ suivant, de cardinal $10$, ne contient aucun trio carré :

$\{1, 3, 4, 5, 6, 7, 10, 11, 13, 14\}$.

Un trio carré ne peut contenir ni $11$, ni $13$, qui sont premiers et n’apparaissent pas dans la décomposition des autres nombres.

Un trio carré contenant $7$ ou $14$ doit obligatoirement contenir l’autre pour que le facteur premier $7$ soit présent deux fois. Le troisième nombre devrait alors être $2$ ou $8$, mais ils sont exclus de $N$. Un trio carré ne peut donc contenir ni $7$, ni $14$.

De même, il ne peut contenir ni $5$, ni $10$.

De même, il ne peut contenir ni $3$, ni $6$.

Il ne reste plus que deux nombres, $1$ et $4$, qui ne peuvent former un trio.

Conclusion : $n = 10$."