Bonjour,

Notre prof d'algèbre nous a donné un challenge, voici l'énoncé :

Dans la suite, je suppose qu'un dessin est un element de l'ensemble {1, 2, ..., M}, et qu'une carte est un element de l'ensemble des sous-ensembles de {1, 2, ..., M}  de cardinalité impair.

J'ai d'abord essayé avec des petites valeurs de M (M=1, 2, 3), et à chaque fois, je trouve que le nombre maximum de carte de jeu est
M.

J'ai développé un programme en python qui calcule pour une entrée M, le nombre maximum de cartes qui respectent les conditions. je trouve que : pour tout , le nombre max de cartes est M. Comme la complexité de l'algorithme est mauvaise, je n'ai pas pu tester pour d'autres valeurs de M.

J'ai par la suite essayé de modéliser le problème en utlisant un graphe : les sommets du graphe sont les cartes (des cartes contenant un nombre impair de dessins), il y a une arrête entre deux sommets lorsque ces deux sommets partagent un nombre pair de dessins. Ainsi, c sommets du graphe forment un jeu de carte si et seulement si il forment une clique (un sous-graphe complet). Le problème revient donc à trouver la taille de la plus grande clique du graphe. C'est là que je me suis arrêté, j'essaies de montrer qu'il ne peux pas exister une clique de taille > M, mais je sais pas comment faire.

Que pensez-vous de mon analyse ? Pensez-vous que je suis sur la bonne voie ? Pouvez-vous me suggérer d'autres pistes ?

Merci d'avance