Un problème de boules
Hier mon collègue Tahar Boulmezaoud m’a posé une belle devinette, juste au moment que je suis parti du bureau pour donner mes colles. Cela m’a bien occupé pendant le trajet et en plus pendant la colle 😉 Le problème peut se résumer ainsi:
Dix boules sont alignées devant nous pour que nous jouions le jeu suivant. Mon rôle est de marquer mentalement deux boules voisines et votre rôle est de deviner lesquelles. Pour cela vous avez droit à nommer deux sous-ensembles des dix boules, puis je vous dirai combien des mes boules marquées y sont contenues dans chacun. Pouvez vous y arriver?
Il y a neufs possibilités pour les deux boules voisines, et pour chaque sous-ensemble, il y a trois valeurs possibles (0, 1, 2), donc ça tombe bien, avec deux sous-ensemble on doit pouvoir distinguer 3 * 3 différentes combinaisons.
Il s’agit maintenant de trouver deux sous-ensembles qui permettent une bijection entre les neufs positions des deux boules voisines et les valeurs (0, 0), (0, 1), …, (2, 2) données par les comptes des deux ensembles.
Après tâtonnement, on peut trouver par exemple:
XOOOOXXXXO
XOOXXXXOOO
qui donnent comme comptes:
100012221
101222100
Et l’on peut vérifier que chacun des neuf couples possibles (lus verticalement) apparaissent bien.
Oui, bravo, avec vos sous-ensembles {1,6,7,8,9} et {1,4,5,6,7} ça fonctionne. En on voit que le même problème avec onze boules ou plus aurait une réponse négative.
Le « tâtonnement » a pris un certain temps chez moi. Par hasard j’ai tâtonné plusieurs fois vers une impasse, et à un certain moment j’étais presque convaincu que ça ne marcherait pas. Donc j’ai fait un graphe pour mieux voir et ainsi j’ai trouvé les sous-ensembles {3,4,5,9,10} et {5,7,8,9,10}. (Évidemment il y a beaucoup d’autres possibilités.)
Une interprétation élémentaire de la solution.
Enchaînons les boules dans l’ordre : 1-2-3-…-9-10. Déposons ensuite cette chaîne sur la figure formée par deux ensembles A et B non disjoints de manière à ce que aucun des quatre domaines de la figure ne contienne deux segments de chaîne.
Les solutions proposées correspondent ainsi à
1AB, 2, 3, 4B-A, 5B-A, 6AB, 7AB, 8A, 9A, 10.
1, 2, 3A-B, 4A-B, 5AB, 6, 7B-A, 8B-A, 9AB, 10AB
Une autre solution serait par exemple
1A-B, 2, 3, 4B-A, 5B-A, 6AB, 7AB, 8A-B, 9A-B, 10B
soit A = (1, 6, 7, 8, 9) et B = (4, 5, 6, 7, 10).
Complément au commentaire 3.
… et de manière à ce qu’il n’y ait pas deux segments joignant les mêmes domaines.
Bonjour,
Mathoman, pourriez-vous préciser votre méthode avec les graphes ? Je ne vois pas comment modéliser la situation.
Merci et bravo pour votre site.
Oui, j’ai retrouvé le brouillon. Dans quelques jours j’en ferai un scan pour le mettre en ligne ici.