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.

Bonsoir Verdurin

En effet , ce n'est pas si simple

Imod

Bonjour,
Enfin un peu d'animation....

 Cliquez pour afficher

Si on prend un nombre de 20 chiffres par exemple et si on met les + entre chaque
chiffre on totalise un nombre compris entre  1 et 180 pour éviter le 0 disons 179
à son tour donnant 17 puis 8  .
Il ne faut que 3 étapes.
Si on met moins de +  par exemple 3 on aura  3 paquets  au maximum  7chiffres+7chiffres+6 chiffres  soit  au plus  63+63+54 =180 et on retombe
sur le cas précédent.

Je pense sans l'avoir encore démontré que 4 étapes seront suffisantes pour n'avoir
qu'un nombre entier à un chiffre.

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

Bien sûr , dans mon contre-exemple on était loin des "endroits stratégiques"

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 10ⁿ-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 2⁶² 4.6x10¹⁸ 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:

Citation :
Quel est le nombre d'étapes maximum nécessaire pour réduire n'importe quel nombre n en un nombre à un chiffre en insérant des '+' entre les chiffres de n à chaque étape?

Soit un nombre de 2n chiffres avec éventuellement .

Posons , la somme de tous les chiffres de n;
, la somme des m dernières paires de chiffres (interprétées comme des nombres de 0 à 99) plus la somme des chiffres restants;
Et , la même somme que y_m mais décalées d'un chiffre vers la gauche.

En réarrangeant, et .

x, comme tous les nombres naturels, se trouve entre deux multiple de puissances de 10. En particulier , avec c le premier chiffre de x et k+1 le nombre de chiffres de x.

Par définition, .

et ne peuvent être en même temps inférieur à . En effet:


Le second terme de la dernière expression est positif pour k > 0. Mais si k = 0 alors x n'a qu'un chiffre et n peut être réduit en une seule étape en additionnant tous les chiffres.

Si ,
est une fonction croissante de avec , il existe donc au moins un tel que . De plus, . Et donc .
Si , x est un nombre à deux chiffres et il est vérifié que tous les nombres inférieur à 100 peuvent être réduits en au plus deux étapes.
Sinon, est donc un nombre composé d'un chiffre, zéro ou plusieurs 0 et enfin deux chiffres formant un nombre entre 0 et 80 compris.

La somme des chiffres de est comprise entre 1 () et 25 ().

Le même raisonnement peut être tenu pour si .

Tous les nombres entre 1 et 25 donnent un nombre à un chiffre en zéro ou une étape sauf 19 qui nécessite deux étapes.

On a donc la garantie qu'au moins un des chemins (avec la somme des chiffres de n),
ou

mène à un nombre de un chiffre.

On a donc besoin au maximum de 4 étapes.

On pourrait réduire à 3 étapes en évitant de passer par 19. Mais c'est une autre histoire.

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

Petite coquille:

Du coup, il faut x > 80, mais ça ne change rien sinon.

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.

Le plus petit nécessitant 3 étapes est 289 comme dit dans mon message du 02-05-19 à 12:08.

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

Je n'ai pas vu à quel endroit tu traitais le deuxième cas , j'ai la vue qui baisse

Imod

Ma démonstration est vraiment si confuse?

Premier cas:

Citation :
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.

Citation :
Si  
Comme , il existe un terme ou égal à   avec .
Pour la même raison qu'avant, ceci prouve le résultat

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 :

Citation :
Soit un nombre de 2n chiffres avec éventuellement .

Vu par weierstrass le 04-05-19 à 17:56 . Voir la parenthèse ci dessous :

Citation :
Dans ce cas, le nombre étudié (notons le pour éviter la confusion avec les indices) est simplifiable en 3 étapes ou moins.

Pour essayer d'avancer le cas binaire:

 Cliquez pour afficher

Cherchons tel que cela prend 3 étapes.
on notera le nombre de bits égaux à 1 de (ou lorsque cela ne prête pas à confusion)

Définition:
Le nombre de blocs de est le nombre de sous-suites constituées uniquement de 1s.

Définition:
Soit , , ..., une liste de nombre binaires.
On définira le delta de par la formule:


Lemme 1:
Soit tel que = , si contient , , ..., comme sous suites (de manière disjointe) et que , alors est soluble en 2 étapes.
Démonstration
Dans le découpage de, si on associe les en un groupe par , et que tout les bits restants de sont associés ensemble, la somme obtenue par ce découpage est

Définition:
Si possède un découpage permettant d'obtenir une somme de , alors dira que possède un delta   ( peut posséder plusieurs delta différents)


Lemme 2:
Si et que possède une sous suite possédant un delta de , alors est soluble en 2 étapes.
Démonstration
Soit , , ..., le découpage aboutissant à un delta de . , , ..., sont donc contenus de manière disjointe dans
De plus, le delta des est égal à , ce qui prouve le résultat.

Lemme 3:
Supposons que pour un donné, on trouve un tel que tout les cas où constitués d'au moins deux blocs peuvent être découpés en une  somme égale à .
Alors pour tout , si , alors A est soluble en 2 étapes.
démonstration:
Toutes les suites constituées d'au moins 2 blocs ont donc un delta de
Soit un entier tel que avec .
Si contient une sous-suite avec et composée de plus de 2 blocs, alors d'après le lemme 2, A est soluble en 2 étapes.
Si toutes les sous-suites de contenant bits sont composées d'un seul bloc de 1s, alors A est composé d'un seul bloc de 1s. (Si était composé de deux blocs de 1s ou plus, on pourrait toujours former une suite de plusieurs blocs de 1s en chevauchant 2 blocs).
Le cas où est composé d'un seul bloc de 1s est soluble en 2 étapes: Il suffit de faire un bloc de 1s et un bloc contenant juste un 1.



Si ça prend clairement 1 étape.
Si il suffit de 2 étapes.

On notera une suite de 0 ou plus.

Si :




Si => 1 + 1 + 1 + 1

Si :
Si contient
Si contient
Donc il ne peut y avoir qu'un bloc.
Si contient

Si:
Si contient (1)
Si contient deux
(donc au plus trois blocs)
Si contient deux (2)
(1) + (2) règlent tout les cas à trois blocs.

Si :
Si contient
Donc au plus 2 blocs.
Si
Si
Ce qui règle les cas à 2 blocs.

Si => 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Ainsi, les cas se déduisent de 5, 6 et 7 par le lemme 3.
Le cas est trivial

Lemme 4:
Si
ne contient pas plus de blocs.
Démonstration
Dans le cas contraire, en prenant les fins de k premiers blocs qui ne sont pas les derniers dans l'écriture décimale de A (et qui sont donc toujours suivis d'un 0):

Notons que ce découpage peut être utilisé dans le lemme 3.

Si :
ne contient pas plus de 5 blocs. (lemme 4)
Les listes:
(1)
(2)
(3)
(4)
ont un delta de 4. ne peut donc pas contenir ces listes de manière disjointe. (lemme 1)
(1) impose que les blocs ne contiennent qu'un seul 1 (à part le dernier)
(2)  impose que si il y a trois blocs ou plus, ils sont tous espacés de un 0.
(3) impose que tous les blocs ont 1 ou 2 1s
(4) impose qu'il ne peut y avoir que seul inter-bloc de un 0, et que si il y a des inter-blocs de 2 0s, il n'y a aucun inter-bloc de un 0.
En combinant (2) et (4), il y a donc moins de 3 blocs.
On voit facilement que ne peut pas être égal à 12.
Découper en utilisant ces deltas permet d'utiliser le lemme 3:
Tout les entiers avec sont solubles en 2 étapes.

Si :
Les suites:
(1)
(2)
(3)
(4)
(5)
ont pour delta 5. ne peut donc pas contenir ces sous-suites.

(1) impose que si il y a 4 blocs ou plus, il sont tous espacés de un 0.
(2) impose qu'il ne peut y avoir qu'un seul bloc possédant plusieurs 1s, et ce bloc possède 3 ou moins 1s.
(3) impose que ce bloc est forcément le dernier
(4) impose que ce bloc contient 2 ou moins 1s, ou alors c'est le seul bloc (dans ce cas, c'est trivial)
(5) Si il y a plus de 3 blocs et que le dernier possède 2 1s, alors ces blocs sont tous espacés de 1.

Si il y a 4 blocs ou moins, il est aisé de voir que .
possède au moins 11 blocs.
Or on sait d'après le lemme 4 que possède moins de 6 blocs.
Découper en utilisant ces deltas permet d'utiliser le lemme 3:
Tout les entiers avec sont solubles en 2 étapes.

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

C'est bon, je pense avoir trouvé la solution:

 Cliquez pour afficher

Soit tel que , (on a alors

possède moins de blocs.

De plus,
à pour delta ()
Donc si possède plus de blocs, alors ils sont tous de taille 1.
Si possède plus de blocs, dans le pire des cas, il en possède . Dans ce cas, on a donc , ce qui est impossible.
Cette liste à pour delta ()
Ceci implique que s'il y a plus de blocs, alors on peut au plus isoler   paires de 1.
Par exemple, si notre liste est 11, 11, 11, 11,  11, 10, 10, 10, si on a plus de 4 blocs, alors on peut isoler au plus 4 groupes de 1. par exemple, 11110111011 marche car on ne peut isoler que 3 paires 11 disjointes. Dans le pire des cas, chaque blocs est de taille impair (car si un bloc est de taille paire, rajouter un 1 ne permettra pas de faire une paire non disjointe des autres paires)
Si il y a blocs, (le cas est déjà traité), posons division euclidienne de par 2.
Le nombre de blocs est donc
On a donc (car dans le pire des cas, il y a paires 11, et un 1 en plus à chaque bloc pour les rendre impairs), soit ,  ce qui est impossible.

Ok, c'est pas bon en fait, il y a paires 11, donc ça marche pas...

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

Comment tu démontres ça? Parce que si tu le démontres, le problème est résolu...

Cette fois ci, je pense que c'est bon

 Cliquez pour afficher

à pour delta ()
Donc si A possède plus de blocs, alors au plus sont de taille 2, le reste étant de taille 1.
Si il y a blocs, (le cas est déjà traité), posons division euclidienne de par 3.
Le nombre de blocs est donc
On a donc (car comporte blocs, et au plus sont de taille 2.
Donc (ce qui est impossible)
Cela est possible si
Cela implique donc

Soit la division euclidienne de par 4.
à pour delta ()
On peut au plus isoler   triplets 111 disjoints.
Soit le nombre de blocs. Dans le pire des cas, chaque bloc est de taille (car sinon, rajouter un 1 ne permettra pas de faire un nouveau triplet 111 non disjoint des autres triplets)
On a donc
Si , alors ce sera impossible.
Cela nous donne
Or on sait déjà que si , c'est impossible, ce qui résout notre problème.

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

Bonjour à tous

Je suis content que ce problème continue à vivre , j'étais quasi-persuadé que trois étapes suffisaient dans le cas décimal et maintenant , c'est confirmé ( Merci Weierstrass ) .

Pour le reste je vous laisse vous amuser

Imod