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

Balade su run 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



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

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

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

Balad sur un 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 : 1430

Balaed 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 : 931

balzde 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

balzde sur un 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 sur un cuve

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 : 2989
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

bzlade sur un 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 : 3309

Balade sur uun cube

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 : 3057
Lieu: Au sud du Nord

Balade sur u cube

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 : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
P2T
Balade sur un carré par McFlambi
28-06-2010 Enigmes Mathématiques
P2T
Diagonales du cube par tatys
17-09-2010 Enigmes Mathématiques
P2T
Balade de ouf par Vasimolo
27-10-2009 Enigmes Mathématiques
08-08-2011 Enigmes Mathématiques
P2T
16-02-2009 Enigmes Mathématiques
P2T
Balade royale par Vasimolo
23-10-2009 Enigmes Mathématiques
08-11-2009 Enigmes Mathématiques
P2T
Balade de tour par MthS-MlndN
24-10-2009 Enigmes Mathématiques
25-04-2011 Enigmes Mathématiques
P2T
2 boules dans un cube par mitsuidewi
15-02-2011 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) — Probabilite+fourmi+cube (3) — Fourmi paresseuse maths (3) — Fourmi sur un cube (3) — Une fourmi se deplace sur les aretes d un cube (3) — Resolution de l enigme sur le cube (2) — Probleme fourmis paresseuse (2) — Resolution enigme cube (2) — Enigme fourmi cube (2) — Calcul probabilite fourmi cube (2) — Solution exos de maths avec une fourmie paresseuse (2) — Tp fourmi paresseuse (2) — Ex probabilite fourmi (2) — Probleme fourmiis paresseuse (2) — Probleme de math solution sur la ballade de (2) — La fourmi paresseuse (2) — Fourmi arete du cube (2) — Deplacement dans un cube et probalite (2) — Enigme cube fourmi (2) — La fourmi paresseuse tp (2) — Probleme de maths la fourmi paresseuse (2) — Fourmi sur le cube (2) — Enigme cube probabilite (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) — Promenade solution enigme (1) — Probleme de deplacement sur un cube en probabilite (1) — Math activite fourmi paresseuse solution en entier (1) — Enigme cube sommet (1) — Enigme de maths college avec une fourmi sur un cube (1) — Solution pour ballade sur cube (1) — Fourmi arete cube moyen (1) — Probabilite cube fourmi (1) — Enigme a resoudre maths suite geometrique cubes (1) — Enigme de math la fourmi (1) — Probleme fourmie sur les arrete du cube math (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) — Balade sur un cube: 3eme maths (1) — Probleme mathematique fourmi et cube (1) — Enigmes geometriques cube (1) — Enigme fourmis (1) — Deplacement cube sommet oppose (1) — Probabilite la fourmi sur un cube (1) — Seconde math la fourmis paresseuse (1) — Probleme cube fourmi (1) — Exercice maths balade fourmi cube (1) — Maths seconde problem cube et fourmi (1) — Enigme de la fourmi sur un cube (1) — Reponse le cube en balade (1) — Somme de coefficients binomiaux au carre (1) — Probleme de math une fourmie paresseuse (1) — Deux fourmis cube (1) — Une fourmi se deplace sur les aretes d'un cube (1) — Probleme fourmis probabilite (1) — La fourmi paresseuse mathematiques (1) — Devinette avec un carre et une fourmie (1) — Cube mathematique enigme probabilite (1) — Tp sur la fourmie paresseuse (1) — Tp1p65 fourmi paresseuse (1) — Reponse (ax+b) au cube (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) — Probabilite deplacement fourmi nord est (1) — Une fourmi se deplace sur les arete d un cube (1) — Cube et la fourmi (1) — Fourmi enigme pointe opposee cube (1) — Mathematique la fourmi paresseuse (1) — Deplacement et calcule d une foutmie sur un cube (1) — La fourmie 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) — Que peut on dire du nombre de deplacement fourmie cube (1) — Maths une fourmi sur un cube (1) — Enigmes de la fourmi sur le cube (1) — Reponse du tp la fourmis paresseuse (1) — Math probleme d optimisation fourmi paresseuse (1) — Fourmi cube (1) — Fourmi promenade sur un cube (1) — La fourmi pareseuse mathematique (1) — La fourmi paresseuse maths tp (1) — Enigmes balade (1) — Reponses de la fourmi paresseuse (1) — Fourmi proba cube (1) — Solution tp maths fourmi paresseuse (1) — Cube logique (1) — Les fourmis expliquees aux enfants (1) — Probleme la fourmi paresseuse solution (1) — Math la fourmi paresseuse (1) — Probabilite fourmi arete cube (1) — Enigme mathematique fourmi sur un cube (1) — Un cube se ballade exercice (1) — Enigme cube et fourmi (1) — Probleme de maths fourmi paresseuse (1) — Fourmi cube moyenne oppose (1) — Une fourmi se deplace sur un cube de sommet en sommet en suivant les aretes (1) — Deplacement d une fourmi sur les arretes d un cube (1) — Solution la fourmi paresseuse maths (1) — Logique fourmi cube (1) — Tp maths une fourmi paresseuse (1) — Probleme maths la fourmi paresseuse (1) — On note un l probabilite que la fourmi soit en (1) — Syst?me d ?quation (1) — Deplacement sur un cube fourmi (1) — Cube sur la pointe (1) — Probleme une fourmi sur un cube (1) — L enigme du cube et de la fourmi (1) — Maths une fourmi paresseuse (1) — Promenade d une fourmi maths (1) — Deux fourmis sur un cube (1) — Math x fourmis paresseuse (1) — Probleme mathematique arete d un cube variable (1) — Quatres fourmis se deplacent sur le cube (1) — Solution probleme fourmi cube (1) — Resoudrele probleme de la fourmi paresesseuse (1) — Traveaux pratique la fourmis paresseuse (1) — Somme des carres des coefficients binomiaux (1) — Probleme de math fourmis sur un cube solution (1) — Exercice math la fourmi paresseuse (1) — Math exercice cube et fourmis (1) — Deplacement sur un cube probabilite (1) — Enigme du cube maths (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