Distribution Puzzle

Les casse-têtes de répartition (également appelés casse-têtes d’allocation sous contraintes ou casse-têtes « œufs et paniers ») mettent le joueur au défi de répartir un ensemble d’éléments entre plusieurs conteneurs tout en respectant plusieurs contraintes. Un casse-tête typique pourrait se présenter ainsi : « Répartissez les nombres de 1 à 9 en trois groupes de manière à ce que chaque groupe totalise 15, qu'aucun groupe ne contienne plus de 4 nombres et qu'aucun groupe ne contienne deux nombres consécutifs. » Ces casse-têtes mettent à l'épreuve à la fois les compétences arithmétiques et le raisonnement systématique, car le joueur doit trouver une répartition qui satisfasse toutes les conditions simultanément.

Règles

Les règles varient selon les casse-têtes, mais le principe général est le suivant :

1. Vous disposez d’un ensemble d’éléments (nombres, objets ou symboles) à répartir.
2. Vous disposez d’un ensemble de conteneurs (groupes, paniers, lignes, catégories).
3. Chaque élément doit être placé dans un seul et même conteneur.
4. Plusieurs contraintes doivent être respectées :

• Contraintes de quantité : chaque conteneur doit contenir un nombre précis d’éléments, ou un nombre compris entre un minimum et un maximum.
• Contraintes de somme : la somme des éléments d’un conteneur doit correspondre à une valeur cible.
• Contraintes d’exclusion : certains éléments ne peuvent pas se trouver dans le même conteneur.
• Contraintes d’inclusion : certains éléments doivent se trouver dans le même conteneur.
• Contraintes d’ordre : les éléments doivent être classés dans un ordre précis au sein des conteneurs.
• Contraintes de propriété : chaque conteneur doit contenir au moins un élément présentant une certaine propriété (par exemple, au moins un nombre impair).

Exemple de casse-tête

Répartissez les nombres de 1 à 8 en deux groupes de quatre, de telle sorte que :

• La somme de chaque groupe soit égale à 18
• Aucun groupe ne contienne deux nombres consécutifs
• Chaque groupe contienne exactement deux nombres pairs

Stratégies

• Commencez par l’arithmétique : calculez les sommes totales. Si l’on répartit les nombres de 1 à 9 en trois groupes de somme égale, la somme totale est de 45 ; chaque groupe doit donc totaliser 15.
• Appliquez d’abord la contrainte la plus stricte : identifiez la contrainte la plus restrictive et respectez-la en premier, puis vérifiez si les contraintes restantes peuvent encore être satisfaites.
• Placements obligatoires : certains éléments peuvent être contraints de figurer dans un groupe spécifique en raison des contraintes. Identifiez-les en premier.
• Paires complémentaires : dans les casse-têtes basés sur des sommes, identifiez les paires ou les groupes dont la somme donne des valeurs utiles.
• Procédé d’élimination : placez d’abord les éléments les plus volumineux ou les plus contraints, puis voyez où les éléments plus petits peuvent s’insérer.
• Essais systématiques : lorsque la déduction ne suffit pas, essayez un agencement, vérifiez toutes les contraintes et ajustez-le. Notez ce que vous avez déjà essayé pour éviter les répétitions.

Les casse-têtes de répartition comptent parmi les plus anciens types de jeux mathématiques. Les premiers exemples connus apparaissent dans d’anciens recueils de casse-têtes provenant de Chine, d’Inde et du Moyen-Orient. Le problème classique consistant à répartir des éléments en groupes tout en respectant certaines contraintes est présent dans les traditions mathématiques de nombreuses cultures.

L'un des casse-têtes de répartition historiques les plus célèbres est le « problème des cent volailles », attribué au mathématicien chinois Zhang Qiujian au Ve siècle après J.-C. : « Si les coqs coûtent 5 pièces chacun, les poules 3 pièces chacune et 3 poussins 1 pièce, comment acheter exactement 100 volailles pour exactement 100 pièces ? » Ce type de problème diophantien — qui consiste à trouver des solutions entières à des équations comportant des contraintes — est essentiellement un casse-tête de répartition.

En mathématiques occidentales, les casse-têtes de répartition ont été popularisés par des auteurs de mathématiques ludiques tels que Henry Dudeney et Sam Loyd au début du XXe siècle. Leurs recueils de casse-têtes et leurs chroniques dans les journaux proposaient de nombreux problèmes portant sur la division de groupes, la répartition de poids et l’allocation de ressources sous contraintes. La rubrique « Mathematical Games » de Martin Gardner dans Scientific American (1956-1981) a contribué à diffuser ces casse-têtes auprès d’un large public.

Les casse-têtes de répartition modernes apparaissent dans les magazines de casse-têtes logiques, les supports pédagogiques de mathématiques et les concours de casse-têtes. Ils sont étroitement liés aux domaines mathématiques de la combinatoire, de la programmation en nombres entiers et de la satisfaction de contraintes. En informatique, les casse-têtes de répartition sont utilisés pour enseigner les algorithmes de retour en arrière, la propagation des contraintes et la résolution par satisfiabilité (SAT). Ces casse-têtes ont également trouvé des applications dans les tests standardisés et les évaluations d'intelligence, où ils permettent de mesurer le raisonnement systématique et la capacité à gérer plusieurs contraintes simultanées.