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 - 04-10-2012 00:04:58

Alexein41
Professionnel de Prise2Tete
Enigmes résolues : 29
Messages : 119

uand un problème dégénère...

Bonsoir tout le monde !

   J'suis en maths spé option informatique, et nous avons réfléchi avec quelques-uns de mes potes à un problème qui est le suivant :

   Vous vous trouvez devant un mur infini, c'est-à-dire que devant vous, le mur s'étend à gauche jusqu'à l'infini, et de même à droite. Vous savez que le mur possède UNE porte, mais vous ne pouvez la trouver qu'à une seule condition : vous retrouver juste devant.
   (On est donc ramené à un problème "géométrique" unidimensionnel où l'on se trouve en un point O et où il faut trouver un point P en parcourant le plus petite distance possible, tout en ignorant la position de P)

   Le but de cet exercice est de trouver cette porte : si on note [latex]d[/latex] la distance initiale de vous à la porte, il faut trouver un algorithme qui permet de trouver cette fameuse porte en une distance en [latex]O(d)[/latex].

   Nous sont venues plusieurs idées à l'esprit comme par exemple, parcourir une distance [latex]a_1[/latex] vers la droite, puis une distance [latex]2a_1[/latex] vers la gauche, puis une distance [latex]3a_1[/latex] vers la droite, etc. ; algorithme qui n'est pas en [latex]O(d)[/latex], mais ce n'est pas ce qui nous intéresse ici !

   En disant un peu n'importe quoi, nous avons considéré l'idée suivante : partir d'une distance [latex]a_1[/latex] vers la droite ou la gauche (ça a peu d'importance, au pire on tire à pile ou face !), puis aller dans le sens opposé si on n'a pas trouvé la porte et parcourir une distance [latex]exp(a_1)[/latex], et recommencer dans l'autre sens en marchant sur une distance de [latex]exp(exp(a_1))[/latex], etc.

   Et tant qu'à faire, pourquoi ne pas utiliser la factorielle ? Prenons une distance entière (ça marche un peu mieux), différente de préférence de 0, 1 et 2 que l'on note [latex]a_1[/latex]. On effectue cette distance d'un côté, et on repart de l'autre si on n'a pas trouvé la porte d'une distance [latex]a_1![/latex]. Si on n'a pas vu la porte, on recommence de l'autre côté d'une distance de [latex](a_1!)![/latex], etc.

   Le problème initial (qui ne nous intéresse donc plus vraiment) nous a conduit au final à nous demander si, en prenant la distance [latex]a_1[/latex] égale à 3, la méthode avec exponentielle "explose plus rapidement" que la méthode avec factorielle.

   Le problème se résume ainsi :
En posant [latex]u_0=a \in \mathbb{N}[/latex], et [latex]u_n_+_1 = exp(u_n)[/latex] et en posant [latex]v_0=a \in \mathbb{N}[/latex] et [latex]v_n_+_1 = (v_n)![/latex], est-ce que pour n "assez grand" l'une des deux suites prédomine sur l'autre ? (On prend a différent de 0, 1 et 2)

   Si [latex]a=3[/latex] :
   Pour l'exponentielle, on obtient environ les termes 3 ; 20 ; 400x10^6.
   Pour la factorielle, on obtient les termes 3 ; 6 ; 720.
   Maple nous a par ailleurs confirmé que [latex]720! < exp(exp(exp(3)))[/latex].

   Personnellement, j'étais arbitrairement partisan de la factorielle, mais en voyant la valeur de [latex]720![/latex] par rapport à celle de [latex]exp(exp(exp(3)))[/latex], j'ai été un peu déçu... Mais bon, peu importe ! Sauriez-vous montrer une inégalité entre les deux suites ? Nous, on est perdus !

Alexein41



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 04-10-2012 12:56:16

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,472E+3

Quand un problème édgénère...

Je déteste ces problèmes sans solution... Parce que en considérant l'infini et avec cette méthode (exp(exp(exp(x))) ou autre, on a toujours infiniment plus de chance de trouver la porte dans le reste de l'infini que dans la "relativement"courte portion parcourue.

Encore un sujet qui va faire parler des heures...

 #3 - 04-10-2012 13:08:29

gilles355
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 416

quand un problèle dégénère...

Non mais là je pense que le problème se résume à savoir si c'est la suite U ou V la plus rapide

En gros qui est le plus grand entre
((((((a!)!)!)!)!)...)! et exp(exp(exp(exp(...(exp(a))))))...)

 #4 - 04-10-2012 18:30:34

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

quand un problème défénère...

Pour [latex]a > 5[/latex], on peut montrer que [latex]u_n[/latex] devient négligeable devant [latex]v_n[/latex],

c'est-à-dire que [latex]\frac {u_n} {v_n}[/latex] tend vers 0.

1) Tout d'abord, on montre par récurrence que [latex]\frac {e^n} {n!} < \frac 1 {2^{n-6}}[/latex] pour tout entier naturel [latex]n \geq 6[/latex]

initialisation : [latex]e^6 < 6![/latex]

hérédité : si [latex]\frac {e^n} {n!} < \frac 1 {2^{n-6}}[/latex], alors
[TeX]\frac {e^{n+1}} {(n+1)!} = \frac e {n+1} \times \frac {e^n}{n!} < \frac 12 \times \frac 1 {2^{n-6}} = \frac 1 {2^{n+1-6}}[/TeX]
2) Notons que cela implique que [latex]e^n < n![/latex] pour [latex]n \geq 6[/latex]

3) On montre par récurrence que la suite [latex](v_n)[/latex] est strictement croissante et minorée par 6.

En effet, [latex]v_{n+1}-v_n = v_n! - v_n = v_n \times ((v_n-1)! - 1)[/latex]

4) On montre par récurrence que [latex]v_n \geq u_n[/latex].

hérédité : La suite [latex](v_n)[/latex] étant minorée par 6, si [latex]v_n \geq u_n[/latex], alors
[TeX]v_{n+1}=v_n!>e^{v_n}\geq e^{u_n}=u_{n+1}[/latex].

5) Ainsi, [latex]\frac {u_{n+1}} {v_{n+1}} = \frac {e^{u_n}} {v_n!} \leq \frac {e^{v_n}} {v_n!} \leq \frac 1{2^{v_n-6}} [/TeX]
6) La suite [latex](v_n)[/latex] est strictement croissante et entière donc elle tend vers [latex]+ \infty[/latex]

7) On obtient le résultat énoncé lorsque n tend vers [latex]+ \infty[/latex]


Restent à voir les cas a=3, a=4 et a=5...

 #5 - 04-10-2012 18:33:26

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

Quand un problèmee dégénère...

Il vaut mieux en effet en rester à la comparaison entre les 2 expressions, car il est clair que la porte est introuvable et inaccessible. D'ailleurs, l'emplacement où on se trouve au départ est nulle part, et la porte aussi est nulle part.
Et ma foi, factorielles ou exponentielles, c'est rien du tout en comparaison de l'infini. Le fini mesurable, ou le mesurable, n'a aucune valeur par rapport à l'infini.
Rapport 720!/infini=0

 

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 : Pim, Pam et ?

Sujets similaires

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