Une petite énigme

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.



Edité 2 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.

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.

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.

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.

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.

Bonsoir, merci à tous pour vos réponses qui m'ont bien aidé.

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.

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 !

Liste des forums - Statistiques du forum

Total
Discussions: 148 744, Messages: 1 499 660, Utilisateurs: 28 309.
Notre dernier utilisateur inscrit erkl.

---

Ce forum
Discussions: 886, Messages: 7 507.