sept 292011
 

Une nouvelle énigme assez corsée qui devrait plaire aux amateurs de la théorie des jeux, inspirée cette fois d'un exercice posé par le professeur de maths d'un des élèves de l'un de mes confrères professeur particulier.

Notez qu'il s'agit d'un exercice de niveau terminale S, donc on ne peut utiliser que les notions vues à ce niveau du programme.

Voici l'énoncé :

Dix personnes sont autour d'une table. Dix jetons portant les numéros de 1 à 10 sont distribués au hasard à ces 10 personnes. Chaque joueur gagne une somme égale (en €) au total des nombres inscrits sur son jeton ainsi que sur ceux de ses voisins de gauche et de droite.

Ainsi peut-on affirmer : "Au moins une des dix personnes aura un gain au moins égal à M€".

Quel est le plus grand nombre que l'on peut mettre à la place de M ?

A vos neuronnes !

N.B. : l'énoncé est un peu alambiqué. Il s'agit de trouver le plus petit gain maximal qu'on est certain d'obtenir quelle que soit la configuration. Il faut donc trouver le min du max...


- Indice 1 (cliquer pour développer)
Démontrez que le gain moyen par joueur est égal à 16,50 €.
- Indice 2 (cliquer pour développer)
Commme il s'agit de trouver quel est le gain minimum M, parmi les gains maximaux possibles, on peut facilement éliminer tous les gains inférieurs à la moyenne...
- Indice 3 (cliquer pour développer)
Démontrer par l'absurde que l'hypothèse M=17 est impossible.

- Solution (cliquer pour développer)
Note : la résolution de cette énigme est inspirée fortement d'une solution proposée par @cours2maths (téléchargeable à cette adresse : blog.cours2maths.com) à l'aide des contributions de @courmpc et de moi-même.
Pour ne pas rebuter trop de monde, j'ai choisi de passer le plus possible par le français en évitant les formules.
La résolution de cette énigme se fera en deux étapes :

  1. Calcul du gain moyen par joueur
  2. Recherche du gain minimal M parmi les gains maximaux possibles.
Etape 1. Gain moyen par joueur.
Les numéros tirés par les joueurs sont tous distincts 2 à 2, mais les gains peuvent être identiques.

Notons S la somme des gains de chaque joueur.
Puisque le gain de chaque joueur est la somme de trois entiers distincts pris entre 1 et 10, effectuer la somme des gains des joueurs est équivalent à calculer trois fois la somme des entiers de 1 à 10 (l'addition est associative. C'est évident, mais ça va mieux en le disant). Cette somme étant égale à 55 (n(n+1)/2 avec n=10), la somme des gains des joueurs est de 3*55=165 :

S=165.

Notons \bar{g} le gain moyen par joueur.
Comme il y a 10 joueurs et que les configurations sont toutes équiprobables, le gain moyen est \bar{g}=S/10 :

\bar{g}=16,5.

Etape 2. Recherche du plus petit des gains maximums.

2.1 Amplitude des gains.

Le plus petit gain pour un joueur donné est de 6 €. En effet, la somme minimale de trois chiffres distincts choisis entre 1 et 10 est 1+2+3=6.
Le plus grand gain pour un joueur donné est de 27 €. En effet, la somme maximale de trois chiffres distincts choisis entre 1 et 10 est 8+9+10=27.
Donc les gains de tous les joueurs sont des entiers compris entre 6 et 27.

Le nombre M recherché, qui représente le plus petit des gains maximaux, est donc un entier compris entre 6 et 27.

2.2 Peut-on avoir M\leq16,5 ?
Dans toute série statistique, le maximum est toujours supérieur ou égal à la moyenne. M en tant que gain maximum est donc nécessairement supérieur ou égal à \bar{g}.
Par conséquent, M ne peut pas être inférieur à 16,5.

Donc M est au moins égal à 17.

2.3 Peut-on avoir M=17 ?

Raisonnons par l'absurde en supposant qu'il existe une configuration dans laquelle on a exactement n gains de 17 €. Nous aurons donc 10-n gains inférieurs ou égaux à 16 € (80=16x5). Notons S' la somme des gains inférieurs ou égaux à 16 €.
Les deux relations suivantes doivent alors être vérifiées :

17n+S'=165, \quad (I)
S'\leq 16(10-n). \quad (II)

De (I) on déduit S'=165-17n. En injectant ce résultat dans la seconde inégalité (II), on obtient après quelques lignes de calcul élémentaire n\geq 5.

Conséquence : s'il existe une configuration dans laquelle on a un gain maximum à 17€, alors il y a nécessairement au moins 5 gains à 17 €.

Considérons pour l'instant le cas n=5.
La somme des 5 autres gains est alors de 80 (S'=165-17\times 5=80). Comme ce sont des entiers inférieurs ou égaux à 16€, ils sont tous égaux à 16 €. Nous avons donc 5 gains à 17 € et 5 gains à 16 €.

Numérotons avec i variant de 1 à 10 les joueurs dans leur ordre consécutif autour de la table. Par ailleurs, notons N_i le numéro figurant sur le jeton tiré par le joueur i et g_i le gain du joueur i.

Montrons que, sous les hypothèses courantes (à savoir M=17 et n=5) deux joueurs successifs ne peuvent pas avoir le même gain.
Considérons arbitrairement les joueurs 5 et 6 (le raisonnement qui suit tient pour tous couple de joueurs consécutifs mais raisonner sur i et i+1 complique la démonstration car les chiffres 10 et 1 sont consécutifs dans l'ordre de la table).
On a,
g_5=N_4+N_5+N_6, \quad \text{et} \quad g_6=N_5+N_6+N_7.
De là on voit que g_5=g_6 implique N_4=N_7 ce qui est impossible puisque les numéros des jetons sont tous distincts. Donc deux joueurs voisins ne peuvent pas avoir le même gain (ce raisonnement tient aussi pour n\geq 5).

La seule distribution possible est donc une alternance de gain à 16 € et 17 €.
Posons arbitrairement la répartition suivante :

g_1=N_{10}+N_1+N_2=17 \quad (1),
g_2=N_1+N_2+N_3=16 \quad (2),
g_3=N_2+N_3+N_4=17 \quad (3),
g_4=N_3+N_4+N_5=16 \quad (4),
g_5=N_4+N_5+N_6=17 \quad (5),
etc.

Alors, (1)-(2)+(4)-(5) donne :

N_{10}+N_1+N_2-N_1-N_2-N_3+N_3+N_4+N_5-N_4-N_5-N_6=17-16+16-17,
ou encore :
N_{10}-N_6=0,
ce qui est impossible puisque les jetons sont tous différents.

Donc la seule possibilité restante est que n soit supérieur à 5. Or, dans ce cas, on aura nécessairement deux joueurs consécutifs avec un gain égal à 17 €, ce qui, nous l'avons montré plus haut, est impossible.

Nous avons envisagé tous les cas pouvant donner un plus petit gain maximal égal à 17 € et avons obtenu à chaque fois un résultat absurde.

L'hypothèse M=17 est donc exclue.

2.3 Peut-on avoir M=18 ?

@courmpc a fait la proposition de répartition suivante donnant un gain maximum égal à 18 €.

Conclusion : M=18.

Au moins une des 10 personnes aura un gain au moins égal à 18 €.

 Posted by on 29 septembre 2011
  • http://goutte-de-science.net/blog Florian

    Alors, amis lecteurs, on sèche ?

  • http://goutte-de-science.net/blog Florian Longueteau

    Ci-dessus (dans l'article), un premier indice pour vous aider.

  • http://goutte-de-science.net/blog Florian Longueteau

    Un deuxième indice dans l'article.

  • Zevenerable

    Je ne comprends pas si le problème est de trouver le plus grand gain qu'il est certain de voir apparaitre à chaque fois, ou bien le plus petit.

  • http://goutte-de-science.net/blog Florian Longueteau

    @88305ae275d2cdcf4a34e1f0ebdb6abd:disqus Dans chaque configuration, il y a un gain maximal. Parmi tous ces gains maximaux possibles, le but est de trouver le plus petit, c'est à dire celui qu'on est certain d'obtenir, quelle que soit la configuration. 

    • http://goutte-de-science.net/blog Florian Longueteau

      L'énoncé est en effet un peu alambiqué. Reformulation "il s'agit de trouver un minorant des gains maximaux présents dans chaque distribution de jetons."

  • http://goutte-de-science.net/blog Florian Longueteau

    Un nouvel indice qui devrait permettre de conclure.

  • http://goutte-de-science.net/blog Florian Longueteau

    Et voilà la solution.
    Si vous avez des commentaires ou une solution plus simple. N'hésitez pas à en faire part aux lecteurs.

  • Remipeyre

    En remplaçant 10 par un nombre N quelconque, je suis parvenu à démontrer que la gain maximal minimal sera de (3N+6)/2 pour N pair supérieur ou égal à 8 et de (3N+7)/2 pour N impair supérieur ou égal à 17. Pour N = 1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 15, le réponses sont respectivement 3, 5, 6, 9, 10, 11, 14, 16, 20, 23, 25. Mais la preuve en général est beaucoup plus compliquée ! Voir aussi mon commentaire sur IdM.

    • http://goutte-de-science.net/blog Florian Longueteau

      Je viens de voir votre réponse sir IdM effectivement : http://images.math.cnrs.fr/spip.php?page=forum&id_article=1062.

      Première remarque, j'aurai pu effectivement d'emblée dire que deux jours adjacents n'ont jamais les mêmes gains, puisque la différence de ceux-ci (numérotés disons i et (i+1)) est N_(i+1)-N_(i-1) qui est toujours non nulle puisque les numéros sont tous distincts. Je vais simplifier la solution en intégrant cet élément.

      Votre seconde remarque, concernant la majoration du max est très bien vue.

      Bientôt une preuve générale ? :)

      • Remi Peyre

        Ayé, j'ai rédigé une petite preuve... Par contre, ça reste très parcellaire, et je suis sûr que mon texte est truffé de coquilles vu que je l'ai fini assez tard :)

        Vous trouverez ma solution en ligne à l'adresse
        http://www.normalesup.org/~rpeyre/perso/rentables/rentables.pdf ,
        et comme mon texte est très largement améliorable, je vous en laisse aussi le code-source si vous voulez vous en servir :
        http://www.normalesup.org/~rpeyre/perso/rentables/rentables.tex .

        Bonne soirée !

        • http://goutte-de-science.net/blog Florian Longueteau

          Merci Rémi pour votre généralisation. Je laisse le soin aux lecteurs motivés de la décortiquer, vous dépasser de loin mes compétences, je le crains :)

  • Claude Morin2

    Il y a une façon très rapide de montrer que le maximum est au moins égal à 18. Mettons à part la personne qui a le numéro 1. Les autres peuvent être réparties en trois groupes de 3 et chaque groupe de 3 a un total inférieur ou égal à M.
    On a donc 2+3+...+10=54 qui est inférieur ou égal à 3M et par suite M est au moins égal à 18.
    Avec 18=10+6+2=9+5+4=8+7+3 il n'est pas difficile de trouver une solution avec M=18.

    • http://goutte-de-science.net/blog Florian Longueteau

      Simple et élégant. Bravo :)

  • Nobody

    Je suggère une réponse : Le google 10^10 ie le rapport de 1à 10 qui est inscrit dans les mains de l'homme mais que l'on recherche depuis des millénaire parce que nous craignons de remonter sur l'arbre un jour et du coup nous renions la réalité.. le google n'est pas dans la mains mais dans les deux mains (c'est ce qu'on appelle le problème du millénaire en mathématiques .. le boson de Higgs en physique des particules.. la matière noire en physique de la relativité générale.. et la loi de la connerie humaine dans le jargon le plus brut dit "bon sens paysans".. ->pour le prouver il faut et il suffit que vous jouillez avec votre curiosité et vos mains assez longtemps, en immitant les gestes de vos super héros préféré (pour les puristes, initiez vous à l'art millénaire du kung-fu et vous comprendrez).. Si cette idée vous parrait infiniment simple, parlez-en juste à vos proches et dites leurs qu'un évènement mondial à lieu en collaboration avec toutes les grandes institutions de ce monde pour explique cet éffet papillon qui viens du fait que la planète n'est ni ronde ni plate, mais patatoïdale, et ça c'est la réalité , le reste vous pensez ce que vous voulez avec le nom que vous voulez mais tout le monde s'en fout !! c'est ça Pi

    PS: Pensez aussi que ce qu'on recherche tous c'est la stabilité, c'est l'idée de dieu, mais logiquement vu qu'on n'as pas les mêmes besoins parce qu'on n'habite pas au même endroit on a tous une couleur de peau différentes ..maintenant faite le lien entre la xénophobie(non assumée), la sexualité(refoulée),la peur du regard des autres, l'envie(pulsion forte qu'on recent quant on veut protéger ceux qu'on aime..qu'on appèlle la motivation, la volonté) et .. voyez par vous même si la guerre perpétuels entre individus où pays au nom d'une petite différence d'attention ne conduit pas innévitablement à une lutte perpétuelle, de plus en plus acharnée contre les autres et contre soit-même ... c'est cela que le boson de Higgs, l'odysée de PiKré, le pb de tous vos héros préférés, la raison pour laquelle on pt diviser pour mieux reignez... bref si vous êtes convaincus par ce texte, partagez le juste avec les personne dont vous pensez qu'ils ont assez de présence d'esprit pour mettre un terme à toute ces conneries et règlons cette fichu querelle tous ensemble en se réunissant dans nos universités et grandes écoles fleurons de notre avenir [tous] ensemble pour travailler à la mise en place d'un nouvel ordre mondial guidée par la seule raison -> RDV à la BIG Conf' le 2 Février Prochain

    faites passer le mot 😉

    Amicalement, mr tout le monde.. (La vraie vie c'est ça, on ne peut se sauver que de proche en proche en espérant que celui qu'on à aidé, pourra aussi aider celui qui vient après.. c'est la solidarité.. tout simplement)

    MERCI