Questions en apparences simples

maxbe

Bonjour

Voici deux questions pour lesquelles l'énoncé est simple et accessible à tous (de type olympiade) mais pour lesquelles trouver la solution est une tout autre affaire  . Elles m'ont été envoyées par un ami à moi et le seule indice qu'il m'ait donné est qu'il peut être utile de considérer l'élément dont une caractéristique est minimale ou maximale.

1. Soit P l’ensemble de tous les nombres d’au plus 100 chiffres s’écrivant uniquement avec des 0 et des 1. Montrer que la somme des réciproques des nombres appartenant à P n’est pas un nombre entier.
2. Une sauterelle se trouve sur la droite réelle à la position 0. Elle saute de nombre entier en nombre entier et chaque nombre est atteint exactement une fois. Montrer qu’au moins un des sauts à une longueur plus grande ou égale à 100.
Pour la première, il est évident que cette somme sera contenue dans l'intervalle ouvert ]1,2[, mais comment montrer cette borne supérieure ?
Tout aide/indices est/sont les bienvenus.
Merci ! 

Homo Topi

Les énoncés de ce genre sont parfois fascinants de par leur aspect "formulation simple mais résolution très compliquée". Le théorème de Fermat-Wiles ou le théorème de Jordan sur les courbes fermées simples planes sont des exemples célèbres de ça.

Je reformule la 2 en : montrer que pour toute bijection $f:\N\longrightarrow\Z$, il existe $n\in\N$ tel que $|f(n+1)-f(n)|\geqslant 100$. Le $100$ ici devrait être purement artificiel et on devrait pourvoir le remplacer par n'importe quel entier naturel.

Math Coss

Réciproque = inverse ?
Pour la sauterelle, qu'est-ce qui l'empêche de faire des sauts de $1$ ? Ah, parce que "chaque nombre" désigne "chaque entier relatif" ?

maxbe

Math Coss a dit :

Réciproque = inverse ?

réciproque de x = 1/x

maxbe

Homo Topi a dit :

Je reformule la 2 en : montrer que pour toute bijection $f:\N\longrightarrow\Z$, il existe $n\in\N$ tel que $|f(n+1)-f(n)|\geqslant 100$. Le $100$ ici devrait être purement artificiel et on devrait pourvoir le remplacer par n'importe quel entier naturel.

Je m'étais effectivement fait la même remarque, mais cela ne m'aide pas beaucoup ...

Math Coss

Pour la première, il y a $2^k$ nombres à $k+1$ chiffres formés de 0 et de 1 ; ils sont plus grands que $10^k$. La somme est donc plus petite que $\sum_{k\ge0}(2/10)^k=1/(1-2/10)=5/4$. Sauf erreur...

Homo Topi

@Math Coss c'est un peu obligé de désigner $\Z$ si on veut en faire un exercice car avec $\N$ tu as vu immédiatement que c'est trivialement faux.

@maxbe Techniquement, si, ça peut nous aider, mais il faut creuser un peu. Si la sauterelle ne fait que des sauts de longueur $99$ ou moins, il faut trouver une contradiction, d'où l'intérêt de chercher avec des nombres inférieurs à $100$ pour se faire une idée de ce qu'il se passe.

maxbe

Math Coss a dit :

Pour la première, il y a $2^k$ nombres à $k+1$ chiffres formés de 0 et de 1 ; ils sont plus grands que $10^k$. 

Que veut tu dire par "ils sont plus grands que 10^k" ?

Math Coss

Pour la deuxième, à partir d'un certain nombre de sauts, la sauterelle sera passée sur tous les entiers de $0$ à $100$. À ce stade, il lui restera à visiter au moins un entier $>100$ et un $<0$ (et en fait une infinité bien sûr). Pour aller de l'un à l'autre, elle fera nécessairement un saut de plus de $100$ dans un sens ou dans l'autre. 

maxbe

Homo Topi a dit :

@maxbe Techniquement, si, ça peut nous aider, mais il faut creuser un peu. Si la sauterelle ne fait que des sauts de longueur $99$ ou moins, il faut trouver une contradiction, d'où l'intérêt de chercher avec des nombres inférieurs à $100$ pour se faire une idée de ce qu'il se passe.

Aurait tu as un exemple pour des sauts plus petits ?

maxbe

Math Coss a dit :

à partir d'un certain nombre de sauts, la sauterelle sera passée sur tous les entiers de $0$ à $100$.

Oui je m'en doute, mais comment le montrer ...

Homo Topi

MC a donné l'idée, il n'a pas rédigé la solution détaillée mais en gros c'est ça. Il reste à justifier proprement pourquoi ce qu'il dit est vrai. EDIT :  je parle du passage "à partir d'un certain nombre de sauts, la sauterelle sera passée sur tous les entiers de $0$ à $100$".

Voilà avec $3$ au lieu de $100$ (donc, sauts de $1$ ou $2$ autorisés) : tu pars de $0$. Tu as $4$ choix : aller en $1$, $-1$, $2$ ou $-2$. Si tu dessines un arbre des chemins possibles, tu vas vite trouver sur chaque branche que la seule manière de garder ta bijection est de faire un saut de $3$. J'en fais une : si tu commences par aller en $1$, ensuite. Si tu vas en $2$, tu devras faire un saut de au moins $3$ pour atteindre $-1$, et si tu vas en $-1$, tu devras faire un saut de au moins $3$ pour aller en $2$.

Avec $100$, ton arbre est juste beaucoup plus grand mais le concept est le même. D'ailleurs je suis assez convaincu que ce problème se modélise avec des marches aléatoires, même si je ne sais plus très bien faire ça.

Médiat_Suprème

Ça c'est évident  f est une bijection , il suffit de regarder le max de $f^{-1}([0; 100])$ qui est fini.

Math Coss

J'allais écrire à partir du rang $\max\bigl\{f^{-1}(k)\mid 0\le k\le100\bigr\}$, si $f(n)$ désigne l'endroit où est la sauterelle au temps $n$.

Médiat_Suprème

Les grands esprits ... 

maxbe

Merci pour votre aide, tout est clair désormais  .

JLapin

Pourrais-tu (toi ou la modération) remettre le message initial ?

Merci d'avance.