Jouons avec les divisions euclidiennes
dans Arithmétique
Voici les règles du jeu:
On fixe un nombre entier positif $R_0$. Chaque joueur choisit un nombre $0<R_1<R_0$. On définit alors la suite des divisions euclidiennes et on note les restes $R_k$.
Le gagnant est celui qui obtient la meilleure somme $\sum R_k$.
En tâtonnant on arrive à obtenir quelques bons candidats pour $R_1$ mais je n'arrive pas à déterminer s'il existe une méthode pour déterminer $R_1$ afin d'obtenir le meilleur résultat.
Al-Kashi
On fixe un nombre entier positif $R_0$. Chaque joueur choisit un nombre $0<R_1<R_0$. On définit alors la suite des divisions euclidiennes et on note les restes $R_k$.
Le gagnant est celui qui obtient la meilleure somme $\sum R_k$.
En tâtonnant on arrive à obtenir quelques bons candidats pour $R_1$ mais je n'arrive pas à déterminer s'il existe une méthode pour déterminer $R_1$ afin d'obtenir le meilleur résultat.
Al-Kashi
Réponses
-
En testant informatiquement toutes les premières valeurs de $R_0$, il semblerait que le $R_1$ qui maximise la somme est toujours compris entre $\alpha R_0-1$ et $\alpha R_0 + 2$, avec $\alpha = \dfrac{\sqrt{5}-1}{2}\approx 0.618$.
-
Joli Guego(tu). Même si cela est de l'ordre de la conjecture, je ne pensais vraiment pas que la valeur $R_1$ pouvait être aussi bien ciblée.
Voilà qui devrait bien faire cogiter maintenant pour tenter de justifier cette conjecture.
Al-Kashi -
Je pense que c'est lié au fait que la suite de Fibonacci réalise les plus petits restes possibles pour une longueur donnée de l'algorithme d'Euclide (ce qui au passage permet de donner la complexité au pire cas de ce dernier).
-
Il peut y avoir plusieurs valeurs de $R_1$ qui conviennent, par exemple $R_1\in \{23,24\}$ pour $R_0=38$.
Pour $R_0=1975$ on a $R_1=1219$ et $\alpha R_0\simeq 1220,6$.
Pour $R_0=2056$ on a $R_1=1269$ et $\alpha R_0\simeq 1270,6$.
Il semble que la somme optimale $R_1+R_2+\cdots$ soit toujours inférieure à $(\alpha+1)R_0$.
P.S. On peut aussi avoir $2<R_1-\alpha R_0<3$, par exemple $R_0=53574$ et $R_1=33113$. Ci joint le graphe de $R_1-\alpha R_0$ où on a pris pour $R_1$ la plus petite valeur qui convient.
P.P.S. 1) Il semble que la plus petite valeurs de $R_1$ qui convient vérifie $-2\leqslant R_1-[\alpha R_0] \leqslant 2$ où $[x]$ désigne l'entier le plus proche de $x$, en tout cas c'est apparemment vrai pour $R_0<500000$.
2) Les valeurs de $R_1$ qui conviennent ne sont pas toujours consécutives, par exemple pour $R_0=40$ on a $R_1=25$ ou $R_1=29$.
3) Pour $R_0=6$, il y a trois valeurs de $R_1$ qui conviennent. -
Merci pour toutes ses informations supplémentaires.
Du coup on s'intéresse au plus petit des $R_1$ qui maximise la somme.
J'ai continué à chercher mais j'ai encore vraiment du mal à trouver ne serait-ce qu'un angle d'attaque pour aborder la conjecture.
Al-Kashi -
Guego a dit 2 choses, il a dit que le ratio était environ 0.618, et il a dit que c'était $\dfrac{\sqrt{5}-1}{2}$
Le ratio R1/R0 est proche de 0.618, mais les ratios suivants aussi ( R2/R1 etc)
On cherche donc R1 tel que :
R1/R0 = R2/R1
et R1+R2 = R0
R1 est donc solution de l'équation R1² + R1.R0 - R0² = 0 , ce qui nous amène à notre $\alpha = \dfrac{\sqrt{5}-1}{2}$
...bon, il y a 1 ou 2 petites impasses dans le raisonnement, mais c'est forcément la bonne piste.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Je ne sais pas démontrer cette conjecture mais je peux démontrer quelque chose de plus faible.
Si $1\leqslant b\leqslant a$, notons $f(a,b)$ la somme $a_1+a_2+a_3+\cdots$ où $a_0=a$, $a_1=b$, etc. sont les restes des divisions Euclidiennes lorsque l'on applique l'algorithme d'Euclide à $(a,b)$. Soit $\alpha=\dfrac{-1+\sqrt{5}}{2}$. On montre par récurrence que
1) Si $b< \alpha a$ alors $f(a,b)<(\alpha+2) b$.
2) Si $b>\alpha a$ alors $f(a,b)\leqslant -(\alpha+1)b+(\alpha+2)a$
(et donc $f(a,b)<(\alpha+1)a$).
En effet, dans le premier cas on écrit la division Euclidienne $a=bq+r$. On a $f(a,b)=b+f(b,r)$. Or, $f(b,r)<(\alpha+1)b$ par hypothèse de récurrence, donc $f(a,b)<(\alpha+2)b$.
Dans le deuxième cas, la division Euclidienne de $a$ par $b$ s'écrit $a=b+(a-b)$. On écrit la deuxième division Euclidienne $b=(a-b)q+r$. On a $f(a,b)=b+(a-b)+f(a-b,r)\leqslant a+(\alpha+1)(a-b)=-(\alpha+1)b+(\alpha+2)a$.
La conjecture revient à montrer que $\max_b f(a,b)$ est atteint en au moins un point $b_0$ tel que $|b_0-[\alpha a] |\leqslant 2$. Ca m'a l'air difficile, mais je pense qu'on peut espérer montrer que $\dfrac{f(a,[\alpha a])}{a}$ tend vers $\alpha+1$ quand $a$ tend vers l'infini, ce qui prouverait que $\dfrac{R_1}{R_0}$ tend vers $\alpha$ lorsque $R_0$ tend vers l'infini. -
Il y a des accidents de parcours.
Prenons $R_0 = 53316291175$
$R_0 * \alpha = 32951280100,2361$ qu'on arrondit à 32951280100
Mais, pas de chance, 53316291175 et 32951280100 ne sont pas premiers entre eux, et leur PGCD est même très grand : 75025
Du coup, la chaîne commençant par (53316291175, 32951280100 ...) finit par (... 300100, 225075, 75025)
Gros gâchis.
A cause de cet accident de parcours, on obtient un meilleur résultat en commençant par (53316291175, 32951280101 ...) (pgcd=1)Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Noter que pour $R_0=499422$ et $R_1=[\alpha R_0]=308660$ le PGCD vaut $506$, et pourtant le résultat est meilleur qu'avec $R_1=308659$ bien que $R_0$ et $308659$ soient premiers entre eux.
-
Je te rejoins JLT sur le fait que cela doit être difficile. De mon côté pas grand chose, juste le résultat assez simple suivant:
Notons le dernier reste $R_m=0$ et $Q_k$ le quotient de $R_{k-1}$ par $R_k$.
On prouve aisément l'identité suivante:
$$\sum_{k=1}^{m-1} R_kQ_k=R_0+R_1-R_{m-1}$$
On en déduit alors que :
$$\sum_{k=0}^{m-1} R_k \leq 2R_0+R_1-R_{m-1}$$
Al-Kashi -
Petit complément : notons $F_0=0$, $F_1=1$, $F_2=1,\ldots$ la suite de Fibonacci. Soient $0<b<a$ des entiers et $n\in \N^*$. Supposons que $\frac{b}{a}$ soit compris entre $\dfrac{F_{n-1}}{F_n}$ et $\dfrac{F_n}{F_{n+1}}$.
(N.B. On a $\dfrac{F_{n-1}}{F_n}<\dfrac{F_n}{F_{n+1}}$ si et seulement si $n$ est impair.)
Si $R_0=a$, $R_1=b$, alors la suite des premiers restes $R_k$ pour $0\leqslant k\leqslant n$ vérifie $R_{k-2}=R_{k-1}+R_k$ pour $2\leqslant k\leqslant n$. On a de plus $R_k=(-1)^kF_{k-1}a+(-1)^{k-1}F_kb$.
On a donc, avec mes notations d'un message précédent, $f(a,b)\geqslant R_1+\cdots+R_n=a+b+(-1)^n(F_{n-2}a-F_{n-1}b)$. Or, $|F_{n-2}a-F_{n-1}b|<\frac{a}{F_n}$ donc
$$f(a,b)>a+b-\frac{a}{F_n}.$$
On en déduit en particulier que si $(b_k)$ est une suite telle que $\frac{b_k}{k}\to\alpha$, alors $f(k,b_k)\sim (\alpha+1)k$ lorsque $k\to \infty$. On peut même préciser que $\max_b f(a,b)\geqslant (\alpha+1)a-O(\sqrt{a})$. -
JLT écrivait:
> On peut même préciser que $\max_b
> f(a,b)\geqslant (\alpha+1)a-O(\sqrt{a})$.
???
pour tout b, $f(a, b) < a$
Je ne vois pas comment on peut avoir $f(a, b) > a$, pour a suffisamment grand.
De mon côté, je me suis limité aux $R_0$ premiers, et relativement grands. Et j'ai regardé l'indicateur $k_i = R_i/R_{i+1} - \frac{1}{\alpha}$
J'affirme différentes choses. Certaines de ces affirmations sont démontrables (notées (D)), d'autres sont des conjectures, notées (ND).
Peu importe le nombre $R_1$ choisi, cette suite est alternativement positive et négative. (D)
Et le début de ces 2 sous suites est 'proche' d'une suite géométrique de raison 6.854. (D)
La demi-suite qui est intéressante, c'est la demi-suite positive.
Et le seuil intéressant , c'est quand cette demi-suite atteint $2- \frac{1}{\alpha}$ , autrement dit ; quand le rapport $\frac{R_i}{R_{i+1}}$ atteint 2.
Tant qu'on atteint pas ce seuil, la somme des restes, c'est la somme des $R_i - R_{i+1}$ .... donc cette somme tend vers \$R0$
Quand on atteint le ratio de 2, Le reste n'est plus $R_i - R_{i+1}$ , mais $R_i - 2* R_{i+1}$
Plus cet événement arrive tard, plus on a des chances d'avoir une somme élevée. (ND)
Concrètement, ça veut dire quoi.
Si $R_0$ est premier, on calcule $R_0 * \alpha$ , et on retient les 2 candidats utiles, les 2 entiers qui entourent ce nombre réel, qu'on va noter $A_1$ et $B_1$
On calcule $A_2$ et $B_2$ :: $A_2 = R_0 - A_1$ et $B_2 = R_0 - B_1$
On calcule $R_0/A_1$ ,, et $A_1/A_2$ ; l'un de ces 2 nombres est plus grand que $\frac{1}{\alpha}$ , on garde ce nombre. ratio_A
Idem pour $R_0/B_1$ ,, et $B_1/B_2$ ; l'un de ces 2 nombres est plus grand que $\frac{1}{\alpha}$ , on garde ce nombre ratio_B
Si ratio_A est plus petit que ratio_B, on va garder A1, et sinon, on va garder B1
Exemple :
R0=7493833
R0* \alpha = 4631443,50001559
Si on prenait un arrondi, on choirait R1=4631444 mais en fait, 4631443 va donner un meilleur résultat, pour la raison décrite ci-dessus. .Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Relis ma définition de f(a,b), c'est la somme des restes $R_1+R_2+\cdots$ par exemple f(5,3)=6.
-
On peut aussi se regarder ce qu'il se passe avec $R_0$ très grand, c'est-à-dire qu'on considère $x_0 = 1$, $x_1 \in \left]0,1\right[$ et on définit $x_{n+2}$ comme le reste de la division de $x_n$ par $x_{n+1}$ : c'est le réel de la forme $x_n - k x_{n+1}$ compris entre $0$ et $x_{n+1}$. On regarde ensuite la somme $\sum_n x_n$. Voici le graphique qu'on obtient, ainsi qu'un zoom autour de $\alpha$. Désolé, c'est assez imprécis, il y a des imperfections dans le dessin joint qui ne devraient pas y être.
-
J'ai redessiné en bleu le graphe de Champ-Pot-Lion, qui correspondent à mettre en abscisse $\frac{b}{a}$ et en ordonnées $1+\frac{f(a,b)}{a}$ pour $a$ très grand, ainsi que les deux segments en rouge d'équation $y= 1+(\alpha+2)x$ et $y=(\alpha+3)-(\alpha+1)x$ correspondant aux deux inégalités http://www.les-mathematiques.net/phorum/read.php?5,1751896,1752100#msg-1752100 ci-dessus.
Je préfère travailler avec la fonction $S(x)=\lim_{a\to\infty}\frac{f(a,[xa])}{a}$. On a $S(x)=x+xS(\{\frac{1}{x}\})$ où $\{\cdot\}$ désigne la partie fractionnaire. La fonction de Champ-Pot-Lion est $S+1$. Je pense que les points de continuité de $S$ sont les irrationnels. -
-
L'exemple tracé correspond à $R_0=300$. La droite rouge correspond à la droite d'équation $R_0+x$ et la droite verte à $2R_0$.
On remarque que les "points bas" proches de la droite rouge sont simples à caractériser. Ce sont grossièrement les points $R_1=\Big\lfloor\dfrac{R_0}{k}\Big\rfloor$ où $k\in\N^*$. On a alors grossièrement une somme qui vaut $R_0+\dfrac{R_0}{k}$. Ainsi les "points bas" sont croissants.
Il faudrait peut être tenter de réussir à caractériser les "points hauts" et ensuite espérer prouver que cette suite est croissante puis décroissante avec un maximum aux environs de $\alpha R_0$.
Avez-vous une idée à ce propos JLT et Champ-Pot-Lion à partir de vos graphiques?
Al-Kashi -
Allez, ça me semble tellement difficile, je vais le classer dans mes problèmes ouverts pour l'année 2019.
Al-Kashi -
On pourra ajouter en parallèle Le produit $\prod R_k$ qui il me semble jouit de la même propriété.
Al-Kashi -
@Guego et @JLT
Bonjour,
Je voudrais me lancer sur une conjecture un peu plus faible vu la complexité du problème.
A partir des programmes que vous avez implémentés, pourriez-vous me dire si la conjecture suivante tient le coup pour de grands nombres:
Conjecture:
On note $(F_n)_{n\in\N}$ les valeurs de la suite de Fibonacci.
Soit $n\ne2$.Si $R_0=F_n$ alors la somme $\sum\R_k$ est maximale pour $R_1=F_{n-1}$.
En vous remerciant,
Al-Kashi -
La conjecture est exacte.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
-
Et pour aller plus loin , Si x est un élément de la suite de Fibonacci 'standard' (celle commençant par 1,2) alors La somme optimale S(x) = x-2
Et ça se généralise :
Si on regarde la suite de Fibonacci commençant par (1,i, 1+i ... ...), si x est un élément de cette suite, alors la somme optimale S(x) = x-i
Et là aussi, c'est en déroulant la suite de Fibonacci 'à l'envers' qu'on obtient cette somme maximale.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
lourrran écrivait:
> La conjecture est exacte.
? Lourran, cela serait bien que tu sois plus constructif et clair dans tes interventions. Je vois bien que tu es nouveau et nous avons tous fait des erreurs, et c'est pour cela que je te conseille de ne pas essayer d'intervenir à tout va et annoncer des choses sans fondement ou sans preuve explicite. Cela fait vraiment perdre en crédibilité.
Al-Kashi -
A partir des programmes que j'ai écrits, la conjecture est exacte. C'est ce que tu demandais de vérifier, et c'est ce que j'ai vérifié. Que dire de plus ? Mais ça reste effectivement une conjecture.
La démonstration que la somme donne x-2 est évidente. La démonstration qu'aucune autre chaine ne peut donner une somme supérieure à x-2 est un peu tordue à formuler, c'est pour cela que j'en reste au niveau 'conjecture' et pas au niveau démonstration.
Idem pour la généralisation aux autres suites de Fibonacci ( 1, i, 1+i... avec i >2), tous les tests faits par programmation confirment que la meilleure somme est obtenue en déroulant la suite de Fibonacci à l'envers. La démonstration que cette somme donne x-i est évidente, la démonstration qu'il n'y a pas de meilleure chaine n'est pas évidente.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Je crois que tu oublies le terme $R_1$ dans la somme. Par exemple si $R_0=x=13$ et $R_1=8$, la suite obtenue est $8,5,3,2,1$ donc la somme est $19$.
-
Voici une idée de démonstration. On modifie un peu ma démonstration http://www.les-mathematiques.net/phorum/read.php?5,1751896,1752100#msg-1752100 pour établir par récurrence que
1) Si $1\leqslant b<\alpha a$ alors $f(a,b)\leqslant (\alpha+2)b-(\alpha+1)$
2) Si $\alpha a<b\leqslant a-1$ alors $f(a,b) \leqslant -(\alpha+1)b+(\alpha+2)a-(\alpha+1)$.
Ceci entraîne que $f(a,b)\leqslant (\alpha+1)(a-1)$, donc la somme optimale ne peut pas dépasser $\lfloor (\alpha+1)(a-1)\rfloor$.
Or, pour $a=F_n$ et $b=F_{n-1}$, on a $f(a,b)=F_{n+1}-2=\lfloor (\alpha+1)(a-1)\rfloor$. -
@JLT
Tout d'abord merci pour ta participation et ton investissement dans ce problème que j'ai posé.
La résolution de la conjecture plus faible que j'ai proposée me semble être une jolie avancée dans ce problème.
Je ne comprends pas la récurrence que tu proposes:
Dans ton message tu écris:
1) Si $b< \alpha a$ alors $f(a,b)<(\alpha+2) b$.
En effet, dans le premier cas on écrit la division Euclidienne $a=bq+r$. On a $f(a,b)=b+f(b,r)$. Or, $f(b,r)(\alpha+1)b$ par hypothèse de récurrence, donc
$f(a,b)<(\alpha+2)b$.
Pourrais-tu clairement préciser l'hypothèse de récurrence en ajoutant des précisions sur $a$ et $b$.
En te remerciant,
Al-Kashi -
Dans mon message http://www.les-mathematiques.net/phorum/read.php?5,1751896,1752100#msg-1752100 je fais une récurrence sur $a$. La propriété $P(a)$ est que pour tout $b$ compris entre $1$ et $a-1$ on a les inégalités 1) et 2).
On démontre facilement que si $a$ est un entier tel que $P(a)$ est vraie, alors $f(a,b)\leqslant (\alpha+1)a$.
Dans le passage que tu cites, je suppose que $P(a')$ est vraie pour tout $a'<a$ et je veux montrer $P(a)$. J'écris $a=bq+r$. Comme $P(b)$ est vraie par hypothèse de récurrence, on a $f(b,r)\leqslant (\alpha+1)b$ (il y a des petites imperfections dans ma démonstration, il faudrait faire attention au cas où $b=a$ mais ce cas est facile). -
Mon avant-dernier message ne demande quasiment pas de travail, il y a juste une constante $\alpha+1$ à mettre en plus, c'est exactement la même démonstration. J'ai cependant pris 15 minutes à faire des essais numériques pour conjecturer la bonne constante $\alpha+1$ et à vérifier numériquement que la majoration est assez fine pour traiter la suite de Fibonacci.
-
@JLT
A part rajouter quelques petites précisions , je ne vois plus aucune objection à ton raisonnement.(tu)(tu)(tu)
Grâce au travail réalisé par JLT, on a donc le résultat suivant:
Théorème de JLT:-D:
On note $(F_n)_{n\in\N}$ les valeurs de la suite de Fibonacci.
Soit $n>2$.Si $R_0=F_n$ alors la somme $\sum\R_k$ est maximale pour $R_1=F_{n-1}$.
Je pense que ce premier résultat est important. Il y a peut être des chances de pouvoir étendre le résultat à d'autres valeurs $G_n$ en considérant les suites $G_{n+2}=aG_{n+1}+bG_n$ récurrentes d'ordre $2$ du même type que celle de Fibonnaci.A suivre.
Al-Kashi -
Il y a d'une part
- les suites de type $G_{n+2}=G_{n+1} +G_n$ (c'est à dire a=1 et b=1,et on joue uniquement sur les 2 premiers termes)
- les suites de type $G_{n+2}=aG_{n+1} +bG_n$ (cas le plus général, sauf le cas a=b=1)
Le premier groupe va donner quelque chose. C'est certain. En particulier, on a une caractéristique très utile, c'est que ces suites sont globalement 'disjointes'.
Et accessoirement, elles ont toutes une asymptote avec la même pente : $y_n=(1+alpha)n + b$
Le 2ème groupe de suites ne va mener à rien. Il permettrait de résoudre un exercice voisin : A partir de R0, R1, on bâtit la suite : $R_{n+2}$ = le reste de la division de $R_n$ par $b*R_{n+1}$ (avec b>1) et on veut maximiser la somme des restes. Pour un exercice comme ça, effectivement, on retomberait sur les suites de Fibonacci du type $G_{n+2}=aG_{n+1} +bG_n$Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
@Lourrran
Je partage globalement ton avis, les suites avec $a=b=1$ donnent le même résultat pour des valeurs de $G_n$ assez grandes.En effet en utilisant le même raisonnement que JLT on montre qu'en choisissant $R_1=G_{n-1}$ la somme des $\sum \R_k$ converge vers la somme optimale.
Al-Kashi -
Pas trop réfléchi, et pas trop d'idées non plus...
-
Dans le même thème, il y a un autre exercice, qui peut déboucher sur quelque chose.
A partir de $X=R_0$, on cherche $R_1$ qui maximise la somme ...
Connaissant $(R_0,R_1)$ , on détermine $R_2$ ; $R_2$ est toujours égal à $R_0-R_1$
Faisons la même recherche, mais avec une autre valeur initiale. Prenons maintenant comme valeur initiale $Y=R_1$ (Le $R_1$ du calcul précédent, qu'on notera maintenant $R_0$ !).
Le meilleur $R_1$ pour cette nouvelle valeur Y, on peut le rechercher. Très souvent, on va trouver $R_1(Y)=R_2(X)$
Mais il doit y avoir quelques exceptions.
Autrement dit : $R_{i+1}(X)$ est il toujours égal à $R_i(R_1(X))$ ?
Ou encore : $R_{i+j}(X)$ est il toujours égal à $R_i(R_j(X))$ ?
Quand $R_j(X)$ est petit, il y a des exceptions, mais quid des exceptions quand $R_j(X)$ est grand (supérieur à 1000 par exemple)Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Bonjour,
Voici une autre conjecture:
Conjecture:
Pour une valeur $R_0$ donnée, on note $f(R_1)$ le nombre d'étapes consécutives à partir de $R_0$ telles que les quotients soient égaux à $1$. La somme $\sum R_k$ est maximale pour une valeur $R_1$ telle que $f(R_1)$ soit maximale.
Dans le cas où cette conjecture serait établie, on montrerait aisément qu'elle impliquerait que $R_1$ est à chercher dans le dernier intervalle du type : $\Big[\dfrac{F_{2k}}{F_{2k+1}}R_0;\dfrac{F_{2k+1}}{F_{2k+2}}R_0\Big]$ contenant au moins un entier.
Al-Kashi -
Si l'un d'entre vous a quelques idées à proposer pour résoudre ce problème qui me résiste encore:-X
Al-Kashi -
Bonjour,
En reprenant à la fois les idées de Champ-Pot-Lion et de JLT et sauf erreur de ma part on obtient la solution au problème dans $\mathbb{R}$.
Pour cela on définit d'abord la division euclidienne dans $\mathbb{R}$ comme Champ-Pot-Lion. On prouve ensuite que:
Lemme :
Soit un nombre $R_0\in\mathbb{R}$ et $R_1\in\mathbb{R}$ tel que $ 0\leq R_1\leq R_0$.La somme $\sum_{0}^{\infty} R_k$ est convergente.
Théorème:
Soit un nombre $R_0 \in \mathbb{R}$. L'unique valeur telle que la somme $\sum_{0}^{\infty} R_k$ soit maximale est $R_1=(\varphi-1) R_0$ où $\varphi$ représente le nombre d'or.
Al-Kashi -
En reprenant mes brouillons, je me rend compte que la preuve coince un peu:
1) On prolonge les résultats obtenus par JLT dans $\mathbb{D}$:
En effet il suffit de remarque que si $R_0$ et $R_1$ sont des décimaux, en multipliant par une puissance de $10^k$ appropriée, on obtient une suite d'entiers dont la somme a donc aussi été multipliée par $10^k$. Ainsi les majorations obtenues restent valables dans $\mathbb{D}$
2) On prolonge ensuite les majorations dans $\R$::
On effectue un raisonnement par l'absurde. On suppose que l'une des deux majorations est fausse pour un couple $(R_0, R_1)\in\R^2$. On construit une suite de rationnels qui converge vers $(R_0, R_1)$. Et c'est ici que ça coince: je n'arrive pas à prouver rigoureusement l'existence d'un couple de rationnels qui ne respecterait pas les majorations.L'analyse et moi on fait $4$.
3) On prouve alors que les deux droites tracées par JLT ci-dessus se croisent en $(\varphi-1)R_0$ et que le maximum est atteint en cette valeur.
Auriez-vous une idée pour clarifier le point 2?
En vous remerciant,
Al-Kashi -
Voici la preuve du premier résultat annoncé, et nous allons directement prolonger dans $\Q$ grâce au lemme suivant en reprenant les notations de JLT:
Lemme1:
Pour tous $(a,b)\in\N^2$ et $\lambda \in\R^{+*}$ : $\lambda f(a,b)=f(\lambda a, \lambda b)$.
Preuve:
Si la division de $a$ par $b$ s'écrit $a=bq+r$, on a alors $\lambda a= \lambda bq+\lambda r$ avec $\lambda r<\lambda b$. On en déduit alors que $\lambda r$ est le reste de la division euclidienne de $\lambda a$ par $\lambda b$. Une récurrence permet de conclure.
Corollaire:
Si $(u,v)\in \Q^{2+}$ alors la somme $f(u,v)$ est définie.
Preuve:
Notons $u=\dfrac{p}{q}$ et $v=\dfrac{r}{s}$. D'après le lemme précédent, on alors: $\dfrac{1}{sq} f(ps,rq)=f(\dfrac{p}{q},\dfrac{r}{s})=f(u,v)$.
Lemme 2:
Pour tout couple $(u,v) \in\Q^{2+}$ tel que $0 \leq v \leq u$ :
Si $v< \alpha u$ alors $f(u,v)<(\alpha+2)v$
Si $v> \alpha u$ alors $f(u,v)<-(\alpha+1)v+(\alpha +2)u$
Preuve:
Notons $u=\dfrac{p}{q}$ et $v=\dfrac{r}{s}$.
Si $\dfrac{p}{q}< \alpha \dfrac{r}{s}$ alors $ps< \alpha rq$. Or d'après les résultats obtenus par JLT dans $\N$ : $f(ps,rq)<(\alpha+2)rq$. On a donc d'après le Lemme1: $\dfrac{1}{sq}f(ps,rq)<\dfrac{1}{sq}(\alpha+2)rq$ soit $f(u,v)<(\alpha+2)v$.
Si $\dfrac{p}{q}> \alpha \dfrac{r}{s}$ alors $ps> \alpha rq$. Or d'après les résultats obtenus par JLT dans $\N$ :$f(ps,rq) \leq -(\alpha+1)rq+(\alpha+2)ps$. On a donc d'après le Lemme1: $\dfrac{1}{sq}f(ps,rq) \leq \dfrac{1}{sq}(-(\alpha+1)rq+(\alpha+2)ps)$ soit $f(u,v)<-(\alpha+1)v+(\alpha +2)u$.
J'espère qu'un analyste pourra nous prolonger dans $\R$.
Ce problème me plaît de plus en plus :-D
Al-Kashi -
Détail :
Lorsque n = Fk, alors la somme des restes, n compris, vaut F(k+2) - 2.
Sinon : (n, n-a)
On a tout intérêt à choisir " a " tel que n-a > n/2, de sorte que la division euclidienne ne soit en fait qu'une soustraction.
a < n/2
Suivant :
n - (n-a) = a
(n, n-a, a)
On a tout intérêt à choisir " a " de sorte que a > (n-a) / 2. soit a > n / 3.
Suivant
(n, n - a, a, n - 2a)
On a tout intérêt à choisir n-2a > a / 2 soit : ....a < 2/5 n
Etc.....
Et on aboutit à la conjecture proposée.
Bien sûr, il faudra ajuster.
Pour 10 : 6 , 4 , 2 est dans les clous ( 10 / phi = 6,18...)
Pour 15 : 10 devrait être le bon choix ( 15 * 0,618...) mais il y a mieux : 15 9. -
Je pense avoir trouvé une preuve rigoureuse pour le prolongement dans $\R$. Rédaction dans l'après midi si j'ai le temps.
Al-Kashi -
Voici la preuve du point 2), c'est à dire du prolongement des majorations dans $\R$:
Lemme 3:
Pour tout couple $(u,v) \in \R^{2+}$ la somme $f(u,v)$ est définie.
Preuve:
Tout d'abord, supposons qu'il existe deux termes consécutifs de la suite des restes du couple $(u,v)$ tels que $\dfrac{R_{j+1}}{R_{j}}$ soit rationnel.
D'après le Lemme 1 la somme $R_{j}f(1,\dfrac{R_{j+1}}{R_{j}})=f(R_j,R_{j+1})$ est définie et donc la suite $f(u,v)$ l'est aussi.
Nous supposons à présent que tous les rapports de la suite $R_k$ sont tels que $\dfrac{R_{j+1}}{R_{j}}\not\in\Q$.
Sachant que la $\sum R_k$ est croissante, il suffit de prouver qu'elle est majorée car toute suite croissante et majorée converge vers sa borne supérieure. Notons $u=qv+r$ la divisions euclidienne de $u$ par $v$ .
On considère la suite $\epsilon_t =\dfrac{1}{t}$.Il existe alors pour tout $\epsilon_t$ un couple de rationnel $(x_t,y_t)$ tel que $u-x_t=\sigma_t <\epsilon_t$ et $v-y_t=\sigma^{'}_t <\epsilon_t$. Autrement dit, la suite $(x_t,y_t)$ converge vers $(u,v)$. Par hypothèse, $\dfrac{u}{v}\not\in\Q$ et donc $q<\dfrac{u}{v}< q+1$.
On a donc pour $t$ assez grand $q<\dfrac{x_t}{y_t}<q+1$ soit $q=\Big\lfloor\dfrac{x_t}{y_t}\Big\rfloor$. Notons $x_t=qy_t+r_t$ la division euclidienne de $x_t$ par $y_t$. On en déduit alors que $r_t=x_t-qy_t$ converge vers $r$. En conclusion la suite $(x_t,y_t,r_t)$ converge vers $(u,v,r)$. On prouve alors par récurrence que la suite des restes $(x_t,y_t,r_t,....)$ converge vers la suite des restes $(u,v,r,...).$. Supposons que $\sum R_k$ ne soit pas majorée. Pour tout $M>0$ il existe une valeur $s$ telle que $\sum_0^s R_k>M$. D'après ce qui précède il existe donc une valeur de $t$ telle que la somme des restes $(x_t,y_t,r_t,....)$ soit strictement supérieure à $M$.Or d'après le Lemme 2 cette suite est majorée par $(\alpha +2)y_t$. Or d'après ce qui précède, $y_t$ converge vers $v$ ce qui implique que pour $t$ assez grand $(\alpha+2)y_t$ est majorée par exemple par $(\alpha+2)(v+1)$. D'où une absurdité et la somme $\sum R_k$ est donc majorée et convergente.
Lemme 4:
Pour tout couple $(u,v) \in\R^{2+}$ tel que $0 \leq v \leq u$ :
Si $v< \alpha u$ alors $f(u,v)\leq(\alpha+2)v$
Si $v> \alpha u$ alors $f(u,v)\leq-(\alpha+1)v+(\alpha +2)u$
Preuve:
Il suffit de raisonner par l'absurde et de reprendre la preuve précédente en remarquant que $(\alpha+2)y_t$ converge vers $(\alpha+2)v$ pour la première majoration et $-(\alpha+1)y_t+(\alpha +2)x_t$ converge vers $-(\alpha+1)v+(\alpha +2)u$. pour la deuxième majoration.
Edit: Correction de coquilles.
Al-Kashi -
Voici les grandes lignes de la preuve du point 3) que je compléterai au fur et à mesure:
On introduit ici la suite de Fibonnaci $F_0=0$, $F_1=1$ et $F_{k+2}=F_k+F_{k+1}$.
Lemme 5:
Pour tout entier naturel $i$ on a $\dfrac{F_{2i+2}}{F_{2i+1}}<\varphi< \dfrac{F_{2i+3}}{F_{2i+2}}$
Preuve:
Tout d'abord on prouve que $F_{2(i+1)+3}F_{2i+2}-F_{2i+3}F_{2(i+1)+2}=-1$ et $F_{2i+2}F_{2(i+1)+1}-F_{2(i+1)+2}F_{2i+1}=-1$.
On en déduit alors que la suite $D_i= \dfrac{F_{2i+3}}{F_{2i+2}}$ est strictement décroissante et la suite $C_i= \dfrac{F_{2i+2}}{F_{2i+1}}$ est strictement croissante.
Or on sait que $D_i$ et $C_i$ convergent vers $\varphi$ ce qui implique que $C_i< \varphi < D_i$.
Lemme 6:
On considère la suite des restes $\R_k$ des divisions euclidiennes successives définie par $ R_0=1$ et $R_1=\varphi-1$.
Pour tout $k\in \N$ on a : $R_k=(-1)^{k+1}F_k\varphi+(-1)^kF_{k+1}$.
Preuve:
Notons $P(i)$: Pour tout $0 \leq k \leq i $ $R_k=(-1)^{k+1}F_k\varphi+(-1)^kF_{k+1}$. $P(1)$ est vraie. Supposons $P(i)$ vraie.
On prouve tout d'abord en utilisant le Lemme 6 que $\dfrac{R_{i-1}}{R_{i}}<2$.Ceci implique que $R_{i+1}=R_{i-1}-R_{i}$.Or:
$R_{i-1}-R_{i}=((-1)^{i}F_{i-1}-(-1)^{i+1}F_i)\varphi+(-1)^{i-1}F_{i}-(-1)^iF_{i+1}$
$R_{i-1}-R_{i}=(-1)^{i+2}F_{i+1} \varphi+(-1)^{i+1}F_{i+2}$.
$R_{i+1}=(-1)^{i+2}F_{i+1} \varphi+(-1)^{i+1}F_{i+2}$
En conclusion $P(i+1)$ est vraie.
Corollaire:
On considère la suite des restes $\R_k$ des divisions euclidiennes successives définie par $ R_0=1$ et $R_1=\varphi-1$.
$\sum_{k=0}^{\infty} R_k=\varphi+1$
Preuve:
D'après les Lemme 3 et Lemme 6 on a:
$\sum _{k=0}^{\infty}R_k=\sum _{k=0}^{\infty}(-1)^{k+1}F_k\varphi+(-1)^kF_{k+1}$
$\sum _{k=0}^{\infty}R_k=\sum _{k=0}^{\infty}(-1)^{k+1}(\dfrac{1}{\sqrt{5}}(\varphi^k-\varphi'^k)\varphi+(-1)^k(\dfrac{1}{\sqrt{5}}(\varphi^{k+1}-\varphi'^{k+1})$
$\sum _{k=0}^{\infty}R_k=\sum _{k=0}^{\infty}(-1)^{k}\dfrac{1}{\sqrt{5}}\varphi'^k\varphi+(-1)^{k+1}\dfrac{1}{\sqrt{5}}\varphi'^{k+1}$
$\sum _{k=0}^{\infty}R_k=\dfrac{1}{\sqrt{5}}(\varphi-\varphi')\sum _{k=0}^{\infty}(-1)^{k}\varphi'^k$
$\sum _{k=0}^{\infty}R_k=\dfrac{1}{\sqrt{5}}(\varphi-\varphi')\times\dfrac{1}{1+\varphi'}$
$\sum _{k=0}^{\infty}R_k=\varphi +1$
Théorème:
Pour une valeur $R_0\in\R^{+}$ donnée, la somme $\sum_{k=0}^{\infty} R_k$ est optimale si et seulement si $R_1=(\varphi-1)R_0$
Preuve:
D'après le Lemme 4:
Pour tout couple $(u,v) \in\R^{2+}$ tel que $0 \leq v \leq u$ :
Si $v< \alpha u$ alors $f(u,v)\leq(\alpha+2)v$
Si $v> \alpha u$ alors $f(u,v)\leq-(\alpha+1)v+(\alpha +2)u$
Or la fonction $g(v)=(\alpha+2)v$ est strictement croissante sur l'intervalle $[0;\alpha u]$ et la fonction $r(v)=-(\alpha+1)v+(\alpha +2)u$ est strictement décroissante sur $[\alpha u;u]$.De plus $r(\alpha u)=g(\alpha u)=\varphi u$. On en déduit alors que pour $v \neq \alpha u$ $f(u,v)<\varphi u$. Or d'après le Corollaire précédent, et au sens de JLT, c'est à dire sans prendre en compte le premier terme, $f(u,\alpha u)=u f(1,\varphi-1)=\varphi u$.
Al-Kashi -
Bonjour,
J'ai complété la fin de la preuve. Bien évidemment, tout n'est pas proprement rédigé mais si vous constatiez une erreur de raisonnement n'hésitez pas . Je tiens à remercier JLT, car c'est à partir du résultat qu'il a obtenu dans $\N$ que j'ai eu l'idée de prolonger successivement les majorations dans $\Q$ puis dans $\R$. Je tiens aussi à remercier Champ-Pot-Lion car c'est à partir de son graphique que j'ai eu l'idée de prouver que le maximum était atteint en $(\varphi-1)R_0$. Bien évidemment, je remercie aussi tous les participants.
Il faut sûrement encore pas mal de travail pour obtenir un résultat précis dans $ \N$.
Al-Kashi -
Bonjour,
Je tenais à vous signaler qu'en théorie ce problème devrait apparaître dans la RMS 130-3 dans la rubrique Terminal S.
Je tiens à remercier JLT ( majorations dans $\N$) qui m'a donné son accord. Sans cela et sans l'aide des graphiques de Guego (conjecture dans $\N$) et Champ-pot-Lion (conjecture dans $\R$) que je remercie aussi je n'aurai pas eu l'idée de tenter un prolongement dans $\Q$ puis $\R$ pour prouver ensuite que la somme optimale est obtenue pour $r_1=r_0(\varphi - 1)$ sur l'intervalle $[0;r_0]$.
Al-Kashi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 22
+16 Invités