Une petite énigme

Nemor
Nemor
dans Combinatoire et Graphes
Bonjour à tous
Voici l'énoncé qui me pose souci.

Dix personnages sont assis autour d'une table ronde. On leur attribue à chacun, de façon aléatoire, un nombre entier de 1 à 10. Ils ont tous un nombre différent. Chacun additionne son numéro avec ceux de ses deux voisins.
Quelle est la somme minimale que celui obtenant le plus grand total est certain d'avoir ?

Mes réflexions sont les suivantes :
- Celui qui obtient le plus petit total ne peut pas être en-dessous de 6 ;
- Celui qui obtient le plus grand total ne peut pas être au-dessus de 27;
- La somme des résultats obtenus par chacun vaut $3 \times (1+2+\ldots+10)=165$.
Il s'agit donc d'additionner $10$ nombres entiers compris au sens large entre $6$ et $27$ dont la somme vaut $165$, et de trouver la valeur minimale que peut prendre le plus grand de ces dix nombres.

Toute aide est la bienvenue. Je vous remercie d'avance.

Réponses

  • bisam
    bisam 
    from itertools import permutations

m = 27
for p in permutations(range(1,10)):                          #on parcourt les permutations de 1,...,9
    l = [10] + list(p)                                       #on complète avec 10
    Msum3 = max(l[k-1]+l[k]+l[(k+1)%10] for k in range(10))  #on calcule le max des triplets de cette permutation
    if Msum3 < m:
        m = Msum3                                            #on met à jour le minimum
print(m)

    Mon esclave Python trouve 18.
  • PierreB
    PierreB
    Le min de la somme max est bien 18.
    Cet énoncé a été posé lors des Olympiades Académiques de 1ere en 2002 (exercice 2).

    Pierre.
  • bisam
    bisam
    Il est trivial de constater que la somme de toutes les sommes de triplets vaut $3\times (1+\cdots+10)=3\times 55 = 165$.
    Par conséquent, le minimum de ces sommes de triplets est supérieur à $165/10$ donc au minimum $17$.

    On arrive assez facilement à trouver des configurations dans lesquelles $18$ est atteint.
    Il reste juste à justifier que $17$ ne peut pas être un minimum.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Bonjour

    Les gros nombres sont 10, 9, 8 et 7. Ils doivent tous être distants de 3 positions. Sinon, ils participent à une somme qui dépasse 17. 4 nombres distants de 3 positions demandent 12 (=4*3) positions. Comme il n'y en a que 10, on sait que 17 est impossible.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • Nemor
    Nemor
    Bonsoir, merci à tous pour vos réponses qui m'ont bien aidé.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    L'honnêteté intellectuelle m'oblige à dire que je me suis trompé. C'est un peu plus compliqué. 9 et 10 doivent être distants de tous les éléments de {10,9,8,7}. D'où cette structure :
    _ _ G _ _ G _ _ 8 7 où $G \in \{10,9\}$

    Autour de 8 et 7, il y a forcément 1 et 2. Et aucune place n'est possible pour le 6, puisque tous les chiffres qui restent sont supérieurs ou égaux à 3. Au minimum, 6 + 3 + 9 = 18.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • bisam
    bisam
    Ton argument me va, PetitLutinMalicieux... et effectivement c'est tout bête.

    Je n'ose imaginer la prise de tête pour les correcteurs de ce genre d'épreuves, correcteurs qui doivent comprendre les élucubrations d'élèves de 1ère tentant d'expliquer quels cas sont impossibles !
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 5

Foysbiguine_equation +3 Invités