|
 
Q1 Sait-on construire une suite de 2016 entiers distincts compris entre 1 et 100 000 tels que trois quelconques d’entre eux ne forment jamais une progression arithmétique?
Q2 Même question que Q1 avec 2050 entiers naturels distincts.
 Pierre Henri Palmade,Pierre Jullien,Francesco Franzosi,Daniel Collignon et Paul Voyer ont résolu la question Q1.
Le niveau de difficulté du problème initialement affiché avec 3 étoiles a été porté à 5 étoiles. En effet la question Q2 se révéle beaucoup plus complexe que ne l'avait imaginé le rédacteur de l'énoncé du problème. A ce jour, on ne connaît pas de bonne réponse à Q2.La question Q1 a été traitée selon deux approches :- la première utilise un algorithme dit "glouton" qui consiste, en partant des deux premiers termes choisis au départ,à écrire le plus petit entier qui n’est pas en progression arithmétique avec deux quelconques termes précédents. Ainsi avec les entiers 1 et 2, on obtient la suite 1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37...répertoriée comme séquence de Szekeres dans l'OEIS (http://oeis.org/A003278). Le 2016ième terme vaut 88331 qui est bien inférieur à 100000. A partir des entiers 1 et 3, on a la séquence 1, 3, 4, 6, 10, 12, 13, 15, 28, 30, 31, 33, 37, 39... qui est dans l'OEIS à l'adresse http://oeis.org/A004793.La deuxième approche consiste à écrire la suite des entiers croissants dont la représentation en base 3 ne contient que des 0 et des 1, les 2 étant donc exclus et qui a au plus 11 chiffres (211 - 1 > 2016). D'où la séquence 1,3,4,9,10,12,13,27,28,.....dont la représentation en base 3 est 1,10,11,100,101,...,c'est à dire la suite des entiers naturels en base 2.Voir sur l'OEIS http://oeis.org/A005836. Le 2016ième terme vaut 88452 qui est aussi inférieur à 100000. On vérifie bien que cette suite ne contient aucune progression arithmétique de trois termes ou plus.En effet, soient x,y,z trois termes de la suite tels que x < y < z. Si on a x + z = 2y, le nombre 2y (en base 3) ne contient que des 0 et des 2.Dès lors les chiffres de même rang de x et z (en base 3) doivent coïncider. Il en résulte que x =y = z. Contradiction. On constate que dans l'une ou l'autre des séquences A003278,A004793 et A005836 le 2050-ième terme (respectivement 177149,177149 et 177150) dépasse largement 100000 et on est tenté de retenir l'impossibilité de construire une suite de 2050 entiers naturels distincts tels que trois quelconques d’entre eux ne forment jamais une progression arithmétique.
Mais rien ne dit qu'il n'existe pas un algorithme plus performant que les algorithmes "gloutons". L'article de Janusz Dybizbanski montre que pour n = 100 (au lieu de 100000) il existe un algorithme qui donne une suite “ad hoc” de 27 termes alors que l'algorithme glouton (que l'on croit être optimal) donne seulement 24 termes : 1,2,4,5,....,95.Il est donc possible qu’avec n = 10000, un bon algorithme existe pour donner un 2050-ième terme < 100000. La difficulté majeure est qu’aujourd’hui aucun ordinateur n’a été capable de le donner.
Nota:
Paul Erdös et des mathématiciens de l'école hongroise (Szekeres,Szemeredi,Turan,..) ont abondamment étudié les suites d'entiers qui ne contiennent jamais trois entiers en progression arithmétique.
1, 3, 4, 6, 10, 12, 13, 15, 28, 30, 31, 33, 37, 39
|
Problèmes par thèmes 
Très facile
Facile
Moyen
Difficile
Variable
