![](/img/vague-bas-gauche.png) |
Résumé de la discussion
- Alexein41
- 04-10-2012 00:04:58
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
|
![](/img/vague-haut-droite.png) |