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

La fausse pièce

Dans l’épisode 18 de la saison 2 de Brooklyn Nine-Nine (l’épisode Captain Peralta), capitaine Holt donne l’énigme suivante à son équipe au début de l’épisode,… et ne donne jamais la réponse. L’énigme est plus difficile qu’elle n’y paraît.

La fausse pièce (**)

Vous avez 12 pièces identiques et une balance à 2 plateaux. Une de ces pièces et fausse, et a un poids différents des 11 autres. Vous devez déterminez quelle est la fausse pièce, et devez dire si elle est plus lourde ou plus légère que les autres. Vous n’avez le droit qu’à 3 pesées.

Ce problème est connu en anglais sous le nom de The counterfeit coin. J’ai trouvé beaucoup de solutions plus ou moins exactes sur des forums, mais aucune solution satisfaisante (sauf ici, mais j’avoue ne pas avoir compris pourquoi ça marchait). J’ai fini par trouver un excellent article sur ce sujet, écrit par (le) Freeman Dyson.

Sa solution, élégante, et expliquée ci-dessous, permet de traiter la généralisation suivante :

La fausse pièce -version 2- (**)

Vous avez maintenant 13 pièces, dont une fausse. Il faut trouver la fausse en 3 pesées (vous n’avez plus besoin de dire si la fausse pièce est plus lourde ou plus légère).

Lire la suite

La montre

Il existe beaucoup de problèmes avec des montres, mais celui-ci est mon préféré. Il m’a été proposé par mon ami Fathi.

La montre aux deux aiguilles (*) La montre d’Alice a ses deux aiguilles de la même taille. Combien de fois par jour ne peut-elle pas savoir l’heure qu’il est ?

Il existe sans doute plusieurs façons de résoudre l’énigme. La solution suivante est géométrique.

Lire la suite

Mettre des biscuits dans une boîte

Ce problème m’a été posé par mon ami Ilia Smilga. Je le trouve très élégant, et le pose souvent à mes collègues.

Les biscuits dans la boîte

Peut-on ranger \({401}\) biscuits ronds de rayon 1 dans une boîte rectangulaire de taille \({4×400}\) ?

Évidemment, si on place les biscuits « 2 par 2 », on ne peut en mettre que 400. La question est donc de savoir s’il y a moyen de mieux disposer les biscuits.

Lire la suite

Les chocolats au carré

La saison des fêtes approche, et il est temps de revoir ses classiques. En l’occurrence, il s’agit des problèmes de maths avec les tablettes de chocolat. Le premier est très classique.

La tablette de chocolat (*)

André et Béatrice jouent avec une tablette de chocolat, composée de \({M \times N}\) carrés de chocolats. La tablette est posée sur la table. À tour de rôle, chaque joueur prend un bout de tablette sur la table, casse ce bout le long d’une rainure (soit horizontalement, soit verticalement), puis repose les (deux) bouts sur la table. Le joueur qui ne peut plus casser de bouts perd (et l’autre mange tout le chocolat). André commence. Peut-il gagner ?

Lire la suite

Une égalité intégrale

J’ai trouvé cette égalité dans un article de Vassilis Papanicolaou (Ewald’s Method Revisited: Rapidly Convergent Series Representations of Certain Green’s Functions), et je l’ai trouvée très étrange. Voici l’énoncé.

Une égalité intégrale

Soit \({f:\mathbb{R} \to \mathbb{R}}\) une fonction intégrable sur \({\mathbb{R}}\). Montrer que

\(\displaystyle \int_{\mathbb{R}} f(x) {\rm d} x = \int_{\mathbb{R}} f \left( x – \frac{1}{x} \right) {\rm d} x. \)

Lire la suite

Les enveloppes

Après une longue absence sur mon blog, j’ai décidé de changer de format. Je vais m’autoriser des articles plus courts, pour en faire plus souvent. Pour fêter ça, voici un de mes problèmes préférés. Il vient de mon ami Mathias, qui l’a trouvé sur le blog de David Madore.

Les enveloppes (***)

Un logicien arrive en enfer (normal, c’est un logicien !). Le diable, qui est toujours très joueur, lui tend 2 enveloppes, et lui dit :
«J’ai écrit un nombre réel dans chacune de ces deux enveloppes. Les deux nombres sont différents. Tu as le droit d’en ouvrir une et de regarder le nombre à l’intérieur. Tu dois ensuite me dire si tu penses que ce nombre est plus grand ou plus petit que l’autre. Si tu trouves correctement, tu gagnes, et tu pourras aller au paradis !»
Montrer qu’il existe une stratégie pour le logicien qui lui permette d’aller au paradis avec une probabilité strictement supérieure à \({1/2}\).

Lire la suite

Les chapeaux

Si les chapeaux sont un peu passés de mode, les problèmes des chapeaux restent des grands classiques.

Les chapeaux

Dans la prison des logiciens, on propose le jeu suivant à 100 prisonniers. On dispose les 100 prisonniers en file indienne, de sorte que chaque logicien peut voir les logiciens devant lui, mais pas ceux derrière lui. On place un chapeau noir ou blanc sur la tête de chacun d’entre eux, puis on demande tour à tour aux logiciens de deviner la couleur de leur chapeau. On commence par demander à celui de derrière (celui qui voit 99 chapeaux), puis on remonte pour finir avec celui de devant (celui qui n’en voit aucun). Chaque logicien entend toutes les réponses précédentes.

Si un logicien trouve la couleur de son chapeau correctement, il est libéré. S’il ne trouve pas, il est condamné à faire des mathématiques appliquées pour le restant de ses jours.

Les logiciens ont le droit de ce concerter avant le jeu et d’établir une stratégie. Quelle stratégie permet de minimiser le nombre de matheux appliqués ?

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