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