Olympiades · Épreuve nationale · 27 mars 2018 · Série S
Un ensemble \(S\) de rationnels est un ensemble arithmétique (EA) si pour tout couple \((a,b)\) d'éléments distincts de \(S\), il existe \(c\in S\) tel que l'un des trois nombres \(a,b,c\) soit la moyenne arithmétique des deux autres. On cherche tous les entiers \(n>0\) pour lesquels il existe un EA de \(n\) éléments.
1a. \(\{0,1,2\}\), \(\{0,1,2,3\}\), \(\{0,1,2,4\}\) sont-ils des EA ? 1b. Montrer qu'il n'existe pas d'EA à 2 éléments ; que dire des singletons ? 1c. Donner un EA à 5 éléments, inclus dans \([0,2]\), contenant \(0,1,2\).
2a. Quels rationnels envisager pour tester si \((a,b)\) ne fait pas échec à la définition ? 2b-c. Écrire (et optimiser) un algorithme TesterEA.
3. Si \(S\) est un EA de \(n\) éléments, de plus grand \(M\) et de plus petit \(m\), montrer que \(S'=\left\{\dfrac{2(a-m)}{M-m}, a\in S\right\}\) est un EA de \(n\) éléments inclus dans \([0,2]\) et contenant \(0,1,2\).
4. Si \(S\subset[0,2]\) est un EA contenant \(0\) et \(2\), montrer que si \(0 5. Montrer que \(S\) ne contient aucun élément dans \(]0,\frac23[\) ni dans \(]\frac23,1[\), et en déduire que \(n\le5\). 6. Conclure : quels sont les entiers \(n\) pour lesquels il existe un EA à \(n\) éléments ? 1b. Pour 2 éléments \(a,b\), il faut \(\frac{a+a}2=b\) ou \(\frac{a+b}2=a\) : les deux forcent \(a=b\). 2a. Si \(a\) est la moyenne de \(b,c\) alors \(c=2a-b\) ; par symétrie il faut aussi tester \(2b-a\). 4. Utiliser la contrapositive : montrer que les nombres qui ne peuvent pas compléter la paire \(\{0,x\}\) ou \(\{2,x\}\) forcent l'appartenance du nombre restant à \(S\) (raisonnement par élimination). 5. Itérer l'argument de la question 4 : un élément proche de 0 (ou de 1) dans \(S\) en génère un autre encore plus proche, ce qui est impossible dans un ensemble fini — bornant ainsi le nombre d'éléments possibles. 1a. \(\{0,1,2\}\) est un EA (\(1\) est la moyenne de \(0\) et \(2\)). \(\{0,1,2,3\}\) n'est pas un EA (la paire \((0,3)\) n'a pas de complément adéquat). \(\{0,1,2,4\}\) non plus (paire \((1,4)\)). 1b. Pour \(\{a,b\}\), il faudrait \(a=b\) : impossible avec 2 éléments distincts. Les singletons \(\{a\}\) sont des EA (la condition est vide, ou triviale avec \(c=a\)). 1c. L'ensemble \(\left\{0,\frac23,1,\frac43,2\right\}\) convient : chaque élément est accompagné, dans un triplet moyenne, des quatre autres. 2a. Si \(a\) est la moyenne de \(b,c\), alors \(c=2a-b\) ; par symétrie des rôles, il faut tester \((a+b)/2\), \(2a-b\) et \(2b-a\). 2b. Fonction 2c. Version optimisée : ne parcourir que \(i 3. Les rapports \(\frac{2(a-m)}{M-m}\) sont bien dans \([0,2]\) car \(0\le a-m\le M-m\) ; \(0,1,2\) s'obtiennent pour \(a=m,\frac{M+m}2,M\) (avec \(\frac{M+m}2\in S\) car \(m,M\) ne peuvent être moyennes l'un de l'autre dans un EA). La transformation étant affine, elle conserve la propriété d'être un EA. 4. Si \(0 5. Si \(S\) contient \(a_1\in\left]0,\frac23\right[\), la question 4 donne \(\frac{a_1+2}2\in S\) puis (ce nombre étant dans \(]1,2[\)) \(\frac{a_1+2}4\in S\), qui est encore dans \(\left]0,\frac23\right[\) et strictement supérieur à \(a_1\) : itéré indéfiniment, cela produit une infinité d'éléments, absurde pour un ensemble fini. Donc \(S\) ne contient aucun élément \(<\frac23\). Un raisonnement symétrique élimine \(\left]\frac23,1\right[\). Il en résulte que le seul élément possible entre 0 et 1 est \(\frac23\), et par symétrie \(\frac43\) entre 1 et 2 : \(n\le5\). 6. Seuls \(n=1\), \(n=3\) et \(n=5\) admettent un ensemble arithmétique.TesterEA : pour chaque couple \((i,j)\), si aucun de \((S_i+S_j)/2\), \(2S_i-S_j\), \(2S_j-S_i\) n'appartient à \(S\), renvoyer Faux. Coût : au plus \(3n^2\) tests.