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
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
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))".
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
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.
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.$$
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.$$
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
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 ,
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.
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.
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
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
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.
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
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... )
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
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
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)
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.
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.
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.
Réponses
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
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]$
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))".
Namiswan l'a très bien expliquée, c'est la même formule de récurrence que j'ai obtenue.
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
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.
Je suis curieux de voir cette formule :-D
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
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 ,
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)
A tous, merci de ne dire rien sur ME pour avoir d'autres raisonnements
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.
Je vais te lire la nuit ( j'ai besoin de me concentrer dans un calme absolu ) et revient si besoin
Merci mille fois
Il y a seulement une coquille dans le sigma, $k$ varie de $0$ à $p-1$, mais la suite du calcul est juste.
@jandri
Pour les 3 mousquetaires, peut-on voir ta solution?:-D
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.
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
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.
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.
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
EDIT: bon bah trop tard (:P)
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
Pour le niveau 3, tu peux commencer par exemple par chercher si les cas $N=8$ et $N=10$ sont faisables
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
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.
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 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)
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.
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.
Déjà j'aimerais que vous deviniez le nombre maximum de pièces que l'on peut traiter en 3 pesées.
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 ?
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 ne suis donc pas bon vu que 13 marche pour $k=3$.