Forum Problème – Aventure n°1

Navigation du forum
Fil d’Ariane du forum – Vous êtes ici :Problème - Aventure n°1Nombres que l'on peut atteindre
Veuillez pour créer des messages et des sujets de discussion.

Nombres que l'on peut atteindre

Mais au fait quels sont tous les nombres que l'on peut atteindre avec :

\(\pm 1\pm 2\pm 3\pm\ldots\pm98\pm99\pm100\)

et si on se choisit un nombre cible parmi eux, peut-on trouver une méthode ou écrire un algorithme qui nous donnera au moins une de ses décompositions ?

Oui , en écrivant un algorithme qui teste toutes les sommes possibles.

encore faut-il écrire cet algorithme. en faisant varier uniquement le + ou - pour chaque nombre; donc il y aurait 2^100 calculs.  ... A VOIR

Avec le petit programme en python :

liste=[-1,1]
for i in range(2,101):
@print(i)
@liste_suite=[]
@for base in liste:
@@liste_suite=liste_suite+[base-i]
@@liste_suite=liste_suite+[base+i]
@liste=list(set(liste_suite))
liste.sort()
print(liste)

les "@" représentent les tabulations, que je n'arrive pas à faire dans ce message.

on constate que tous les nombres pairs sont atteignables, et aucun impair.

Remarque qui se généralise en fonction de la parité du plus grand entier de la liste.

 

On peut améliorer pour déterminer le nombre de combinaisons, et afficher les combinaisons également.

1.Une proposition pour montrer "à la main" que tous les nombres pairs sont atteignables :

On part de S = 1+2+3+...+99+100 = 5050

Changer un signe + en signe - revient à soustraire à S le double du nombre qui suit le signe.

Ainsi changer +1 en -1 dans S revient à soustraire 2 à S pour obtenir 5048

En changeant dans S uniquement +2 en -2, on obtient 5046 et ainsi de suite jusqu'à changer + 100 en -100 ; puis on garde -100 et on repart en changeant +1 en -1 et ainsi de suite de 2 en 2 jusqu'à obtenir -5050.

Par symétrie on peut bien sûr partir de -5050

2.Reste la question : combien de décompositions pour chaque nombre ?

Prenons un exemple simple, on veut atteindre 5040.

J'utilise le raisonnement précédent : on part de S = 5050 , on calcule la différence 5050-5040 = 10

On peut donc changer le signe 5 mais aussi les signes de 4 et 1 ou ceux de 3 et 2 : il y a trois solutions qui correspondent aux partitions strictes de 5.

Si je ne dis pas de bêtises, cela reste valable jusqu'à 4850 (et donc aussi entre -5050 et -4850) où il y aura autant de solutions que de partitions strictes de 100 mais après, en suivant ce raisonnement, il y aura des partitions à enlever...et ça ne va pas être de la tarte... déjà que le nombre de partitions strictes d'un nombre, c'est pas du gâteau...(on peut avoir une idée de la suite sur l'OEIS avec les valeurs de 1 à 5000 ici).

@sdumortier

si tu peux donc améliorer ton petit programme pour donner le nombre de décompositions pour chaque nombre, ça serait chouette !

A suivre...

 

 

Bonsoir,

en fait le nombre de façons d'atteindre un nombre pair donné est donné par un coefficient dans un méchant produit eulérien... Dès que tout sera en place, un petit article apparaîtra 🙂

F.D.

Si vous rencontrez des difficultés relatives à l’utilisation du forum, ou si vous souhaitez vous inscrire aux forums pour participer aux discussions, vous pouvez envoyer un courriel à :