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?

6 réponses
  1. FelixCQ
    FelixCQ dit :

    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.

    Répondre
  2. MathOMan
    MathOMan dit :

    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.)

    Répondre
  3. DanielPM
    DanielPM dit :

    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).

    Répondre
  4. DanielPM
    DanielPM dit :

    Complément au commentaire 3.
    … et de manière à ce qu’il n’y ait pas deux segments joignant les mêmes domaines.

    Répondre
  5. chris
    chris dit :

    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.

    Répondre

Laisser un commentaire

Rejoindre la discussion?
N’hésitez pas à contribuer !

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *