[Maths] Marathon de problèmes

a marqué ce sujet comme résolu.

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.

Prouver que sur un échiquier de dimension $4 \times n$ ($n \geq 1$), il n’existe pas de parcours fermé d’un cavalier qui passe par chaque case une fois et une seule (sauf la première puisqu’on veut y revenir).

Banni

Salut !

Pour ta solution :

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.

+1 -0
Banni

@InaDeepThink J’ai perdu patience pour chercher la réponse à ton énigme et j’ai regardé sur wikipédia. :( Désolé. Il me manquait une idée intéressante et j’aurais dû persévérer… mais comment savoir à l’avance ? ^^ Je ne sais pas si quelqu’un va trouver mais comme on avait dit limite de 2 jours, peut-être que tu peux donner la réponse qu’on passe à une autre énigme ?

+1 -0

Ça veut dire quoi "couvrir" un rectangle avec des cercles ? Instinctivement, il me vient à l’idée que ça veut dire que tu paves le rectangle avec des carrés et que les disques sont simplement les disques inscrits dans ces carrés. Si c’est ça, c’est trop trivial et du coup je me dis que j’ai raté un truc.

@adri1 Pour moi ça veut plutôt dire :

Si on note $C$ l’ensemble des points à l’interieur du rectangle (bordure incluse ).

Et si tu notes $c_i$ l’ensemble des points à l’interieur Du $i$-eme cercle (en prenant aussi la bordure).

Alors couvrir veut dire que :

$$C \subseteq \bigcup_{i=1}^{200}c_i$$
+0 -0

@adri1.

Blo yhg Parle de disques, et non de cercles. Le cercle, c’est le périmètre du disque.

Tu as un rectangle de papier, de couleur noire. Tu as 100 pièces de monnaies (d’épaisseur nulle de préférence). Tu disposes ces 100 pièces sur le rectangle, de façon à ce qu’on ne voie plus le moindre point noir.

Si tu peux le faire, alors selon l’énoncé de l’exercice, tu peux aussi couvrir le même rectangle avec 400 pièces de rayon 2 fois plus petit.

OK, je vois un peu mieux l’intérêt de la question même si la réponse est toujours très simple.

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.

+0 -0
Banni

Salut,

@adri1 Oui, c’est bien la réponse attendue. Elle est simple en effet. Le problème qui peut survenir est d’avoir l’idée dans « le mauvais sens » et d’essayer de couvrir chaque disque du recouvrement initial par des disques de rayon 1 (en tout cas c’est c’est ce que j’ai essayé en premier).

edit À toi de poster une énigme si tu veux.

+0 -0

Dans un registre un peu différent, assez classique.

On considère deux nombres entiers de $n$ chiffres en base $b$ (les premiers chiffres peuvent être des zéros). Quelle est la probabilité d’avoir au moins une retenue lorsqu’on ajoute ces deux nombres? (On considère que les nombres ont été tirés au hasard de façon homogène dans $[0, b^n-1]$).

+4 -0
Banni

Voici ma réponse pour le problème de adri1.

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$.

Banni

Ok, voici un autre problème (que j’ai inventé).

On considère le jeu suivant à deux joueurs. Chaque joueur dispose à l’origine de $n$ jetons. Soit $p ∈ [0,1]$ un paramètre. Chaque joueur joue de manière indépendante et à la fin, celui qui a le plus grand score gagne. Voici le déroulé :

  1. Choisir un nombre $k$ de pions et les placer sur le plateau.
  2. Avec une probabilité $p$, on gagne autant de points qu’on a misé de pions. Les pions sont détruits.
  3. S’il reste des pions, on revient en 1.

La stratégie A consiste à tout miser d’un coup. La stratégie B consiste à miser ses pions un par un.
Déterminer, en fonction de $p$, quelle stratégie l’emporte sur l’autre.

Bonus : étudier d’autres stratégies. Y a-t il des phénomènes non transitifs ? Que se passe-t il si, lorsque le joueur gagne des points à l’étape 2, les pions sont récupérés ?

+2 -0
Banni

@Skodt : Les pions qu’on a misés sont retirés du jeu. C’est-à-dire que le joueur ne peut pas les rejouer à un autre tour. Ça répond à la question ?

@melepe : Les deux joueurs jouent de manière indépendante. On ne gagne que les pions qu’on a misés soi-même.

+0 -0

Les 2 joueurs jouent de façon indépendante. Donc quand le joueur 2 joue, il n’a pas connaissance de la stratégie adoptée par le joueur 1.

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.

Banni

@elegance

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$.

J’ai fait un code Python pour tester les stratégies.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from random import random

class Checker:
  def __init__(self,n,p):
    self.n = n
    self.p = p
    self.nonplayed = n
    self.played = 0
    self.score = 0
  
  def play(self,m):
    if m > self.nonplayed:
      m = self.nonplayed
    self.score += int(random() < self.p) * m
    self.played += m
    self.nonplayed -= m

def play_game(strat,n,p):
  ch = Checker(n,p)
  strat(ch)
  return ch.score

def prob_win(stratA, stratB, n, p, *, nb_tries=10**5):
  nb_gt = 0
  nb_eq = 0
  nb_lt = 0
  for _ in range(nb_tries):
    sa = play_game(stratA,n,p)
    sb = play_game(stratB,n,p)
    if sa > sb:
      nb_gt += 1
    elif sa == sb:
      nb_eq += 1
    elif sa < sb:
      nb_lt += 1
  return (nb_gt/nb_tries, nb_eq/nb_tries, nb_lt/nb_tries)

def stratA(checker):
  checker.play(checker.n)

def stratB(checker):
  for i in range(checker.n):
    checker.play(1)

print(prob_win(stratA, stratB, 100, 0.3))
+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte