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
G233. Les suites universelles Imprimer Envoyer
G2. Combinatoire - Dénombrements
calculator_edit.png  
Soit un entier naturel n. On dit que S(n,k), suite de k nombres entiers naturels (avec k > n), est universelle d’ordre n si on peut obtenir n’importe quelle des n ! permutations des entiers {1,2,….,n} en supprimant k – n de ses termes. Par exemple, la suite de 3 termes (1,2,1) est universelle d’ordre 2 car on peut obtenir les 2 permutations (1,2) et (2,1) en supprimant respectivement le troisième chiffre qui est égal à 1, ce qui donne (1,2,*) et le premier chiffre lui aussi égal à 1, ce qui donne (*,2,1). A l’inverse (1,2,2) ne l’est pas car il est impossible d’obtenir (2,1).
On désigne par L(n) la longueur de la suite universelle d’ordre n la plus courte possible. On a par exemple L(2) = 3.
1) Démontrez que L(3) = 7 et L(4) = 12.
2) A partir de suites universelles S(3,7) et S(4,12) d’ordres 3 et 4 et de longueur minimale, donnez et justifiez un mode de construction de suites universelles d’ordre 5, 6, 7,….n dont la longueur vous paraît minimale.
Pour les plus audacieux et les plus courageux qui ont trouvé une suite universelle de longueur 4 028 052 pour n = 2008, il ne leur reste plus qu’à démontrer que L(2008) = 4 028 052 (difficulté : *******).

Source : d’après Olympiade 1976 de mathématiques en URSS – Problème n°12


Pierre Henri Palmade, Jean Nicot et Fabien Gigante ont résolu le problème.

Jean Moreau de Saint Martin fait remarquer que le problème proposé aux olympiades soviétiques de 1976 trouve sa solution dans l'ouvrage Mégamath de Pierre Bornsztein (éditions Vuibert).

Jean Drabbe donne les références d'un article dans lequel est proposée une deuxième solution possible du même problème.

 

 
RSS 2.0 Our site is valid CSS Our site is valid XHTML 1.0 Transitional