Énigmes de gebrane et Namiswan - Page 3 — Les-mathematiques.net The most powerful custom community solution in the world

Énigmes de gebrane et Namiswan

13

Réponses

  • Merci bisam
    Je tape quoi pour utiliser ton programme.

    Jandri
    bonjour,
    Pour n paire de disques . si x_n désigne le nombre d’étapes minimale. peux-tu nous donner cette relation de récurrence.

    La partie 3 de l’énigme bien curieuse. on mets dans la tour A les n disques noirs puis au dessus les n disques blanc.
    Pour une paire de 2 disques, le nombre d’étapes minimale est bien celui de Hanoi classique 15 étapes
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Voici la preuve.

    J'appelle H(N) le nombre de coups pour Hanoi classique à N disques, et HG(N) pour le Hanoi de Gebrane à N disques: on a N disques sur A, numérotés par taille décroissante, et on veut amener les disques pairs en B et les disques impairs en C (je ne suppose pas nécessairement N pair).

    Pour se faire:
    -On doit déplacer le grand disque 1, on doit nécessairement déplacer la tour de N-1 disques au dessus. Puisqu'on veut le mettre le disque 1 sur C, on commence par déplacer la tour de N-1 disques en B.
    H(N-1) coups

    -On peut maintenant mettre le disque 1 en C. (Le disque 1 est maintenant bien placé, et le disque 2 aussi en bonus)
    1 coup

    -Pour déplacer le disque 3, on doit déplacer les N-3 disques au dessus. Puisque le disque 3 doit aller sur C, on déplace les N-3 disques sur A.
    H(N-3) coups

    -On met le disque 3 en C. (Les disques 1,2,3 sont maintenant bien placés,les autres sont en A)
    1 coup

    -Les N-3 disques restants sont en A, et on doit les distribuer entre B et C. On s'est donc ramener au problème initial avec 3 disques de moins. Donc on recommence, sauf qu'on doit inverser B et C pour des raisons de parité. On résout donc par induction.
    HG(N-3) coups

    Moralité: $HG(N)=H(N-1)+1+H(N-3)+1+HG(N-3)$

    On sait que $H(k)=2^k-1$ donc $HG(N)=2^{N-1}+2^{N-3}+HG(N-3)=5\cdot 2^{N-3}+HG(N-3)$

    On itére: $HG(N)=5(2^{N-3}+2^{N-6}+\cdots+2^r)+HG(r)$ où $r$ est le reste de N mod 3

    Pour $r=0,1,2$, $HG(r)=r$. Quand à la somme c'est un somme géométrique de raison 8. On calcule donc

    $HG(N)=5\frac{2^N-2^r}{7}+r=\frac{5\cdot 2^N}{7}-(\frac{5\cdot 2^r}{7}-r),$

    avec $\frac{5\cdot 2^r}{7}-r\in ]0,1[$, donc $HG(N)=\left[\frac{5\cdot 2^N}{7}\right]$
  • @gebrane :

    Il faut copier la fonction "move" de mon premier post et la fonction "move_bicolore" du deuxième.
    Ensuite, pour obtenir la liste des mouvements à faire pour N disques, il suffit de taper "move_bicolore(N)".
    Si tu veux juste le nombre de mouvements, il suffit de taper "len(move_bicolore(N))".
  • @gebrane
    Namiswan l'a très bien expliquée, c'est la même formule de récurrence que j'ai obtenue.
  • Merci bisam infiniment
    Merci Jandri
    Namiswan Tu es quelqu'un d'exceptionnel , ta solution me laisse bouche bée surtout l'utilisation des r pour r=0,1,2
    Suite du post effacée contient erreur et inutile
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Edit : Salut gebrane,

    Pour ta suite $HG$, on a donc pour tout $n$, $$HG(n+3)=5\cdot 2^n+HG(n),\;HG(0)=0,HG(1)=1,HG(2)=2.$$On peut chercher une formule algébrique avec un logiciel de calcul formel.
  • Gai Requin
    Je suis curieux de voir cette formule :-D
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Edit : Maple trouve pour tout $n$ :$$HG(n)=-\frac 1{21}\cos\left(\frac2 3n\pi\right)+\frac 1 7\sqrt 3\sin\left(\frac2 3n\pi\right)+\frac 5 7 2^n-\frac 2 3.$$
  • Mh intéressante formule Gai Requin. Peut-on l’écrire sous forme d'une récurrence d'ordre 6?
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Edit : D'après une idée de Math Coss [ici], $HG$ est aussi la solution de la récurrence linéaire suivante :$$u_{n+6}=5u_{n+5}-9u_{n+4}+7u_{n+3}-5u_{n+2}+9u_{n+1}-6u_{n},\quad u_0=0,u_1=1,u_2=2,u_3=5,u_4=11,u_5=22.$$
  • Formidable !
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Gai Requin
    Si on pose dans une olympiade . Montrer que le nombre d’étapes minimale pour Hanoi G est edit $$HG(n)=-\frac 1{21}\cos\left(\frac2 3n\pi\right)+\frac 1 7\sqrt 3\sin\left(\frac2 3n\pi\right)+\frac 5 7 2^n-\frac 2 3.$$ pour n disques. J'aimerais bien voir la tête des candidats
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Il reste les parties 3 et 4 de l’énigme.
    On place cette fois-ci dans la tour A les disques noirs en premier et au dessus les disques blancs.
    3- Chercher le nombre minimal d’étapes pour mettre les blancs dans la tour B et les noirs dans la tour C
    4- Chercher le nombre minimal d’étapes pour déplacer les disques à la tour C mais en mettant les blanc en premier et au dessus les noirs. edit ( oubli signalé par bisam) On peut mettre un disque blanc sur un disque noir ou un disque noir sur un disque blanc sans condition sur le diamètre , bien sûr à respecter si on mets blanc sur blanc ou noir sur noir ,
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • l’énigme est postée sur ME https://math.stackexchange.com/questions/3713759/gebranes-hanoi
    J’espère qu'il ne sera pas fermé

    En profitant de l’édition, corriger les fautes signalées par AD, je propose l'énigme bien connu ( mais version gebrane)
    3 personnages appelés Poirot , Pablo et Gebrane . En sachant que Poirot répond toujours en disant la vérité, que Pablo ment continuellement et que gebrane répond souvent au hasard, tombant parfois sur la vérité et parfois sur le mensonge.

    La question est « simple » : identifiez les identités de Poirot , Pablo et Gebrane en ne posant uniquement que 3 questions dont la réponse est soit vrai, soit faux.

    Chaque question ne peut être posée qu’à une seule personne mais si vous décidez d’interroger une personne (au maximum 3 par conséquent), les autres ne pourront donner de réponse.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Merci Philippe Malot pour la modification dans ME (tu)
    A tous, merci de ne dire rien sur ME pour avoir d'autres raisonnements
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • gebrane :
    Dans ton post, il y a un problème avec la question 4 : c'est impossible si on veut respecter la condition qu'on ne peut pas mettre un disque au-dessus d'un disque plus petit.

    Pour la question 3, on peut reprendre la même technique que Namiswan.
    Si on note $H_3(b,n)$ le nombre minimal de mouvements pour déplacer $b$ disques blancs posés sur $n$ disques noirs, on a les relations suivantes pour tout entier $b$ :
    • $H_3(b,0)=H(b)=2^b-1$ car c'est juste les tours de Hanoï classiques,
    • $H_3(b,1)=H(b)+1=2^b$ car il faut juste faire un dernier mouvement pour mettre le disque noir à sa place
    • et pour tout $n\geq 2$, $H_3(b,n)=H(b+n-1)+1+H(b+n-2)+1+H_3(b,n-2)$ car on déplace d'abord tous les disques vers la tour B sauf 1 de manière classique, puis on place le dernier noir sur la tour C, ensuite, on déplace à nouveau tous les disques de la tour B vers la tour A sauf le dernier noir que l'on place sur C. On s'est alors ramené au même problème avec deux disques noirs de moins.
    Si on écrit $n=2p+r$ avec $r\in\{0,1\}$ alors \[H_3(b,n)=H_3(b,r)+\sum_{k=0}^{p-1}3\times 2^{2k+r+b}=(2^b-1+r)+3\times 2^{b+r}\times\frac{2^{2p}-1}{4-1}=2^b\left(2^n-2^r+1\right)+r-1=2^b\left(2^n-r\right)+r-1\]

    [Edit] J'ai corrigé la coquille signalée plus bas par jandri.
  • Merci bisam
    Je vais te lire la nuit ( j'ai besoin de me concentrer dans un calme absolu ) et revient si besoin
    Merci mille fois
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Je trouve comme bisam.
    Il y a seulement une coquille dans le sigma, $k$ varie de $0$ à $p-1$, mais la suite du calcul est juste.
  • A vrai dire, je n' ai pas encore compris tout. Mais j' y arriverais . Merci encore bisam.
    @jandri
    Pour les 3 mousquetaires, peut-on voir ta solution?:-D
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Pour les trois mousquetaires : pour abréger, on identifie chaque mousquetaire à un nombre. Celui qui dit toujours la vérité vaut 2, celui qui ment toujours vaut 0 et celui qui répond au hasard vaut 1.

    Appelons A, B, C les trois mousquetaires. Alors $(A,B,C)$ est une permutation de $(0,1,2)$.

    On pose une première question à A : si tu étais égal à $2-A$, est-ce qu'il serait possible que tu répondes "oui" à la question "est-ce que B=1" ?

    Premier cas : la réponse est "oui". Alors les seules configurations possibles sont (2,0,1), (0,2,1), (1,0,2), (1,2,0).

    Alors on demande à B : "est-ce que 0=0 ?". S'il répond oui alors on est dans l'un des deux cas (0,2,1) ou (1,2,0), et il suffit de l'interroger à nouveau, sachant qu'il dit toujours la vérité, pour savoir dans quel cas on est. S'il répond non alors on est dans l'un des deux cas (2,0,1) ou (1,0,2) et il suffit de l'interroger à nouveau, sachant qu'il dit toujours un mensonge, pour savoir dans quel cas on est.

    Deuxième cas : le réponse est "non". Alors les seules configurations possibles sont (2,1,0), (0,1,2), (1,0,2), (1,2,0). Même méthode en échangeant les rôles de B et de C.
  • JLT il t'a fallu combien de temps pour trouver ta solution ? ce n'est vraiment pas évident
    Source de l'"énigme avec solution http://villemin.gerard.free.fr/LogForm/Troidieu.htm
    bisam ok c'est bon merci. Pour la 4 je viens de me rendre compte que j'ai oublié de signaler qu'on peut mettre un disque blanc sur un disque noir ou un disque noir sur un disque blanc sans condition sur le diamètre , bien sûr à respecter si on mets blanc sur blanc ou noir sur noir , désolé pour l'oubli
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • En effet ce n'est pas évident, j'ai longtemps tourné en rond avant de raisonner de la manière suivante :

    Notons $N(k)$ le nombre de configurations possibles après $k$ questions. On a $N(0)=6$ et le but est d'arriver à $N(3)=1$.

    Disons qu'on pose la première question à $A$. Les configurations (1,2,0) et (1,0,2) sont compatibles avec les deux réponses. Parmi les deux autres configurations, au moins deux sont compatibles avec l'une des réponses, donc quelle que soit la question posée, on ne peut pas éviter d'avoir $N(1)\geqslant 4$ dans certains cas.

    Comme $N(k+1)\geqslant N(k)/2$ pour tout $k$, il faut donc s'arranger pour être sûr d'avoir $N(1)=4$, $N(2)=2$ et $N(3)=1$.

    Après une question, on a trois cas possibles :

    Premier cas : (2,0,1), (2,1,0), (1,2,0) et (1,0,2) sont compatibles avec l'une des réponses, et (0,1,2), (0,2,1), (1,2,0) et (1,0,2) avec l'autre.

    Si par exemple à la deuxième question on interroge B, la configuration telle que B=1 est nécessairement compatible avec les deux réponses, donc il y aura au moins trois configurations compatibles avec les deux réponses. Même raisonnement si on interroge A ou C à la deuxième question. Le premier cas ne convient donc pas.

    Deuxième cas : (2,0,1), (0,1,2), (1,2,0) et (1,0,2) sont compatibles avec l'une des réponses, et (2,1,0), (0,2,1), (1,2,0) et (1,0,2) avec l'autre. Ca ne convient pas pour la même raison.

    On est donc nécessairement dans le troisième cas : (2,0,1), (0,2,1), (1,2,0) et (1,0,2) sont compatibles avec l'une des réponses, et (2,1,0), (0,1,2), (1,2,0) et (1,0,2) avec l'autre.

    Il faut donc trouver une question posée à A telle que, si A=0 ou A=2, la réponse est "oui" dans les cas (2,0,1) et (0,2,1), et la réponse est "non" dans les cas (2,1,0) et (0,1,2). On remarque que B=1 dans le deuxième ensemble de cas et B est différent de 1 dans le premier. Donc il faut forcer A à répondre en mentant à la question "a-t-on B=1" ?

    On se souvient alors de l'énigme du prisonnier avec les deux portes.
  • J'aurais bien vu une tactique avec la question suivante: "Si je te dis que la théorie de Galois est vraie, me dirais-tu que j'ai raison?"8-)
  • Je me suis abstenu de répondre: ayant lu pas mal de livres de Raymond Smullyan dans ma jeunesse, ce genre d'énigme ça me connait :)

    Tiens Gébrane, voilà une énigme dans la continuité des premières que tu as posées qui peut t'intéresser, bien que vous la connaissez peut être dèjà

    Niveau 1: (version "historique" facile et bien connue)
    On a 9 pièces de même poids sauf une qui est fausse, légèrement plus lourde. On a une balance à 2 plateaux à disposition. Trouvez la fausse pièce en 2 pesées

    Niveau 2: (la variation)
    On a toujours 9 pièces de même poids sauf une qui est fausse, mais on sait juste qu'elle est de poids différent, donc peut être plus lourde, peut être plus légère. On a toujours notre balance. Trouvez la fausse pièce en 3 pesées.

    Niveau 3: (ça se complique...)
    On a N pièces de même poids, sauf une fausse de poids différent, et on doit la trouver en 3 pesées. Pour quelles valeurs de N est-ce possible (autre que 9 donc)?

    Niveau 4: (on généralise)
    Si au lieu de 3 pesées on à k pesées, quelles valeurs de N peut on traiter? (toujours pour trouver une pièce de poids différent parmi N)

    PS: tu devrais mettre un "s" à ton titre de topic.
  • Ok je vais changer le tire en Enigmes de gebrane et Namiswan et j’espère qu'il changera en Enigmes de gebrane, Namiswan, bisam et JLT.
    Je laisse le niveau 3 et 4 pour bisam et ou JLT, je me constante du niveau 1 ou 2 :-)
    edit Le changement du titre est fait , avec ajout dans le premier message des liens vers les énigmes
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Pas besoin de me nommer hein, juste "Enigmes" ça va très bien :) (ou éventuellement "Enigmes en tout genre," Le bazar à énigmes", "énigmes de 7 à 77 ans", etc... )

    EDIT: bon bah trop tard (:P)
  • Namiswan c'est fait exprès pour intéresser la foule
    J'ai trouvé pour les niveaux 1 et 2 , on commence par mettre 3 pièces de chaque coté du plateau .
    NIveau 1
    Si la balance est équilibrée, la pièce se trouve parmi les 3 autres. Dans ce cas on met une pièce de chaque coté de la balance
    et on conclut.
    Si la balance n'est pas équilibré, la pièce se trouve parmi les 3 trois du plateau penché vers le bas. La suite est claire
    Niveau 2 Je laisse le plaisir de trouver par Cere
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • (tu)

    Pour le niveau 3, tu peux commencer par exemple par chercher si les cas $N=8$ et $N=10$ sont faisables
  • Pour la 8 c'est simple mais pas facile à rédiger
    On mets 2 pièces de chaque cotés de la balance
    1er cas: Si équilibré, la fausse se trouve parmi les 4 autres pièces. je prends 2 pièces parmi ces quartes autres que je mets dans un plateau et 2 de bonnes dans l'autre plateau.
    1 er sous-cas Si équilibré, la fausse se trouve parmi les 2 autres.
    Dans ce cas je mets une pièce parmi ces deux autres dans un plateau avec une bonne dans l'autre plateau.
    Si encore équilibre, la fausse c'est l'autre pièce, si ce n'est pas équilibre, je reconnais la fausse
    2eme sous-cas Si ce n'est pas équilibré; la fausse se trouve parmi les 2 pièces pesés et on répète le raisonnement
    2eme cas Si ce n'est pas équilibré, la fausse se trouve parmi les 4 pesés et on répète le raisonnement
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Pour n=10, on mets 4 pièces de chaque côté de la balance. Ca marche aussi pour n =12
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Merci Gebrane pour avoir pensé à moi :)
    Je fais donc la 2(de mon téléphone):

    On met 3 pièces de chaques cotés.
    Si c'est equilibré alors la fausse pièce est dans les 3 dernieres, pas de détails.
    Si ce n'est pas equilibré:
    La où la balance tombe le plus (nomé A), on enlève les 3 pièces et on les remplaces avec les 3 pièces restantes valides.
    Si cela s'equilibre, la pièce fausse est en B et est plus légère.
    Si cela s'équilibre pas, la pièce fausse est en A et est plus lourde.
    Dans ces deux derniers cas, on prend deux pièces des 3 faussées et on peut conclure comme à l'etape 2 du niveau 1 en fonction de d'ou la balance panche ou bien ne panche pas.
  • Pour le niveau 4:
    Si on sait que la pièce est plus lourde ou bien qu'elle est plus légère,pour k pesés possibles, si $n \leq 3^k$ alors c'est bon je crois.

    En 2 pesés, on peut savoir si la pièces est plus lourde ou moins lourde et qu'elle se situe dans un bloc d'au plus $n/3$ pièces.
    (En faisant comme ce que j'ai décris pour le niveau 2).

    Je dirais donc que pour $k$ assez grand, la borne sup pour $n$ tend vers $ 3^{k-1}$.

    Ps: Je n'ai ni papier ni stylo, j'ai donc surement une erreur.
  • Ok pour le niveau 1 par Gebrane
    Ok pour le niveau 2 par Cere
    Ok pour le niveau 3 pour N=8 par Gebrane (un bel algo de dichotomie, on élimine la moitié des pièces à chaque pesée)
    Pas convaincu pour le cas N=10: tu met 4 pièces de chaque coté: si ça s'équilibre, la fausse pièce est dans les 2 qui reste et c'est facile. Si ça penche, elle est dans les pièces pesées: comment tu fais pour la trouver en 2 pesées?
    Pour le niveau 4 par Cere: oui, tu donnes un algorithme qui permet de traiter $3^{k-1}$ pièces en k pesées. Ce n'est cependant pas le nombre de pièces optimal (par exemple, il est effectivement possible de traiter 10 pièces en 3 pesées). Mais ça reste un bon ordre de grandeur (on peut aisément se convaincre qu'aucun algorithme ne peut traiter plus de $3^k$ pièces)
  • Tu as raison pour n=10. Mon raisonnement ne tient pas.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Namiswan, tu m'as fait douter du raisonnement. Je donne les détails.
    On mets 4 pièces de chaque coté de la balance, à gauche les 4 pièces notées
    a1,a2,a3 et a4 et à droite les pièces b1,b2,b3 et b4 et il reste les deux pièces c1 et c2

    1er cas. Si équilibré, c'est ok comme tu as constaté

    2ème cas. Si non équilibré, alors c1 et c2 sont bonnes et pour fixer les idées on suppose que la balance penche vers la droite : la plus lourde est parmi b1,b2,b3 et b4.
    On met a1 + a2 + b2 sur le plateau de gauche et b1 + a3 + c1 sur le plateau de droite.

    1er sous-cas. Si équilibré, la mauvaise pièce est parmi a4, b3 et b4.
    On met alors a4 + b3 sur le plateau de gauche et c1+ c2 sur l'autre.

    Si équilibré, la mauvaise est b4.

    Si la balance penche du même coté que la première pesée, c'est-à-dire vers la droite alors la mauvaise pièce est a4 (la seule qui n'a pas changé de coté).

    Si la balance penche de l'autre coté, la mauvaise pièce est b3 (la seule qui a changé de coté).

    2eme sous-cas. Si non équilibré.
    1er sous-sous-cas. Si la balance penche vers la gauche, la mauvaise pièce a changé de plateau et c'est donc a3 ou b2.
    On met a3 sur un plateau et c1 sur l'autre.
    Si équilibré, la mauvaise pièce est b2.
    Si non, la mauvaise est a3.

    2-ème sous-sous-cas. Si la balance penche vers la droite, la mauvaise pièce est a1 ou a2 ou b1. Dans ce cas, sur le plateau de gauche, on met a1 + b1 et on met c1 + c2 sur celui de droite

    Si équilibre, la mauvaise pièce est a2.
    si non équilibré,
    - si la balance penche toujours du même coté, la mauvaise pièce est a1 (la seule qui n'ait pas changé de place)
    - si la balance penche de l'autre coté, la mauvaise pièce est b1.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Le but n'était pas de te mettre pas de te faire des doutes mais d'avoir des détails. Je suis maintenant (parfaitement) convaincu pour ton N=10 (tu)
  • Namiswan
    Je sais que ma borne n'est pas exacte, je m'étais couvert avec "k assez grand" :-D !
    Est ce qu'il y a une formule précise à trouver?
    Si c'est le cas alors évidemment ma solution n'est pas satisfaisante.
  • Il y a bien une formule précise "fermée" en fonction de k.
  • Namiswan peux-tu donner cette formule?
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Laissons encore un peu les gens y réfléchir :)

    Déjà j'aimerais que vous deviniez le nombre maximum de pièces que l'on peut traiter en 3 pesées.
  • En 3 pesées c'est 12.
  • Je pense aussi que 12 est le mximum pour 3 pesées
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • On peut faire mieux :-D
  • Mince car ça casse la formule que j'avais conjecturé et que je voulais tenter de démontrer...
  • Ok pour 13 pieces en 3 pesees
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Pour 14 pièces , ça coince en 3 pesées
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Une âme bien faisante m'a mp. Le nombre de pesées optimale pour n pieces (n>2) est la partie entière du logarithme à base (je cache) de n
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Gebrane : bien joué, en trois pesées le nombre optimal est effectivement 13. Il sera bien que quelqu'un explicite un algo avec 13 pièces, pour la postérité (le plus dur du travail ayant déjà été fait).

    Je me pose des questions sur la formule qu'on t'a donnée. Déjà il est plus simple d'expliciter le nombre de pièces optimal en fonction du nombre de pesées plutôt que l'inverse. D'autre part je ne vois pas ta formule correspondre avec la mienne. Elle donne par ex bien 3 pour 13 pièces ? et 4 pour 14 ?
  • Le but était que quelqu'un trouve tout seul.
    Je pense que l'on est tous assez érudis pour chercher la reponse sur google sinon :-D !

    Par contre si tu parles de base 3, je crois que c'est faux.
    Si dans le problème, on savait si la pièce était plus ou moins lourde, le nombre optimal de pesées pour n pièces serait la partie entiere supérieur de log(n) en base 3 (du moins, avec l'algo au quel je pense).
    Donc pour le log en base 3...
    Mais je ne vois pas de quelle autre base on pourrait parler.
  • Je crois avoir un algo qui donne la borne sup $(3^k -3)/2$.
    Je ne suis donc pas bon vu que 13 marche pour $k=3$.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!