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

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

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

Le problème de Freudenthal

Ce problème m’a été posé initialement par mon père quand j’étais assez jeune, et je me souviens avoir noirci un grand nombre de feuilles pour trouver la solution (je n’avais pas encore appris à coder). J’ai appris récemment que ce problème s’appelle le problème de Freudenthal, et je vous invite à aller voir l’article de Jean-Paul Delahaye sur ce sujet.

La somme et le produit (***)

Alice tient le discours suivant : J’ai choisi deux nombres entiers \({X}\) et \({Y}\) tel que \({2 \le X \le Y \le 100}\). À toi Pauline, je vais te donner le produit des deux nombres \({P = X\times Y}\), et à toi Sophie, je vais te donner la somme des nombres \({S = X+Y}\). Voici la conversation qu’ont Pauline et Sophie.
Pauline : « Je ne peux pas déduire les deux nombres. »
Sophie : « Je le savais ! »
Pauline : « Dans ce cas, je connais les deux nombres. »
Sophie : « Alors moi aussi. »
Quels sont les deux nombres choisis par Alice ?

Lire la suite

Questions dénombrables

Commençons tout de suite la catégorie Problèmes par un nombre (au plus) dénombrable de problèmes sur les ensembles dénombrables.

Ce premier problème m’a été posé par mon ami Bastien, et fait parti de mes problèmes favoris. Voici l’énoncé.

Les 8 (*)

On appelle 8 une courbe fermée comportant exactement un point double. Peut-on mettre un nombre indénombrable de 8 dans le plan qui sont 2 à 2 disjoints ?

Lire la suite