Combinatoire extrême

Je suis allé il y a peu de temps au séminaire What is…? de l’ETHZ (Zurich), pour écouter l’exposé What is … Extremal Combinatorics? Si vous passez à Zurich, allez à ce séminaire, qui est le seul séminaire que je connais où sont offerts des bières et des pizzas. L’orateur était D. Korándi, et nous a proposé une série de problèmes en rapport avec la combinatoire extrême, pour qu’on comprenne ce qu’est ce nouveau sport de l’extrême.

Nous commençons par un problème classique avec des échiquiers.

L’échiquier

Quel est le nombre maximum de tours qu’on peut placer sur un échiquier \({8 \times 8}\) sans qu’aucune ne puisse en prendre une autre ? Même question avec des fous. Même question avec des cavaliers.

La même question avec des pions ou des rois n’est pas très intéressante, et la question avec les dames est un classique d’algorithmique, connu sous le nom du Problème des huit dames.

Cliquez ici pour voir la solution

J’ai beaucoup apprécié ce second problème et sa solution. Bonne chance !

Club-city (*)

Dans la petite ville de Club-city vivent 100 personnes. Chacune de ces personnes est membre de 0 ou plusieurs clubs (dont le club d’échecs, le club de maths, le club des détails qui ne font pas avancer l’énigme, etc.). Chaque club comprend un nombre impair de membres, et si on considère deux clubs différents quelconques, alors le nombre de membres communs à ces deux clubs est pair. Combien de clubs au maximum existe-t-il à Club-city ?

Cliquez ici pour voir la solution

Le dernier exercice est plus complexe, et nécessite un peu de théorie des graphes…

Distribution de nombres irrationnels (**)

Une professeur de maths sadique décide de donner un nombre irrationnel différent à chacun de ces N élèves. Pour chaque paire d’élèves, on dit que la paire est gagnante si la somme des deux nombres qu’ils ont est rationnelle. Quel est le nombre maximum de paires gagnantes dans la classe?

Cliquez ici pour voir la solution

C’est tout pour aujourd’hui. Encore merci à D. Korándi pour ce lot de jolis problèmes.

Lien pour marque-pages : Permaliens.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *