Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 29-06-2010 09:39:58

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

Blade sur un cube

Là, ça se complique un peu par rapport à la balade sur le carré, mais une bonne compéhension d'une technique sur le carré devrait pouvoir être étendue à ce problème. Encore une fois, et plus que pour le carré, une petite culture mathématique me semble asseez utile pour résoudre le problème.

Je redonne donc l'énigme : Combien y a-t-il de balades différentes, allant de [latex]A[/latex] à [latex]B[/latex], et de exactement [latex]n[/latex] déplacements* ?

[* On ne se déplace que sur les arêtes du cube, pas de diagonale]

                        Cas 1 :
http://www.prise2tete.fr/upload/McFlambi-baladecube1.JPG


                        Cas 2 :
http://www.prise2tete.fr/upload/McFlambi-baladecube2.JPG


                        Cas 3 :
http://www.prise2tete.fr/upload/McFlambi-baladecube3.JPG


                        Cas 4 :
http://www.prise2tete.fr/upload/McFlambi-baladecube4.JPG

  • |
  • Répondre

#0 Pub

 #2 - 29-06-2010 12:49:21

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

Balade sur u cube

quelles sont les regles de deplacement? peut-on repasser sur une arete plusieurs fois?


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #3 - 29-06-2010 16:42:41

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Blade sur un cube

Déjà, pour éviter d'avoir à le répéter partout: pour les cas 1 et 3, on a une valeur nulle pour tout n impair, et pour les cas 2 et 4 pour tout n pair.
Pour le reste, voilà ce qu'on va faire: on va se faire un système d'équations sympatoche !

Les inconnues:
[TeX]a_n[/latex],[latex]b_n[/latex],[latex]c_n[/latex] et [latex]d_n[/latex], répondent aux cas 1,2,3 et 4

Les équations:
Pour arriver au cas 1, on vient forcément au coup précédent du cas 2 (ou un de ses symétriques)
[latex]a_n = 3*b_{n-1}[/TeX]
Pour arriver au cas 2, on peut venir du cas 1 au coup précédent, ou bien du cas 3 ou de son symétrique
[TeX]b_n = a_{n-1} + 2 * c_{n-1}[/TeX]
Pour arriver au cas 3, on peut venir du cas 2 au coup précédent ou de son symétrique, ou encore du cas 4
[TeX]c_n = 2 * b_{n-1} + d_{n-1}[/TeX]
Pour arriver au cas 4, on vient forcément au coup précédent du cas 3 (ou un de ses symétriques)
[TeX]d_n = 3 * c_{n-1}[/TeX]
On remarque aussi que
[TeX]
a_0 = 1, b_0 = c_0 = d_0 = 0
[/TeX]
Résolution :
[TeX]
a_n = 3 * b_{n-1} = 3 * a_{n-2} + 6*c_{n-2}\\
c_n = 2 * b_{n-1} + d_{n-1} = 2 * a_{n-2} + 7 * c_{n-2}\\
[/TeX]
Donc
[TeX]a_n - c_n = a_{n-2} - c_{n-2}[/TeX]
Donc la différence entre a et c est constante (pour n pair bien entendu), et par la valeur en n=0, on remarque que cette constante vaut 1.
[TeX]a_n = 3 * a_{n-2} + 6*c_{n-2} = 9 * a_{n-2} - 6[/TeX]
On pose alors
[TeX]v_n = a_n + K\\
v_n = 9 * a_{n-2} - 6 + K\\
v_n = 9 * v_{n-2} - 6 -8 K\\
v_n = 9 * v_{n-2} - 6 -8 K[/TeX]
et on aimerait bien avoir une progression géométrique, donc on va prendre K = -6/8 = -3/4
[TeX]
v_n = a_n - \frac{3}{4}\\
v_n = 9 * a_{n-2} - 6 -\frac{3}{4}\\
v_n = 9 * v_{n-2}\\
[/TeX]
Donc
[TeX]
v_{n+1} = 3*v(n)\\
v_n = 3^n * v_0 = 3^n * (a_0 - 3/4) = \frac{3^n}{4}\\
a_n = v_n + \frac{3}{4} = \frac{3^n + 3}{4}
[/TeX]
On pourrait faire pareil pour les autres variables, mais on va faire plus court:

D'après ce qu'on a dit plus haut déjà:
[TeX]c_n = a_n-1\\
c_n = \frac{3^n - 1}{4}[/TeX]
Ensuite, on a une relation entre b et a
[TeX]
b_{n-1} = \frac{a_n}{3}\\
b_{n-1} = \frac{3^{n-1} + 1}{4}\\
b_{n} = \frac{3^n + 1}{4}
[/TeX]
Et enfin, une relation entre c et d
[TeX]
d_n = 3 * c_{n-1}\\
d_n = \frac{3^{n-1} - 1}{4} * 3
d_n = \frac{3^n - 3}{4}
[/TeX]
Réponse:
Pour le cas 1
   0 si n est impair
   3^n +3) / 4

Pour le cas 2
   0 si n est pair
   (3^n +1) / 4

Pour le cas 3
   0 si n est impair
   (3^n -1) / 4

Pour le cas 4
   0 si n est pair
   (3^n -3) / 4

Et, coup de chance incroyable, ça vérifie nos équations !
Bon ok c'était pas vraiment tiré du chapeau ces suppositions. Pour trouver ça:

 #4 - 30-06-2010 10:31:08

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 964

Baade sur un cube

Je préfère raisonner en terme de probabilités uniformes, il suffit de multiplier par 3^n pour avoir le nombre de balades.

Au bout d'un nombre pair de déplacements, la fourmi est soit en A, soit en l'un des 3 sommets situés au bout d'une diagonale de face issue de A.
Soit p(2n) la probabilité que la fourmi soit en A au bout de 2n déplacements.
Pour n=0, o a p(0)=1.
J'obtiens avec un arbre de choix :
[TeX]p(2n+2)=\frac 13 p(2n)+\frac 29 (1-p(2n))[/latex] d'où [latex]p(2n+2)=\frac 29 + \frac 19 p(2n)[/TeX]
On observe alors :
[TeX]p(2n+2)- \frac 14 =\frac 19 [p(2n)- \frac 14][/TeX]
On voit apparaître une belle suite géométrique de raison 1/9 et de terme initial 3/4.
Alors :
[TeX]p(2n)=\frac 14 + \frac 34 (\frac 19)^n[/TeX]
Nombre de balades revenues en A au bout de 2n déplacements : [latex]\frac {9^n + 3}4[/latex]
Nombre de balades correspondant au cas n°3, pour chacun des 3 sommets concernés : [latex]\frac {9^n - 1}4[/latex] justifié par l'événement contraire.

Au bout d'un nombre impair de déplacements, la fourmi est soit en l'un des 3 sommets situés au bout d'une arête issue de A soit au point opposé à A dans le cube, sommet que je note G.
Soit p(2n+1) la probabilité que la fourmi soit en G au bout de 2n+1 déplacements.
Pour n=0, o a p(1)=0.
Des calculs similaires donnent :
[TeX]p(2n+3)- \frac 14 =\frac 19 [p(2n+1)- \frac 14][/TeX]
On voit apparaître une autre suite géométrique de raison 1/9 et de terme initial -1/4.
Alors :
[TeX]p(2n+1)=\frac 14 - \frac 14 (\frac 19)^n[/TeX]
Nombre de balades aboutissant en G au bout de 2n+1 déplacements : [latex]\frac {3(9^n -1)}4[/latex]
Nombre de balades correspondant au cas n°2, pour chacun des 3 sommets concernés : [latex]\frac {3 \cdot 9^n + 1}4[/latex] obtenu également par événement contraire.

J'espère que j'ai bon, sinon je réclame l'anonymat lol


Celui qui fuit les casse-tête ne vaut pas un clou.

 #5 - 30-06-2010 11:32:34

falcon
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 106

balade sur yn cube

posons
1er cas : x(n)
2eme cas : y(n)
3eme cas : z(n)
4eme cas : t(n)

Remarquons que les cas 1 et 3 sont "pairs", c'est à dire que l'on ne peut pas relier A et B avec un nombre impair de déplacement dans ces deux cas. De meme 2 et 4 sont "impairs"

ensuite on obtient facilement les lois de récurences suivantes
x(n+1) = 3 y(n)
y(n+1) = x(n) + 2 z(n)
z(n+1) = 2 y(n) + t(n)
t(n+1) = 3 z(n)

posons alors v(n) = y(n) + z(n). v(n) vaut y(n) si n est impair et z(n) sinon.
et v(n+1) = 2 v(n) + 3 v(n-1)

deplus v(1) = 1 et v(2) = 2

d'ou v(n) = [(-1)^(n+1) + 3^n ] / 4

Ainsi onobtient

x(n) = 3 * [(-1)^(n) + 3^(n-1) ] / 4 si n est pair 0 sinon.

y(n) = [(-1)^(n+1) + 3^n ] / 4 si n est impair 0 sinon.

z(n) = [(-1)^(n+1) + 3^n ] / 4 si n est pair 0 sinon.

t(n) = 3 * [(-1)^(n) + 3^(n-1) ] / 4 si n est impair 0 sinon.


Il vaut mieux pomper meme s'il ne se passe rien que risquer qu'il se passe quelque chose de pire en ne pompant pas

 #6 - 30-06-2010 12:17:33

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

Balade su un cube

3 bonnes réponses ! bravo à scarta, scrabblor et falcon!

Rappel, on peut se déplacer sur les arêtes uniquement, revenir sur ses pas, repartir, bref, tout ce qui compte, c'est qu'en partant de [latex]A[/latex], et en [latex]n[/latex] déplacements élémentaires, on arrive en [latex]B[/latex]. La réponse est sous la forme d'une fonction de [latex]n[/latex].

 #7 - 30-06-2010 12:53:13

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

balade sir un cube

cas 1:
un nombre impair de deplacements: 0 cas
2 deplacements: 3 cas
4 deplacements: 9 cas
6 deplacements: 45 cas
cas 2:
un nombre pair de deplacements: 0 cas
1 deplacement: 1 cas
3 deplacements: 5 cas
etc...


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #8 - 02-07-2010 19:17:46

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

balade sur ub cube

[img][/img]

La solution la plus élégante est la récurrence. J'avais aussi écris une démonstration utilisant le dénombrement, et comptant explicitement les déplacements possibles avec une méthode similaire à celle expliquée dans l'énigme "balade sur un carré", mais je'ai la flemme de la réécrire. L'idée est qu'on a une double somme de coefficients binomiaux, et que la somme à l'intérieur se transforme en la moitié de [latex]2^n[/latex] et des brouettes, et que la somme totale devient le quart de [latex]3^n[/latex] et des brouettes, qui est la solution.

Pour la résolution par récurrence, en voici une version (un peu) simplifiée, ou je détaille  beaucoup la récurrence.

Tout d'abord, étudions les symmétries du problème. Encore une fois, la parité de [latex]n[/latex] détermine les positions où l'on peut-être :
- pair, on est soit au départ (cas 1), soit dans le cas 3
- impair, on est soit dans le cas 2, soit dans le cas 4.

A partir de là, il suffit de 2 suites pour résoudre le problème, que je note [latex]u[/latex] et [latex]v[/latex], comme sur l'image :
http://www.prise2tete.fr/upload/McFlambi-baladecubesolpriv.JPG

Pourquoi cela suffit-il ? Parce que la parité donne accès aux 4 cas différents !
En effet, soit on est sur un point de type [latex]u[/latex], et dans ce cas un [latex]n[/latex] pair implique qu'on est dans le cas 1, et un [latex]n[/latex] impair dans le cas 4. Soit on est sur un point de type [latex]v[/latex], et dans ce cas un [latex]n[/latex] pair implique qu'on est dans le cas 3, et un [latex]n[/latex] impair dans le cas 2.

Ensuite, la récurrence proprement dite : Etre en un point de type [latex]u[/latex], c'est venir d'un de ses trois "voisins" de type [latex]v[/latex]. Et etre en un point de type [latex]v[/latex], c'est venir soit d'un de ses deux "voisins" de type [latex]v[/latex], soit de son voisin de type [latex]u[/latex] :
http://www.prise2tete.fr/upload/McFlambi-baladecubesolpriv2.jpg

Donc la récurrence est :
[TeX]\left{\begin{array}{l} u(n+1)=3v(n) \\ v(n+1)=u(n)+2v(n)\end{array}\right.[/TeX]
La je fais place à l'élégance d'une résolution matricielle. La récurrence étant équivalente à :
[TeX]{\left( \begin{array}{c}u \\ v \end{array}\right)}_{n+1} = \left( \begin{array}{cc} 0 & 3 \\ 1 & 2 \end{array} \right) {\left( \begin{array}{c} u\\ v\end{array} \right)}_{n}[/TeX]
Pour résoudre cette récurrence, il suffit de calculer les racines du polynôme caractéristique de la matrice dans la récurrence. Donc :
[TeX]\det \left( \begin{array}{cc} -x & 3 \\ 1 & 2-x \end{array}\right)=-x(2-x)-3=x^2-2x-3[/TeX]
de racines "évidentes" 3 et -1.

Donc les solutions (pour [latex]u[/latex] et [latex]v[/latex]) sont du type [latex]a 3^n+ b (-1)^n[/latex].

Les valeurs initiales nous permettent de trouver ces coefficients :
[TeX]\left{\begin{array}{l} u(0)=a_u +b_u =1 \\ u(1) = 3a_u - b_u = 0 \\v(0)=a_v+b_v =0 \\v(1)=3a_v-b_v=1 \end{array}\right. \Rightarrow \left{\begin{array}{l} a_u=1/4 \\ b_u = 3/4 \\ a_v=1/4 \\ b_v=-1/4 \end{array} \right.[/TeX]
Et donc :
[latex]\left{ \begin{array}{l} u(n)=\frac{3^n+3(-1)^n}{4} \\ v(n)=\frac{3^n-(-1)^n}{4}\end{array}\right.[/latex].

Voili voilou !

 #9 - 03-07-2010 15:28:44

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Balade sur un cbe

Je pense qu'il me faut encore de la logique pour comprendre tout ça c'est pourquoi je pense que je vais finir les énigmes jusqu'a la 48 quitte à m'entayer les veines!! yikes

J'ai eu du mal à comprendre l'énoncer alors les réponses O_O.

Je ne regarderai plus jamais un cube de la même manière. smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #10 - 03-07-2010 16:34:47

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3073
Lieu: Au sud du Nord

Balade sur un cuube

J'ai eu du mal à comprendre l'énoncer alors les réponses O_O.

+1


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
P2T
Cube magique par SaintPierre
15-08-2011 Enigmes Mathématiques
P2T
Énigme du cube par Gulio
29-06-2013 Enigmes Mathématiques
P2T
16-02-2009 Enigmes Mathématiques
P2T
06-11-2017 Enigmes Mathématiques
P2T
Balade sur un carré par McFlambi
28-06-2010 Enigmes Mathématiques
P2T
Balade royale par Vasimolo
23-10-2009 Enigmes Mathématiques
P2T
Diagonales du cube par tatys
17-09-2010 Enigmes Mathématiques
17-05-2013 Enigmes Mathématiques
P2T
Balade de ouf par Vasimolo
27-10-2009 Enigmes Mathématiques
P2T
cube logique par linny
29-01-2009 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)
La fourmi paresseuse maths (12) — Maths la fourmi paresseuse (8) — Ballade sur un cube (8) — Fourmi cube (7) — Balade sur un cube (6) — Probleme fourmi cube (5) — Balade sur un cube maths (4) — Tracer un cube en une seule fois (4) — Fourmi sur un cube probabilite (3) — Travaux pratiques la fourmi paresseuse (3) — Ballade sur cube (3) — La fourmi paresseuse correction (3) — Fourmi paresseuse maths (3) — Probabilite+fourmi+cube (3) — Fourmi sur un cube (3) — Une fourmi se deplace sur les aretes d un cube (3) — Enigme fourmi cube (2) — Probleme fourmiis paresseuse (2) — Resolution enigme cube (2) — Resolution de l enigme sur le cube (2) — Calcul probabilite fourmi cube (2) — Fourmi baton probabilite enigme (2) — Probleme fourmis paresseuse (2) — Tp fourmi paresseuse (2) — Solution exos de maths avec une fourmie paresseuse (2) — Ex probabilite fourmi (2) — Fourmi arete du cube (2) — Probleme de maths la fourmi paresseuse (2) — Deplacement dans un cube et probalite (2) — La fourmi paresseuse (2) — Enigme cube fourmi (2) — La fourmi paresseuse tp (2) — Probleme de math solution sur la ballade de (2) — Enigme cube probabilite (2) — Fourmi sur le cube (2) — Comment resoudre le probleme la ballade de la fourmi (1) — La fourmis paresseuse mathematique (1) — Probalite de deplacement dans un cube (1) — Tp de math la fourmi paresseuse (1) — Probleme de deplacement sur un cube en probabilite (1) — Enigme a resoudre maths suite geometrique cubes (1) — Solution pour ballade sur cube (1) — Enigme de maths college avec une fourmi sur un cube (1) — Fourmi arete cube moyen (1) — Promenade solution enigme (1) — Enigme cube sommet (1) — Probabilite cube fourmi (1) — Math activite fourmi paresseuse solution en entier (1) — Probabilite la fourmi sur un cube (1) — Maths probleme la fourmi paresseuse (1) — La fourmi paresseuse reponse (1) — Enigme de cube fourmi (1) — Probleme de math sur un cube fourmi (1) — Maths seconde problem cube et fourmi (1) — Probleme mathematique fourmi et cube (1) — Enigmes geometriques cube (1) — Enigme fourmis (1) — Deplacement cube sommet oppose (1) — Probleme fourmie sur les arrete du cube math (1) — Seconde math la fourmis paresseuse (1) — Exercice maths balade fourmi cube (1) — Probleme cube fourmi (1) — Enigme de math la fourmi (1) — Deux fourmis cube (1) — Reponse le cube en balade (1) — Probleme fourmis probabilite (1) — Somme de coefficients binomiaux au carre (1) — Probleme de math une fourmie paresseuse (1) — Balade sur un cube: 3eme maths (1) — Une fourmi se deplace sur les aretes d'un cube (1) — La fourmi paresseuse mathematiques (1) — Tp1p65 fourmi paresseuse (1) — Devinette avec un carre et une fourmie (1) — Deplacement et calcule d une foutmie sur un cube (1) — Cube mathematique enigme probabilite (1) — Tp sur la fourmie paresseuse (1) — Balade sur cube (1) — Tp math la fourmi paresseuse (1) — Calcul probabilite arete cube (1) — Fourmi cube -paresseuse (1) — Probleme fourmi sur un cube (1) — Fourmi cube sommet (1) — Enigme cube deplacement (1) — Probleme de la fourmi et le cube probabilite (1) — Enigme des trois v (1) — Exercice maths le cube et la fourmi (1) — Cube fourmi (1) — Une fourmi se deplace sur les arete d un cube (1) — Probabilite deplacement fourmi nord est (1) — Cube et la fourmi (1) — Mathematique la fourmi paresseuse (1) — Fourmi enigme pointe opposee cube (1) — Enigme de la fourmi sur un cube (1) — Math exercice cube et fourmis (1) — Probleme de maths fourmi paresseuse (1) — Math activite la fourmi paresseuse soluce (1) — Probleme maths 2eme fourmi1 et fourmi 2 (1) — Activite mathematiques la fourmi sur le cube (1) — Fourmi paresseuse+cube (1) — La fourmi paresseuse solution (1) — Lyon balade enigme (1) — Somme des carres et des cubes avec coefficients binomiaux (1) — Maths une fourmi sur un cube (1) — Que peut on dire du nombre de deplacement fourmie cube (1) — Reponse du tp la fourmis paresseuse (1) — Fourmi cube (1) — Math probleme d optimisation fourmi paresseuse (1) — Enigmes de la fourmi sur le cube (1) — Les fourmis expliquees aux enfants (1) — Cube logique (1) — Reponses de la fourmi paresseuse (1) — La fourmi paresseuse maths tp (1) — Enigmes balade (1) — Fourmi proba cube (1) — Solution tp maths fourmi paresseuse (1) — Probabilite fourmi arete cube (1) — Un cube se ballade exercice (1) — Probleme la fourmi paresseuse solution (1) — Math la fourmi paresseuse (1) — La fourmi pareseuse mathematique (1) — Enigme mathematique fourmi sur un cube (1) — Enigme cube et fourmi (1) — Fourmi promenade sur un cube (1) — Math x fourmis paresseuse (1) — Deplacement d une fourmi sur les arretes d un cube (1) — On note un l probabilite que la fourmi soit en (1) — Une fourmi se deplace sur un cube de sommet en sommet en suivant les aretes (1) — Solution la fourmi paresseuse maths (1) — Probleme maths la fourmi paresseuse (1) — Logique fourmi cube (1) — Syst?me d ?quation (1) — L enigme du cube et de la fourmi (1) — Deplacement sur un cube fourmi (1) — Fourmi cube moyenne oppose (1) — Cube sur la pointe (1) — Probleme une fourmi sur un cube (1) — Maths une fourmi paresseuse (1) — Tp maths une fourmi paresseuse (1) — Promenade d une fourmi maths (1) — Quatres fourmis se deplacent sur le cube (1) — La fourmie paresseuse (1) — Solution probleme fourmi cube (1) — Traveaux pratique la fourmis paresseuse (1) — Resoudrele probleme de la fourmi paresesseuse (1) — Probleme mathematique arete d un cube variable (1) — Somme des carres des coefficients binomiaux (1) — Exercice math la fourmi paresseuse (1) — Deux fourmis sur un cube (1) — Deplacement sur un cube probabilite (1) — Enigme du cube maths (1) — Probleme de math fourmis sur un cube solution (1) — Reponse (ax+b) au cube (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete