Dans mon tout premier article de ce blog, je vais vous embarquer pour une petite aventure mathématique. Aucune connaissance préalable ne sera requise! L’objectif principal est de vous montrer que les mathématiques sont avant tout une manière de penser, bien loin de se limiter à la manipulation de symboles énigmatiques.
Bien, allons-y pour notre aventure mathématique ! Imaginez que vous avez neuf pièces de monnaie, dont l’une est une contrefaçon , un peu plus légère que les autres. Votre mission est de découvrir quelle pièce est la faussaire en utilisant une bonne vieille balance à bascule. A votre avis, combien de pesées faudra-t-il pour déterminer quelle pièce est fausse?
Avant de continuer à lire, essayer de réfléchir quelques minutes par vous-mêmes:) Afin d’avoir un petit support visuel, Je vous propose cette image génerée par l’IA…
Comme vous l’avez remarqué, la formulation de ce problème est compréhensible par un enfant de 8-10 ans. La solution est également assez simple à comprendre mais pas facile à trouver! Commençons à s’en approcher pas à pas… En tant que première étape je vous propose une approche sans doute trop simpliste, mais qui peut servir du point de départ.
Round 1 : L’approche pas si maline
Au départ, vous pourriez penser, “Eh bien, soyons méticuleux !” Vous prenez la première pièce et la mettez d’un côté de la balance, puis vous mettez chacune des huit autres pièces de l’autre côté, une par une. Si la balance penche, voilà ! Vous avez trouvé la pièce plus légère. Cependant cette approche est lente et inefficace. Dans le pire des cas (si par malchance la balance penche que lors du dernier essai) vous devriez utiliser la balance à bascule huit fois, en comparant la première pièce à toutes les autres, une par une. Parlez d’une corvée !
A ce moment la vous avez déjà une petite intuition du processus de comparaison. Après avoir lu une première stratégie pas très optimale proposé par moi et peut-être une autre stratégie inventée par vous, je vous propose d’essayer d’améliorer la stratégie pour minimiser le nombre de pésées. Pour cela, il est toujours utile de se poser quelques questions: Quelles sont les faiblesses de la stratégie? Pourquoi est-elle plus lente et sous-optimale dans le pire des cas? Quelles sont les pistes pour améliorer ma stratégie? Je vous propose de vous arrêter pour quelques petites minutes de réflexion avant de continuer à lire.
Round 2 : Optimisation du processus
Alors, penchons-nous sur les inconvénients de cette première approche. Le hic, c’est que si, après la première pesée de deux pièces, la balance nous dit qu’elles ont le même poids, nous sommes certains que la faussaire se trouve parmi les sept pièces restantes. C’est une information utile, mais voici le problème : nous avons utilisé une pesée seulement pour réduire le nombre de pièces de neuf à sept. Cela est très inefficace!
Peut-être que dans notre excitation de jouer les détectives de pièces contrefaites, nous avons oublié une chose : nous ne sommes pas obligés de peser les pièces une par une ! C’est comme si on utilisait une balance pour mesurer le poids d’un paquet de frites en mettant les frites une par une, au lieu de simplement peser le paquet entier. C’est sûr, mais c’est un peu exagéré, non ?
Alors essayons de mettre plus de pièces de chaque côté de la balance lors du premier essai! Il est essentiel de noter cependant que cela n’a de sens de comparer que des groupes de tailles égales ; sinon, notre essai ne nous fournira aucune information utile. Pourrez-vous en utilisant ces conseils améliorer la stratégie?
En fait, il est important de réaliser que chaque pesée n’est rien de plus qu’une séparation de toutes les pièces en trois groupes : le Groupe 1 à gauche de la balance, le Groupe 2 à droite, et le Groupe 3 qui reste à l’écart sans être pesé. De plus, pour que la pesée ait un sens, il faut que le nombre de pieces dans le Groupe 1 soit égal au nombre de pieces dans le Groupe 2. Dans ce cas, si la balance penche lors de la pesée, comme on compare le même nombre de pieces, cela veut forcement dire que c’est à cause de la fausse piece plus légére que la balance a penché. Donc dans ce cas la fausse piece se trouve dans le groupe du côté plus léger de la balance. Si, au contraire, la balance est restée dans l’équilibre, cela les pieces suspectés d’être fausses ne sont que dans le Groupe 3, celui qui n’a pas été pesé.
Vous vous sentez un peu perdu? Eh bien, dans ce cas il est souvent utile de considérer un problème similaire mais un peu plus simple. Imaginez qu’au lieu de 9 pieces vous avez seulement 3 pieces et vous voulez determiner la fausse piece. En fait, dans ce cas une seule pesée suffit pour determiner la fausse piece! Vous prenez deux pièces et les placez de chaque côté de la balance. Deux scénarios se présentent :
- Si les deux côtés de la balance sont équilibrés, cela signifie que la pièce contrefaite est celle qui n’a pas été pesée.
- Si l’un des côtés de la balance penche, vous savez immédiatement que la pièce plus légère est la faussaire.
Pouvez-vous maintenant deviner combien de pesées faudra-t-il dans le cas de 9 pieces?
Round 3 : La Stratégie Optimale
Le premier pas de la stratégie optimale consiste en diviser nos 9 pieces en trois groupes de trois pièces chacun. Commencez par peser le Groupe 1 contre le Groupe 2. Si un côté penche, félicitations ! Cela veut dire que la fausse pièce se trouve dans le Groupe plus léger qui contient 3 pieces et vous avez réduit la liste des suspects à trois pièces en une seule pesée. Génial ! Mais que se passe-t-il si les deux côtés s’équilibrent ? Eh bien, cela signifie que la pièce contrefaite est dans le Groupe 3.
Maintenant, vous êtes dans la même situation que lorsque nous n’avions que trois pièces. Prenez les trois pièces du Groupe correspondant et appliquez la stratégie que nous avons déjà vu pour les trois pièces. En une seule pesée supplémentaire, vous découvrirez quelle pièce est la plus légère.
Bonus
Et si au début on avait pas 9 pieces mais 27? Ou même 81? Combien de pesées faudrait-il dans ces cas? Ecrivez vos réponses dans les commentaires! Et n’oubliez pas les explications!