Bonjour à tous
Un petit problème qui traîne dans mes brouillons depuis pas mal de temps :
On considère un nombre entier en écriture décimale , on insère des signes "+" aux endroits stratégiques entre certains de ses chiffres et on effectue les additions : c'est une première étape . On recommence l'insertion de "+" sur ce nouvel entier et on effectue à nouveau les additions : fin de la deuxième étape ...
Au bout de combien d'étapes est-on assuré d'obtenir un entier à un seul chiffre ?
J'ai une solution qui serait complète si je pouvais exhiber un entier ne pouvant pas être réduit à un chiffre en moins de quatre étapes : cet entier existe-t-il ?
J'espère que ce problème vous amusera autant qu'il m'a amusé
Imod
bonjour Imod
merci pour ce problème
le résultat final ne dépend pas des places des + insérés, c'est bien cela?
c'est amusant
Bonjour Veleda
En effet en considérant les sommes modulo 9 , on voit que le résultat ne dépend pas du nombre ni de la position des "+" . Par contre la vitesse de convergence en dépend fortement
Imod
Salut,
j'ai l'impression que la somme des chiffres ( on met des + partout où on peut ) assure la convergence la plus rapide.
Mais il va falloir que je regarde d'un peu plus près.
Si c'est le cas le problème me semble presque trivial.
Je crois donc mes impressions fausses.
Bonjour Dpi
J'ai montré que 4 étapes suffisent toujours et 3 dans pratiquement tous les cas , il me manque juste le cas où l'entier est congru à 1 modulo 9 .
La solution est assez courte mais un poil astucieuse
Je suis presque sûr que trois étapes suffisent dans tous les cas mais il me manque un argument .
Je donnerai un indice sur ma façon de faire si le problème ne décolle pas .
Imod
Je pensais rechercher un contre-exemple pour les trois étapes mais il faudrait trouver un nombre d'au moins 23 chiffres et sûrement beaucoup plus . Il vaut mieux espérer que trois étapes suffisent dans tous les cas .
Imod
Bonjour,
Je pense qu'il faut imposer un nombre minimum de + en fonction du nombre de chiffres ,car
si on prend un seul + au début ou à la fin d'un grand nombre,on obtient un autre
grand nombre en éloignant ainsi la réduction attendue.
Non , il est inutile d'imposer le nombre de + , on en met autant qu'on veut et ce n'est pas forcément en en mettant un maximum qu'on a la meilleure stratégie .
Imod
Il ne faut pas prendre la congruence modulo 9 comme une idée de démonstration .
Si on peut atteindre un entier inférieur à n=28 en deux étapes on a fini , sauf si n=19
Imod
Bonjour,
--> imod : comment traitez-vous 10n-1 , n formé d'un très grand nombre de 9 en quantité multiple de 9 ?
@vham
Il suffit d'additionner le premier 9 avec le nombre composé de tous les autres pour obtenir 10^(n-1)-1 + 9 = 10^(n-1)+8 qui est composé d'un '1', un '8' et n-2 '0' donc en deux étapes on arrive à 9.
@Imod
Encore un problème impossible à résoudre?
Parmi les nombre inférieurs à un million, la plupart n'ont besoin que de deux étapes. Il n'y a que 63443 nombres qui ont besoin de 3 étapes. Le plus petit étant 289.
Mais comment prouver qu'un nombre comme n=579315441871736358998339932168614659615325433246361729431918111 n'a pas besoin de 4 étapes?
Je connais un chemin en 4 étapes :
n -> 289 -> 19 -> 10 -> 1
Mais je ne peux pas tester les 262 4.6x1018 sommes possibles.
Le truc est de générer le plus de 0 possibles mais je n'ai pas encore trouvé de technique plus efficace que l'essai erreur.
Impossible à résoudre ? Tout dépend de l'endroit où on place la barre
On peut réduire à un chiffre tout nombre non congru à 1 modulo 9 en trois étapes et pour les autres en quatre étapes au plus .
Si on arrive à trouver un exemple de nombre congru à 1 qui n'est pas réductible à 1 chiffre en moins de quatre étapes on aura fini le travail . De même si on arrive à montrer que tout nombre congru à 1 est réductible à 1 chiffre en seulement trois étapes ( je penche plutôt pour cette hypothèse ) .
Imod
PS : je donnerai un indice sur ma méthode ce soir , là je n'ai pas le temps .
L'idée de la démonstration.
Soit avec éventuellement . On note S , P , I , G et D la somme de tous les chiffres de , des chiffres de rang pair , de rang impair ou groupés par 2 en partant de la gauche ou de la droite . On peut trouver un entier à 1 chiffre c et un entier k tels que . On peut supposer par exemple que et on montre facilement qu'alors . Il suffit alors de partir de la somme S et de remplacer successivement par puis par , ... jusqu'à ce que la T somme dépasse . Comme à chaque pas on augmente au maximum de 81 , la somme des chiffres de T ne dépasse pas 25 et on peut conclure .
Imod
Bon, d'accord. Ce n'est pas impossible
J'ai eu du mal à suivre ton explication, en particulier tu définis D comme la somme de tous les chiffres de x groupés par 2 en partant de la droite alors que c'est les chiffres d'un autre nombre que j'appelle n ci-dessous. x est égal à S.
Il y aussi la partie "on montre facilement qu'alors (c+1)10^k<D" qui ne me semblait pas facile du tout.
J'ai donc décidé de réécrire tout ça un peu plus rigoureusement Voici le résultat:
Chacun voit les choses à sa façon , j'ai préféré choisir un nombre impair de chiffres pour différencier clairement les groupement par paquets de deux en partant de la gauche ou de la droite . Après si alors comme :
et .
On note que l'on peut regrpouper les chiffres deux par deux dans l'ordre que l'on veut à condition de respecter la parité , c'est pour cette raison que je laisse peu de chance à une solution en quatre étapes ( sauf cas pathologique ) .
Imod
Bonjour à vous deux,
j'ai du mal à suivre,mais ce problème est déroutant ...
En pratique on s'étonne du résultat,comment s'imaginer que 4 étapes suffisent.
Et pourtant....
Restons scolaires :
Soit un nombre de 1 milliard de chiffres,en les additionnant on devrait trouver
statistiquement 5 500 000 000 au pire 8 999 999 999 en étape1 et 89 en étape 2
puis 17 pour finir sur 8.
Par tranche de 1000 (999 ) on n' ajouterait que 27 à ce 89 ce qui promet d'aller loin
Merci d'animer
Pas très disponible et en déplacement, mais je pourrai regarder sérieusement en fin de semaine ce problème original qui semble très amusant !
Très sympathique comme problème!
J'ai juste l'impression qu'il y a une légère erreur chez LittleFox:
Bon après, ça ne change pas le raisonnement...
Voici un proposition pour achever cette démonstration:
Donc:
Si , alors
Dans ce cas, le nombre étudié (notons le pour éviter la confusion avec les indices) est simplifiable en 3 étapes ou moins.
Dans le cas contraire, on a :
Si est congru à 1 modulo 9 et que
Alors il existe un terme ou égal à avec
Dans ce cas, à la prochaine étape, la somme sera inférieure à 18 (donc 10 ou 1) ce qui prouve le résultat.
Si
Comme , il existe un terme ou égal à avec .
Pour la même raison qu'avant, ceci prouve le résultat
Fait intéressant, cette démonstration peut être adaptée à toutes les bases. Elle suit exactement le même cheminement, jusque dans les moindres détails...
Pour aller plus loin:
Quel est le plus petit nombre nécessitant au moins 3 étapes? (s'il en existe un)
En binaire, peut on toujours faire 2 étapes?
Bonjour Weierstrass
Beaucoup de questions
Exactement trois étapes en écriture décimale , je suis convaincu que ça existe , pour le plus petit , je laisse faire les informaticiens ( idem pour le cas binaire ) .
Sûr , iI est très amusant ce problème mais il reste la question : minimum 3 ou 4 en écriture décimale
Imod
Justement, je viens de démontrer que l'on peut toujours faire 3 en décimal.
J'ai réglé le cas général.
Après réflexion a tête reposée, mes questions ne sont pas si dures.
Pour le plus petit nombre nécessitant 3 étapes, le plus petit est 289.
En binaire, on peut toujours faire en 2 étapes, c'est très facile, je vous laisse trouver.
C'est la seule base pour laquelle c'est le cas.
@Weierstrass : Si x est congru à 1 modulo 9 et que
Je pense que tu as repris les notations de LittleFox avec x la somme des chiffres de l'entier de départ mais pourquoi aurait-on ?
Imod
Je distingue le cas 2\times
et le cas
(Je m'aperçois d'ailleurs que j'ai fait une faute sur la deuxième condition dans mon précédent message...)
Ma démonstration est vraiment si confuse?
Premier cas:
A la réflexion, j'ai pas réussi à démontrer qu'on pouvait faire en 2 étapes en binaire, mon argument était bidon. Je pense qu'il y a là un joli problème à résoudre pour poursuivre cette énigme.
Bonjour,
J'ai un peu de temps pour commencer à tenter de me mettre dans le bain
Une petite remarque sur le début de l'explication de LittleFoxle 03-05-19 à 11:49 :
Vu par weierstrass le 04-05-19 à 17:56 . Voir la parenthèse ci dessous :
Pour essayer d'avancer le cas binaire:
Ok, j'ai trouvé un sujet sur reddit qui prouve que c'est toujours possible en 2 étapes en binaire. Je n'ai pas lu la solution car j'ai envie de chercher, mais ça nous renseigne au moins sur le fait qu'il n'y a pas besoin de chercher de contre exemple...
En base 2,
Je ne sais pas si ça mène loin mais pour tout les nombres > 1 soit ils n'ont que deux chiffres 1, soit il y a moyen d'arriver à une somme qui est la puissance de 2 juste supérieure à la somme des chiffres.
Sauf pour 31(10) = 11111(2).
Cette fois ci, je pense que c'est bon
Ok, j'ai regardé la preuve trouvée sur Reddit:
En fait, c'était tout simple :
Au lieu de faire des groupes de 2, on fait des groupes de 3, on peut montrer que l'une des associations peut mener à quelque chose plus de 2 fois plus grand que x.
On garde juste les 4 premiers 1.
Le plus grand delta sur 3 digits est atteint pour 111 et vaut 4.
On peut donc obtenir un nombre de la forme 2^n-R avec R plus petit que 3.
Sur les 4 premiers digits égal à 1, si on analyse toutes les configurations, on pourra toujours faire un delta de R.
Comme pour la preuve en 3 étapes, c'est seulement valable à partir d'un A assez grand.
Pour aller (toujours) plus loin, est ce que pour tout x, on peut trouver un A qui n'est pas soluble en 2 étapes.
Par exemple, pour x = 19, on a 289, mais existe t-il de tels nombres pour x = 100, 200, 10000?
J'ai l'intuition qu'a partir d'un certain x, on pourra toujours le faire en deux étapes, on adaptant un peu la preuve du cas binaire...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :