Riddle

Bonjour,

Je cherche des énoncés de problèmes où la réponse ne vient pas immédiatement à l'esprit,

mais une fois trouvée elle s'impose par sa simplicité et rend le problème intéressant. Un exemple:

Cinquante pièces de monnaie de différentes valeurs sont alignées sur une table. Alice et

Bob prennent, chacun à son tour, une pièce d'une des deux extrémités. Alice commence.

Prouver qu'elle peut, à la fin du jeu, ramasser au moins la moitié de l'argent mis sur la table.

En connaissez-vous d'autres ?


Un amical merci - Cidrolin
«1

Réponses

  • Cidrolin,
    Je dirais bien le théorème des tiroirs mais en fait c'est un peu la même idée...

    Le problème c'est qu'une solution qui ne vient pas immédiatement à l'esprit
    la première fois qu'on voit un problème, elle vient immédiatement à l'esprit une
    fois qu'on a vu 10 fois le même genre de problème, donc c'est assez subjectif comme notion ...
    Et comme tous les théorèmes sont des tautologies (paraît il)... ;-)

    Sinon je pense que beaucoup d'énigmes de logique sont un peu dans ce cas lorsque la solution
    est simple (genre faire 4 triangles identiques avec 6 allumettes etc , les exemples sont innombrables
    et c'est un peu ce qui leur vaut l'appellation "énigme" d'ailleurs..).

    Eric
  • La question de Cidrolin ne peut être résolue puisque l'énoncé est absurde:

    Cela ne se peut pas :D
    (à moins que je n'ai pas compris le sens de cette phrase)
  • Fin de partie écrivait:
    > Cela ne se peut pas :D

    Même en prenant des yen, des dollars, des euros, ... !?
  • Par ailleurs,

    Je pense qu'en français il y a une différence de sens entre les phrases:

    et:

    Dans la première phrase le sens pour moi est qu'il y a au moins deux pièces de valeur différente

    tandis que dans la seconde phrase le sens est, pour moi, qu'aucune des pièces n'a la même valeur.
  • Bonjour Cidrolin

    J'ai failli corriger ton titre, mais la correction n'aurait pas eu de rapport avec ton message !
    acceptation acception ci-dessus !
    Bon, en changeant de dictionnaire
    Traduction de riddle
    > riddle (nom)
    
    énigme [fém.].
    devinette [fém.].
    charade [fém.].
    crible [masc.].
    claie [fém.].
    
    qui, au moins pour les premiers items, semble mieux correspondre à ton message (:D
    AD

    [Edit : Merci à EV dont j'accepte bien évidemment la remarque :) AD]21763
  • On peut remarquer que le nom du méchant sorcier adversaire de Harry Potter est Riddle, transcrit par le traducteur en Jedusor (jeu du sort).

    Bonne soirée
  • @AD mon premier titre était : Les pièces du fond,

    @Fin de partie, j'ai tenté de traduire du pieux que je meut :

    21765
  • Denominations est bien valeurs, mais various est peut-être mieux traduit par diverses dans ce contexte ?
  • Le cas le plus défavorable à Alice survient quand les pièces se présentent (à "retournement près") de la sorte:


    $x_2$ $x_3$ $x_4$ ...$x_1$

    Les $x_i$ sont les pièces classées dans l'ordre croissant de leur valeur.

    Son total à la fin sera de $T=x_2+x_4+x_6+x_8+x_{10}+...+x_{50}$

    Si $S=x_1+x_2+x_3+...+x_{50}$

    reste à voir pourquoi $\dfrac{T}{S} \ge 0,5$

    PS:

    Cidrolin: avec le texte en anglais tu encourages à la triche ;)
  • Alice ne prend pas forcément ses pièces toujours du même côté.

    Cordialement
    E.C.
  • Fin de partie écrivait:

    > avec le texte en anglais tu encourages à la triche ;)

    C'est vrai, avec ces mots on trouve la réponse avec google :?

    En fait je ne voulais pas poser un problème :D, je demandais si vous en aviez en réserve du même type.

    Amicalement
    C. E.
  • Je ne sais pas dans quelle mesure cela correspond exactement à ce que tu recherches Cidrolin, mais voici quelques problèmes que l'on peut cataloguer comme contre-intuitifs, où bien des gens ont spontanément envie de donner une réponse fausse :

    1) On assimile la Terre à une sphère parfaite. On tend une corde autour d'une circonférence terrestre, puis on coupe la corde, on rajoute un mètre et on forme un nouveau cercle concentrique avec la Terre. Qu'est-ce qui peut passer sous cette corde : un atome, un microbe, un cheveu, un chihuahua, un arbre, la tour Montparnasse ?

    2) On dispose de deux récipients dont la contenance est un litre et d'une cuillère. Le premier récipient est entièrement constitué de café, le deuxième de lait.
    On prend une cuillère du premier récipient que l'on verse dans le deuxième. On touille bien.
    On prend une cuillère du deuxième récipient que l'on verse dans le premier.
    Y a-t-il plus de lait dans le récipient de café que de café dans le récipient de lait, l'inverse, ou les mêmes proportions ?

    3) Albert et Bernard ont respectivement 2 et 3 croissants. Ils invitent Claude pour le petit-déjeuner. Les trois amis mangent la même quantité de croissants. Claude veut dédommager équitablement Albert et Bernard. Il peut leur donner 5 euros. Que donne-t-il à chacun ?

    4) Dans un pays comptant un million d'habitants, une maladie se déclare. Elle affecte actuellement une centaine de personnes qui ne manifestent aucun symptôme. Un test est mis au point pour déterminer si une personne est atteinte ou non et sa fiabilité est de 99 %. Vous passez ce test et les résultats indiquent que vous êtes atteint par la maladie.
    Statistiquement, devez-vous être optimiste ou pessimiste ?

  • Non, mais sauf erreur, sa stratégie pour optimiser son gain est de prendre la pièce de plus grande valeur à chaque fois que c'est son tour de prendre une pièce.

    PS:
    Je comprends le problème, Alice ne joue pas forcément à optimiser son "gain" et pire, l'autre joueur non plus B-)-

    PS2:

    Il doit bien y avoir une configuration où elle va prendre les 25 pièces de plus petites valeurs.
  • Bonsoir
    Fin de Partie a écrit:
    Non, mais sauf erreur, sa stratégie pour optimiser son gain est de prendre la pièce de plus grande valeur à chaque fois que c'est son tour de prendre une pièce.

    Et bien non, ce n'est pas une stratégie gagnante, ça peut conduire à la catastrophe !

    Aldo
  • Reprenons:

    Le total le plus bas que puisse faire Alice est: $T=x_1+x_2+x_3+...+x_{25}$

    Les $x_i$ sont les pièces classées dans l'ordre croissant de leur valeur.

    Si $S=x_1+x_2+x_3+...+x_{50}$

    reste à voir pourquoi $\dfrac{T}{S} \ge 0,5$

    S est minoré par $(x_1+(x_1+1)+(x_1+2)+(x_1+3)+...+(x_1+24)$
    C'est à dire minoré par $25x_1+12\times 25$

    T est majoré par $50x_{50}$ donc sauf erreur $\dfrac{T}{S} \ge \dfrac{25x_1+12\times 25}{50x_{50}}$

    $\dfrac{25x_1+12\times 25}{50x_{50}}> 0,5$ est équivalent à $x_{50}-x_1 <12$
    Cette dernière inégalité n'est pas possible compte tenu des hypothèses.
    On doit avoir: $x_{50}-x_1 >49$

    En espérant ne pas avoir écrit (trop) d'âneries.

    PS:
    On n'est pas obligé de supposer que toutes les pièces ont une valeur différente, il suffit qu'il y ait au moins 13 sortes de pièces sauf erreur de ma part.

    PS2:
    Je crains que ma minoration soit en fait insuffisante pour conclure.

    PS3:
    J'ai du mal avec ce problème, il me semble que mon approche initiale était correcte donc.
    J'avais fini par comprendre, à tort, qu'Alice pouvait jouer au hasard.
  • Je ne sais pas quelles sont les hypothèses implicites que tu fais sur les denominations, qui sont seulement various, mais si $x_1$ jusqu'à $x_{49}$ sont en progression arithmétique de raison 1 centime, partant de 1 centime, et $x_{50}$ est un billet de 5000 €, je ne vois pas comment ton truc peut marcher...
  • Remarque: je fais l'hypothèse que la valeur inscrite sur chaque pièce est un nombre entier.
  • Selon les valeurs des pièces qui peuvent être très variées et même diverses, la meilleure stratégie risque d'être épouvantablement difficile à calculer.

    Heureusement, l'énoncé demande seulement de trouver une stratégie qui évite la défaite.

    Pour ceux que ça amuse, voici en fichier joint zippé le même jeu à 2 dimensions.
  • (troisième tentative)

    Le cas le plus défavorable à Alice (son gain est le plus petit) survient quand les pièces se présentent (à "retournement près") de la sorte:


    $x_2$ $x_3$ $x_4$ ...$x_1$

    Les $x_i$ sont les pièces classées dans l'ordre croissant de leur valeur.

    Son total à la fin sera de $T=x_2+x_4+x_6+x_8+x_{10}+...+x_{50}$

    Si $S=x_1+x_2+x_3+...+x_{50}$

    On a la propriété $x_i\ge i$ pour $1\le x_i \le 50$

    On a: $T \ge 2+4+...+50$

    C'est à dire que $T \ge 25 \times 26$

    Il reste à finir...
  • > Fin de partie

    C'est difficile de voir où tu veux en venir. Dans tes posts précédents, tu appelles T la somme des 25 plus petites valeurs et S la somme des 50 valeurs et tu veux montrer que T/S est supérieur ou égal à 1/2, mais il n'y a aucune raison qu'il en soit ainsi.
  • Est-il vraiment nécessaire de dérécursifier la meilleure stratégie ? Elle existe clairement, avec un argument d'arbre min/max, et il doit être possible de montrer par récurrence sur le nombre de pièces que le gain est positif.

  • Relis l'énoncé, il affirme qu'Alice a toujours une stratégie pour que son gain soit au moins la moitié du total des sommes
    (la somme des valeurs de toutes les pièces).
    Si Bob fait de même j'ai fourni plus haut une configuration où Alice obtiendrait le plus petit gain en jouant au mieux de ses intérêts.
    Si tu n'es pas convaincu essaie avec 50 pièces de valeurs 1,2,3,...50 pour t'en convaincre.
  • FdP : C'est à toi de te convaincre que tu as tort. Que donne ton raisonnement sur un exemple à la remarque, avec les valeurs 1,2,...,48,49,100000000 ? Et attention à ne pas confondre l'hypothèse et la conclusion.

    Comme le dit Aléa, il suffit (par exemple en écrivant les équations de Bellman si on veut formaliser à tout prix) de montrer que le passage de $n$ à $n-2$ pièces peut se faire de manière avantageuse pour Alice, et c'est le cas si au moins l'une des deux inégalités $x_1 \geq \max(x_2,x_n)$ ou $x_n \geq \max(x_1,x_{n-1})$ est vraie.
  • Dans une rue, toutes les familles qui y habitent ont deux enfants. Un démarcheur sonne à la porte de l'une des maisons de cette rue et c'est un jeune garçon qui ouvre la porte. Quelle est la probabilité que l'autre enfant soit une fille ?
  • Bon, en fait ce n'est pas si simple, parce que la condition "$x_1 \geq \max(x_2,x_n)$ ou $x_n \geq \max(x_1,x_{n-1})$" n'a pas de raison d'être vraie...

    Pour me faire pardonner cette digression : les problèmes cités dans ce billet : http://images.math.cnrs.fr/C-est-pourtant-simple.html et dans ses commentaires correspondent assez bien à la demande initiale.
  • Spoiler: numéroter les pièces de 1 à 50 dans l'ordre où elles se présentent.
    Le joueur 1 a toujours la possibilité de prendre : toutes les pièces paires s'il le souhaite ; ou bien toutes les pièces impaires. Il suffit de choisir le cas correspondant au montant le plus élevé.


    [Corrigé selon ton indication. AD]
  • Alice et Bob possèdent une table (parfaitement ronde) et un nombre suffisant de pièces d'un euro. Ils posent à tour de rôle une pièce sur la table. deux pièces ne peuvent pas se toucher. Celui qui ne peut plus rien poser perd. Qui gagne, Alice ou Bob (Alice commence)?
  • Il y a cent rats dans un tube de 10 mètres (avec des extrémités débouchées), allant dans divers sens. Lorsque deux rats se rencontrent ils font tous les deux demi-tour (instantanément). Chaque rat va à un mètre par seconde. Lorsqu'un rat arrive à une extrémité du tube il s'enfuit et n'a plus aucune interaction.
    On suppose que les rats accélèrent instantanément et ont une taille nulle.

    Question : Tous les rats finiront-ils par sortir ? En combien de temps dans le pire des cas ?
  • Bien vu Foys pour les pièces...

    Pour les rats de Mpif, on peut penser "indiscernabilité"...
  • Merci à tous, bravo à Foysnc.
  • Toto a choisi un entier N, puis il a écrit au tableau tous les entiers de 1 jusqu'à N.
    Il choisit au hasard deux entiers parmi ceux qui sont écrits ; il écrit leur différence (positive) puis efface les deux nombres choisis, et il continue ainsi jusqu'à ce qu'il ne reste plus qu'un seul nombre écrit.
    Ce nombre peut-il être n'importe lequel ?
  • Pardon d'insister B-)-

    (quatrième tentative et dernière je pense)

    Le cas le plus défavorable à Alice (son gain est le plus petit) survient quand les pièces se présentent (à "retournement près") de la sorte:


    $x_2$ $x_3$ $x_4$ ...$x_1$

    (cela me semble clair mais je n'ai pas trouvé d'argument convaincant)

    Les $x_i$ sont les pièces classées dans l'ordre croissant de leur valeur.

    Son total à la fin sera de $T=x_2+x_4+x_6+x_8+x_{10}+...+x_{50}$

    Si $S=x_1+x_2+x_3+...+x_{50}$

    On a la propriété $x_i\ge x_{i-1}$ pour $2\le i \le 50$

    $2T=(x_2+x_2)+(x_4+x_4)+(x_6+x_6)+(x_8+x_8)+(x_{10}+x_{10})+...+(x_{50}+x_{50})$
    $\ge (x_1+x_2)+(x_3+x_4)+(x_5+x_6)+(x_7+x_8)+(x_9+x_{10})+...+(x_{49}+x_{50})$

    Cette dernière somme est S, la somme totale sur la table.
    Donc $2T \ge S$

    S ne dépend que de la valeur des 50 pièces et non pas de la position des 50 pièces sur la table.
  • Il faut d'abord établir que l'ordre dans lequel on choisit les nombres ne change pas la parité du dernier nombre.

    On se facilite alors la tâche en regroupant les entiers successifs dans l'ordre depuis 1 : 1 et 2, 3 et 4, etc.

    On observe alors que :

    - le dernier nombre est pair si N est congru à 0 ou 3 modulo 4.
    - le dernier nombre est impair si N est congru à 1 ou 2 modulo 4

    Peut-on en dire plus sur le dernier nombre ? Je ne vois rien pour l'instant.
  • Marrants les rats de mpif :
    21777
  • Il me semble que les rats étaient déjà apparus sur le forum sous forme de fourmis se déplaçant sur une circonférence.

    > remarque : je suis peut-être exigeant mais sur ton gif tu ne peux pas avoir une position de départ aléatoire car ça devient vite lassant ? Bon, c'est vrai qu'on n'est pas obligé de passer son temps à regarder ces bestioles.
  • D'autant plus que je ne sais pas dans quel espace vivent ces rats ponctuels mais ils ont des drôles de formes.

    Sinon je sèche complétement sur le coup de la table parfaitement ronde d'Alice et Bob. On peut poser les pièces sur la tranche ?
  • remarque : je suis peut-être exigeant mais sur ton gif tu ne peux pas avoir une position de départ aléatoire car ça devient vite lassant ?

    Et non, on ne peut pas sur un gif animé.:-( C'est un petit peu consubstantiel au gif animé d'être répétitif, et cela fait parfois son charme. Mais ceci dit, tu peux sûrement faire une applet geogebra vachement plus légère et vraiment aléatoire ! :D
  • Question subsidiaire pour les Rats de Mpif : si les positions et sens de déplacement initiaux sont choisis aléatoirement (indépendamment, etc), quel est le temps moyen d'évacuation complète ?
  • Concernant l'entier N choisi par Toto, on parvient plus vite au résultat en observant que l'opération décrite ne change pas la parité du total qui vaut N(N+1)/2.
  • Bonsoir,

    mon premier Riddle qui m'a fait comprendre qu'arrivé en Terminale C, je n'avais jamais rien compris rien aux nattes.
    (la source originelle relative à moi était Quadrature que j'avais piqué dans les WC, laissé par mon grand frère)
    Là j'ai tapé Google.

    Le docteur Volampson reçoit pour les vacances de la Toussaint ses deux neveux Pierre et Serge, deux petits génies précoces férus de mathématiques. Un soir pour jouer le docteur proposa un jeu après avoir écrit quelquechose sur deux morceaux de papier :

    - Les jeunes, je viens de penser à deux entiers a et b tels que $2< a<b$. Pierre prends ce papier mais ne le montre pas à Serge, tu y découvriras le produit des deux nombres. Serge prends celui-ci pour y trouver leur somme mais cache le bien. Bon, pouvez-vous me dire quels sont les nombres auxquels j'ai pensé ?
    - Je ne sais pas, dit Serge.
    - Je ne sais pas non plus, répondit Pierre.
    - Ah ! Dans ce cas je connais les deux nombres, rétorqua Serge.
    - Du coup moi aussi, triompha Pierre.

    Mais quels sont ces deux nombres ?

    Dans mon hardware, je crois que $b$ était plus petit que 100, peut-être que Google n'est pas mon ami.

    S
  • Mon approche n'est pas la bonne :-(

    En effet, pour simplifier considérons le même jeu mais avec 4 pièces disposées de la sorte:

    2 3 4 1

    J'avais l'impression qu'en jouant au mieux Alice ne pouvait être sûr que de faire un score de 6=2+4

    C'est faux !!!

    Si Alice prend la pièce 1 quelque soit la pièce prise par Bob ( pièce 2 ou 4) elle est sûre, si elle joue au mieux, de faire un score de 7 au minimum sauf erreur.

    PS:
    Il reste un espoir cependant on a seulement besoin de montrer qu'à chaque fois, Alice, en jouant au mieux, peut faire un score supérieur à T (nombre défini plus haut). J'ignore si c'est vrai en fait.

    Y'a-t-il une configuration dans laquelle Alice obtient au mieux un score strictement inférieur à ce nombre?
  • C'est toujours incompréhensible et on ne doit pas parler du même jeu. Comment Alice peut-elle marquer 7 ?

  • Tu as raison, je suis un imbécile !!!

    J'ai additionné quelques pièces de Bob avec celle d'Alice donc mon impression initiale n'était pas malgré tout si mauvaise. Alice peut au moins faire un score de 6(=2+4).

    Dans la configuration 2 3 4 1

    Alice peut prendre la pièce 1 ou 2

    Si elle prend la pièce 2 on se retrouve dans la configuration:

    3 4 1

    Que Bob prenne la pièce 3 ou 1 Alice peut prendre au final la pièce 4 et ton total sera de 6.

    Au départ, si elle prend la pièce 1 on se retrouve dans la configuration:

    2 3 4

    Si Bob prend la pièce 4 Alice peut prendre la pièce 3 son total sera de 4
    Si Bob prend la pièce 2 Alice peut prendre la pièce 4 son total sera de 5

    Ainsi, si j'ai bien compris le fonctionnement du jeu, je pense que dans un jeu avec 50 pièces, Alice peut se retrouver dans une configuration de jeu où elle ne peut faire au mieux (Alice et Bob jouant au mieux pour maximiser leur gain) qu'un score
    de:
    $x_2+x_4+x_6+...+x_{50}$

    En espérant ne pas avoir écrit (trop) d'énormités.
  • Tu n'es plus très loin de la solution.

    Tu as observé que Alice, en commençant par x50 peut s'assurer de prendre x2, x4, x6, ... x50..

    Le même raisonnement : si elle commence par x1, elle peut s'assurer de prendre les pièces ....

    Bon je te laisse terminer.
  • Aldo:

    Ce que je cherche à déterminer est la situation la plus défavorable pour Alice et le score associé.
    C'est le score minimal qu'Alice peut espérer faire même si Bob joue au mieux de son intérêt.

    Et comme indiqué, le score minimal est, selon moi, $x_2+x_4+\ldots +x_{50}$

    Il reste à montrer qu'on ne peut pas trouver de situation dans laquelle, Alice en jouant au mieux , obtiendrait une valeur inférieure à cette valeur.

    [La case LaTeX. AD]
  • > Fin de partie : désolé, je jette l'éponge, je ne comprends rien à ce dernier message.
  • Aldo:

    Pour chaque disposition des 50 pièces il y a une stratégie optimale pour Alice: elle peut se garantir un gain (minimum) qui dépend de la disposition des pièces.

    Maintenant on peut considérer toutes les dispositions des pièces et le gain minimum qui y est associé.
    On peut prendre le minimum de tous ces nombres entiers.

    J'affirme (pour la nième fois et sans preuve pour le moment) que ce minimum est $S=x_2+x_4+x_6+....+x_{50}$ il est associé à une configuration possible des 50 pièces qui est la suivante: $x_2;x_3;...;x_{50};x_1$

    (Les $x_i$ sont les valeurs des 50 pièces ordonnées dans le sens croissant $x_i<x_j$ si $i<j$ )

    Si on appelle $T=x_1+x_2+x_3+...+x_{50}$, le total des gains d'Alice et de Bob

    On peut montrer que:
    $\dfrac{S}{T}\ge 0,5$


    Pour chaque configuration des 50 pièces, le total des gains d'Alice et de Bob est le même c'est T.

    Soit une configuration des 50 pièces dans laquelle Alice peut espérer (au moins) un gain de A quelque soit la façon de
    jouer de Bob.

    Puisque par définition $A\ge S$
    On a donc: $\dfrac{A}{T} \ge \dfrac{S}{T} \ge 0,5$

    PS:
    Supposons que les 50 pièces aient pour valeurs $1$, $2$,$3$,...,$50$
    Si Alice prend les pièces n'importe comment elle pourrait se retrouver avec les 25 pièces:
    $1$,$2$,$3$,...,$25$ dont le total des valeurs est: $\dfrac{25\times 26}{2}=325$

    Le total des gains de Bob et Alice est de $\dfrac{50\times 51}{2}=1275$

    Et $\dfrac{325}{1275}<0,5$
  • Fin de partie

    En conservant ta notation, voici un exemple à 6 pièces :

    x1 = 1
    x2 = 3
    x3 = 5
    x4 = 7
    x5 = 9
    x6 = 11

    Ce que tu appelles S est donc S = x2 + x4 + x6 = 3 + 7 + 11 = 21

    Et T le total des 6 valeurs vaut 36.

    Il est évident que S est toujours supérieur ou égal à la moitié de T puisque chaque terme de rang pair est supérieur au précedent.

    Mais tu prétends que pour toute configuration initiale, la stratégie optimale de Alice lui permettra de marquer au moins S.

    Dans notre exemple, cela fait S=21

    Alors je te propose la position de départ suivante :

    1 - 11 - 7 - 5 - 9 - 3

    Je veux bien prendre le rôle de Bob et te laisser celui d'Alice. Donc tu commences. Je te mets au défi de marquer 21.

    Et pour pimenter l'affaire, je t'annonce d'avance mon premier coup :

    Si tu choisis 1, je prends 11. Si tu choisis 3, je prends 9.

    Bonne chance !

    Aldo
  • Bah si Aldo c'est Bob et Alice c'est Fin de Partie elle ne peut pas commencer sinon c'est Bob enfin Aldo qui fini la partie.
    Foysnc a écrit:
    Alice et Bob possèdent une table (parfaitement ronde) et un nombre suffisant de pièces d'un euro. Ils posent à tour de rôle une pièce sur la table. deux pièces ne peuvent pas se toucher. Celui qui ne peut plus rien poser perd. Qui gagne, Alice ou Bob (Alice commence)?

    Vous avez une idée ? Parce que je ne vois pas du tout le truc.
  • La symétrie centrale peut aider Alice....
Connectez-vous ou Inscrivez-vous pour répondre.