Énigmes de gebrane et Namiswan

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
Namiswan l'a très bien expliquée, c'est la même formule de récurrence que j'ai obtenue.

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.

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.$$

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.

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.

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.

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.

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)

(tu)

Pour le niveau 3, tu peux commencer par exemple par chercher si les cas $N=8$ et $N=10$ sont faisables

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.

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)

Il y a bien une formule précise "fermée" en fonction de k.

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.

Mince car ça casse la formule que j'avais conjecturé et que je voulais tenter de démontrer...

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 ?

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$.