Bonjour,

une question que je me pose lié au PMU :

Etant donnés 6 numéros fixés (disons 1,2,3,4,5 et 6 pour simplifier). Combien faut-il au minimum écrire d'ensemble à 3 éléments parmi les 6 numéros possibles pour être certain que n'importe quelle paire formée de deux numéros distincts parmi les 6 fixés soit contenue dans au moins un de ces ensembles?

Par exemple si on écrit :
{1;2;3}
{1,4,5}
{1,6,2}
{2,4,5}
{3,4,5}
{3,6,4}
{6,5,1}

Alors si on prend n'importe quelle paire d'éléments, par exemple {2,5} ou {1,6} alors il existe au moins un des ensembles précédents la contenant (ici c'est {2,4,5} et {1,6,2}).

J'ai donc trouvé que ça marche avec 7 ensembles mais je ne sais pas prouver qu'on ne peut pas faire mieux.

Je m'intéresse aussi à une généralisation : Combien de parties à p éléments parmi n fixés doit on au minimum avoir pour être certain que toute partie à q éléments (q < p) soit contenue dans au moins l'une d'entre elles? Et si on plus on veut que chaque paire ne soit contenue que dans un seul ensemble? (dans mon exemple, {1,6} est contenue dans deux ensembles, {1;6;2} et {6;5;1})

Pas d'idées?

J'ai posé la question à un collègue qui pourra peut être m'éclairer, plus d'infos demain.

Merci pour cette réponse intéressante.

J'aime bien l'argument de géométrie projective, c'est à peu près à partir de ça que j'ai extrait la solution à 7 triplets que j'ai donné dans mon dernier post. J'arrivais pas à générer de solution avec 6 triplets avec donc j'en ai déduis que c'était impossible.

Force du tâtonnement, j'ai fini par trouver une solution avec 6 :
{1,2,3}
{1,4,6}
{2,4,6}
{3,5,4}
{2,5,1}
{3,6,5}

Sauf erreur, ça fonctionne. Du coup, conjecture pour la généralisation : Pour un ensemble à n éléments et des triplets dans lesquels on doit retrouver toutes les paires, en faudrait-il pas exactement n triplets? (je sais que c'est grossier de faire une conjecture sur un seul résultat, mais j'ai aussi trouvé une solution avec 7 triplets dans le cas n=7)