Small Fonts Default Fonts Large Fonts

Plus de 2500 récréations et problèmes mathématiques !

Ce site a été créé en souvenir de DIOPHANTE, mathématicien grec, qui nous a laissé de remarquables ouvrages d'arithmétique. L'objectif est de constituer une vaste bibliothèque de problèmes mathématiques avec les énoncés et les solutions classés par thèmes et selon leur niveau de difficulté et de proposer chaque mois plusieurs problèmes à la sagacité des lecteurs qui ont toute latitude pour envoyer leurs réponses.

Avertissement

Tous les problèmes sont identifiés par un niveau de difficulté :

Très facile

Facile

Moyen

Difficile

Très difficile

Variable

 

D'autre part, les problèmes se traitent généralement à la main et sont alors repérés par l'icône

 

Pour faciliter leur résolution, l'ordinateur peut être utile. Dans ce cas, vous verrez apparaître aussi cette icône

 

Quand l'ordinateur est indispensable, l'icône figure seule.

 

Pour avoir accès aux solutions de chaque problème, cliquez sur solution.

 

Les figures et les graphes ont été réalisés grâce au logiciel Declic.

Avertissement
Open/Close
E126. Les progressions interdites Imprimer Envoyer
E1. Suites logiques

calculator_edit.png  

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.


pdfPierre Henri Palmade,pdfPierre Jullien,pdfFrancesco Franzosi,pdfDaniel Collignon et pdfPaul 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 pdfJanusz 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:
 pdfPaul 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
 
RSS 2.0 Our site is valid CSS Our site is valid XHTML 1.0 Transitional