[Maths] Marathon de problèmes

Au début j’étais parti pour trouver un pattern ou à utiliser Legendre en regardant : $v_5((2^n)!)$, mais en fait on peut juste utiliser les critères de divisibilité de base pour prouver ça.

Un entier est divisible par $2^n$, si et seulement si ses $n$ derniers chiffres sont divisibles par $2^n$.

Donc ou bien : $\overline{a_i \ldots a_1} = 0$, ou $\overline{a_i \ldots a_1} \geq 2^n$.

Ici, on s’intéresse aux entiers de la forme $2^k$, donc puisque clairement : $v_5(2^k) = 0$, alors le premier cas est exclu. On se retrouve donc dans le deuxième cas.

Maintenant l’idée c’est de remarquer que si : $S(2^k) \leq M$, alors on peut trouver des suites de $0$ consécutifs de plus en plus grande dans l’écriture décimal de $2^k$. Or, c’est impossible au vu de ce qu’on a dit précédemment. Effectivement, on peut à partir d’un certain rang prendre une puissance de $2$ strictement supérieur à : $10^n$. Cette puissance de deux à donc un exposant qui est minorée par $4n$. Dans ce cas, on a au moins un chiffre non nul dans l’écriture décimal de $2^k$ tronquée au $n+1$-ième chiffre.

Bref, on ne peut pas avoir cette majoration par $n$, et on a même une infinité d’intervalles de la forme : $[1, 3], ..., [4^{n-1}, 4^n-1]$ dans lesquelles on trouve un chiffre non nul, donc clairement la suite converge vers $+\infty$.

L’idée de la preuve, c’est donc d’utiliser le critère de divisibilité et le fait que : $2^{un} > 10^n$ pour tout $u \geq 4$. Donc en prenant, $u = 4$, on peut trouver des intervalles dans lesquelles on trouve un chiffre non nul.

Ok, j’ai compris ce que tu fais. Par contre, je pense que tu t’es un peu trompé dans les détails. Il faut considérer une suite d’exposants $(n_i)_{i∈ℕ}$ telle que $2^{n_{i+1}}$ a un nombre de chiffres supérieur à $n_i$ non ? La suite $(4i)_{i∈ℕ}$ ne satisfait pas ça mais c’est facile de voir que ça existe. edit Ah oui mais ok, c’était la suite $(4^i)_{i∈ℕ}$ que tu considères, je me suis trompé. C’est bon.
Dans ce que j’ai fait, on commence par remarquer que le dernier chiffre est non nul. On suppose qu’il existe $M∈ℕ$ tel qu’on peut trouver des $k$ arbitrairement grands tels que le nombre de chiffres non nuls de $2^k$ soit inférieur à $M$. Je n’ai pas fait les détails mais on obtient un $2^k$ tel que dans ses chiffres, il y a un trou (des zéros consécutifs) très grand par rapport au nombre de chiffres qui sont moins significatifs que les chiffres du trou. La conséquence est que quand on va diviser par $2$ de manière répétée, le trou va mettre trop de temps à être « traversé » par les chiffres (lors d’une division par $2$, les chiffres n’influent pas plus loin que le précédent car $1/2 = 0.5$). Du coup, les chiffres moins significatifs que le trou vont être trop divisés par $2$ (et donner des décimales après la virgule) avant que l’influence des autres chiffres ne les atteigne. Ouais bon… c’est probablement pas du tout clair mais c’est chiant à rédiger précisément en fait…
On peut obtenir un minorant sur le nombre de chiffres non nuls de $2^n$ par les deux méthodes (probablement très large). C’est possible qu’on obtienne la même borne, les raisonnements semblent quand même assez similaires.

Si on prend un rectangle et un ensemble de disques le recouvrant, on peut reproduire cette figure 4 fois, les placer selon un rectangle de même rapport d’aspect que le rectangle de départ, et finalement appliquer une homothétie de facteur 1/2. On aura alors un rectangle identique au rectangle initial, mais couvert avec 4 fois plus de disques de rayon deux fois plus petits.

Soit $C_b := \{0,…,b-1\}$ l’ensemble des chiffres en base $b$. On tire deux éléments uniformes de $(C_b)^n$ notés $u$ et $v$. Il y a une retenue si et seulement si il existe $i$ entre $1$ et $n$ tel que $u_i + v_i ≥ b$. Par indépendance, la probabilité de ne pas avoir de retenue est la probabilité de ne pas avoir de retenue pour un seul chiffre élevée à la puissance $n$. Cette probabilité est $\frac{b^2 + b}{2 b^2} = \frac{1 + 1/b}{2}$. La réponse à la question est donc $1 - \left(\frac{1+1/b}{2}\right)^n$.

Intuitivement, si la probabilité p est supérieure à 0.5, il faut faire ’tapis’. On a une |probabilité supérieure à 50% de faire le score maximum, et donc de gagner (ou match nul |si l’adversaire choisit la même stratégie et gagne le maximum de jetons).|

Si ma probabilité p est inférieure à 0.5, il ne faut pas faire tapis. En faisant tapis, |on aurait une probabilité supérieure à 50% de finir avec 0 jeton, et donc de perdre, |quelque soit la stratégie de l’autre joueur. Mais il faut faire quoi ?

Je joue un seul jeton., uis encore un seul jeton et encore un seul jeton … A priori, |mon adversaire joue come moi, parce que lui aussi à réfléchi. Si à un moment, je |considère que j’ai eu très peu de chance (par exemple au bout de 20 jetons, je n’ai eu |aucun coup gagnant, alors que la probabilité théorique est de 40% de gain à chaque |lancer), alors je pense que j’ai un retard significatif, je n’ai plus de chance de gagner |avec cette stratégie, et je dois donc faire tapis.

Reste à trouver la bonne formule pour définir quand il faut basculer de la stratégie 1 à |la stratégie 2.

Et même, si on a beaucoup de jetons au départ, la stratégie parfaite est probablement de |jouer 1 jeton à la fois au début, puis 2 jetons à la fois si on a un retard significatif, |puis 3 à la fois…

Si on a 1000 jetons au départ, si p vaut 40%, et si au bout de 100 jetons joués, j’ai |gagné seulement 25 points, je suis 15 points en retard par rapport à l’espérance normale. |En jouant 1 pion par 1 pion, je joue la stratégie qui donne une très faible variance, je |me donne peu de chances de faire plus de 40% sur les 900 pions restants. En jouant les |pions 5 par 5 ou 10 par 10, l’espérance est la même, mais la variance est plus élevée, |j’augmente donc mes chances de rattraper mon retard.

Intuitivement, si la probabilité p est supérieure à 0.5, il faut faire ’tapis’. On a une probabilité supérieure à 50% de faire le score maximum, et donc de gagner (ou match nul si l’adversaire choisit la même stratégie et gagne le maximum de jetons).

À peu près oui, mais il faut faire attention au fait que l’autre stratégie peut aussi gagner tous les points (il y a en fait trois issues possibles : gagner, perdre ou partie nulle). Il est possible de trouver une valeur de $p$ (qui est strictement supérieure à 1/2) à partir de laquelle aucune stratégie ne bat cette consistant à tout miser.

Je joue un seul jeton., uis encore un seul jeton et encore un seul jeton … A priori, mon adversaire joue come moi, parce que lui aussi à réfléchi. Si à un moment, je considère que j’ai eu très peu de chance (par exemple au bout de 20 jetons, je n’ai eu aucun coup gagnant, alors que la probabilité théorique est de 40% de gain à chaque lancer), alors je pense que j’ai un retard significatif, je n’ai plus de chance de gagner avec cette stratégie, et je dois donc faire tapis.

Déjà, quand on dit « gagner », ça dépend contre quelle autre stratégie, et en plus on veut maximiser ses chances de gagner, bref c’est un peu complexe. En faisant ce que tu dis, on va être battu par une stratégie qui continue à miser un par un jusqu’à la fin (si $p<1/2$), pour la même raison que l’on a plus intérêt à miser un par un au début.

Et même, si on a beaucoup de jetons au départ, la stratégie parfaite est probablement de jouer 1 jeton à la fois au début, puis 2 jetons à la fois si on a un retard significatif, puis 3 à la fois…

Il est possible a priori qu’il n’y ait pas de stratégie parfaite. C’est pour ça que je parlais de phénomènes non transitifs. Je ne suis pas convaincu par ce que tu dis car une stratégie battant la stratégie « tout miser » pour $p$ compris entre 0 et une valeur critique fait un peu le contraire…

Si on a 1000 jetons au départ, si p vaut 40%, et si au bout de 100 jetons joués, j’ai gagné seulement 25 points, je suis 15 points en retard par rapport à l’espérance normale. En jouant 1 pion par 1 pion, je joue la stratégie qui donne une très faible variance, je me donne peu de chances de faire plus de 40% sur les 900 pions restants. En jouant les pions 5 par 5 ou 10 par 10, l’espérance est la même, mais la variance est plus élevée, j’augmente donc mes chances de rattraper mon retard.

Mais tu augmentes aussi tes chances de creuser ton retard. Bref c’est pas clair. De toute manière il faudra bien faire des calculs quelque part si on veut dire quelque chose.

Déjà, chaque stratégie (pour un nombre de jetons $n$ fixé) peut être représentée sous forme d’arbre binaire entier étiqueté par des entiers positifs et tel que la somme sur chaque chemin menant de la racine à une feuille soit $n$.