Les deux piles

Ce problème assez surprenant m’a été posé par Amic. On peut le trouver sur affairedelogique.com.

Les deux piles (*)

Alice possède \({2N}\) cartes, portant les numéros de 1 à \({2N}\). Elle mélange les cartes, et en fait deux piles A et B de \({N}\) cartes chacune. Elle range la pile A dans l’ordre croissant, et la pile B dans l’ordre décroissant. Enfin, elle prend la première carte de chaque pile, calcule la valeur absolue de leur différence, et range les deux cartes. Elle fait de même avec toutes les cartes suivantes, et additionne tous les résultats. Quelle est la somme totale ?

Et non, la somme totale ne dépend du mélange initial !

Lire la suite

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.

Lire la suite