|
#1 - 21-07-2020 19:08:31
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Encore une somme de chiffre
Bonsoir @ tous.
L'énigme précédente concernait des nombres en binaire à somme de chiffres constante. On parvenait assez facilement à s'en sortir par l'intermédiaire du calcul des combinaisons. Dans ce nouveau problème, c'est un petit peu plus compliqué....
Soit " a " un entier positif à 4 chiffres, et l'intervalle [a; 10^4-1]
Trouver " a " tel que le nombre de nombres à somme de chiffres = somme de chiffres de " a " est maximal. Trouver aussi le nombre de nombres dans l'intervalle.
Généralité pour les plus inspirés: même question pour le max de " a " à k chiffres ( on demande ici seulement " a " et pas le nombre de nombres de l'intervalle).
Bon courage.
PS: ça se fait à la main.
#2 - 21-07-2020 21:33:14
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
enxore une somme de chiffres
Phrase trop longue, j'ai mal à la tête... Sans certitude, je dirais 1089 - je pense que 18 arrive en tête des "sommes communes" et c'est le plus petit 18. Ou alors c'est 1099. Faudrait que je compte le nombre de nombres pour être sur.
Edit : je précise: 18, parce que au max on a 9999 => 36, et 18 ou 19 sont à la moitié
#3 - 21-07-2020 22:33:44
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
Encore une smme de chiffres
Pour [latex]4[/latex] chiffres on trouve [latex]a=99[/latex] avec [latex]670[/latex] nombres ayant pour somme [latex]18[/latex] dans l'intervalle [latex][99;\,9999][/latex]
Plus généralement pour [latex]k[/latex] chiffres :
[latex]a=\underbrace{9\ldots 9}_{\frac{k}{2}\,\mathrm{fois}}[/latex] si [latex]k[/latex] est pair. [latex]a=4\underbrace{9\ldots 9}_{\frac{k-1}{2}\,\mathrm{fois}}[/latex] si [latex]k[/latex] est impair.
#4 - 22-07-2020 07:29:09
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Encore une somme de cchiffres
Est-ce que -9900 compte comme un nombre à 4 chiffres ?
#5 - 22-07-2020 08:58:14
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
encore une somme de chiffrrs
Je parle pour " a " d'un entier > 0 à 4 chiffres significatifs, donc ne commençant pas par 0.
@ Scarta: ta 1ère réponse est sur la bonne voie, reste à finaliser.
#6 - 22-07-2020 16:04:26
- TOUFAU
- Professionnel de Prise2Tete
- Enigmes résolues : 0
- Messages : 105
Encore une somme d chiffres
Avec a = 1089, je trouve 615 nombres dont la somme des chiffres vaut 18 entre a (inclus) et 10^4-1 (615 = 2*∑i² + ∑i entre 1 et 9)
Le max est obtenu quand la somme des chiffres vaut 4,5k (ou l’entier supérieur quand k est impair). Pour la même raison qu’il vaut mieux miser sur 7 quand on lance 2 dés… Le plus petit de la bande est facile à trouver.
Par exemple a=10499 pour k=5 ; a=100899 pour k=6
Plus généralement a = 10^(k-1) + 9*10^(k/2-1) – 1 si k est pair a = 10^(k-1) + 5*10^((k-1)/2) – 1 si k est impair
#7 - 22-07-2020 16:47:13
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Encore un esomme de chiffres
@ Toufau : parfait
As-tu une justification pour la généralité ?
#8 - 22-07-2020 18:03:04
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
enxore une somme de chiffres
Autant pour moi, ça ne change pas grand chose mais du coup :
Pour [latex]4[/latex] chiffres significatifs on trouve [latex]a=1089[/latex] avec [latex]615[/latex] nombres ayant pour somme [latex]18[/latex] dans l'intervalle [latex][1089;\,9999][/latex]
Plus généralement pour [latex]k>2[/latex] chiffres significatifs :
[latex]a=1\underbrace{0\ldots 0}_{\frac{k-2}{2}\,\mathrm{fois}}8\underbrace{9\ldots 9}_{\frac{k-2}{2}\,\mathrm{fois}}[/latex] si [latex]k[/latex] est pair. [latex]a=1\underbrace{0\ldots 0}_{\frac{k-3}{2}\,\mathrm{fois}}4\underbrace{9\ldots 9}_{\frac{k-1}{2}\,\mathrm{fois}}[/latex] si [latex]k[/latex] est impair.
#9 - 22-07-2020 18:14:10
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Ecore une somme de chiffres
@ Sydre : très bien !
Même remarque que pour Toufau.
Au fait, personne n'a envisagé la non-unicité du max.....
#10 - 22-07-2020 19:02:35
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Encore un somme de chiffres
ben si moi - sauf que j'avais pas fait le decompte. Mais bref, si 1089 aurait fait mieux sur 0..9999, il fait pareil que 1099 sur 1000..9999 (à savoir 615)
#11 - 23-07-2020 08:02:25
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Encoore une somme de chiffres
Ah aussi, si un tableur n'est "qu'une aide au calcul" comme la dernière fois, n lignes suffisent pour sortir le résultat pour n chifres
#12 - 23-07-2020 09:30:22
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Encore uune somme de chiffres
Intéressant, Scarta !
Des précisions ?
#13 - 23-07-2020 10:01:10
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Encore ue somme de chiffres
Ben du dynamique progamming, version Excel
Ligne 1 : 1, suivi de 9*N zéros Ligne 2 A2: Sum($A1, A1), on copie A2 jusqu'en J2 K2: Sum(B1:K1), on copie K2 jusqu'à la 9N+1ème cellule Lignes suivantes : copie de la ligne 2 Ligne N+1 : 1ere colonne : 0 2eme colonne : sum($An,An), copiée jusqu'en Jn Kn: Sum(Bn:Jn), on copie Kn jusqu'à la 9N+1ème cellule
Et voilà !
L'équivalent en Excel donc du code suivant
#14 - 24-07-2020 08:19:15
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
encore ube somme de chiffres
OK, Scarta. Je n'ai pas tout compris à ton algo, ça m'a l'air super efficace.
@ tous : cependant il reste du non-dit:
Plusieurs réponses correctes sur la généralisation, cela dû peut-être à l'intuition qui nous pousse à chercher les valeurs moyennes ( ou plus simplement, ce sont les calculs aidés qui ont donné ce résultat ? ) mais quid de la preuve ?
#15 - 24-07-2020 09:23:01
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Encore une omme de chiffres
L'algo en 2 mots : je dispose de N chiffres
- avec 0 chiffre, je peux faire une somme de 0 d'une seule manière, et toutes les autres sommes jusqu'à 9N de zéro manière (je peux pas quoi)
- avec un chiffre de plus, je peux faire une somme S d'autant de manières que je pouvais faire S-9, S-8, S-7, etc... avec un chiffre de moins (puisque j'ajoute ce nouveau chiffre au nombre)
et bien entendu, on répète le processus pour chaque chiffre qu'on ajoute
- la seule particularité, pour le dernier chiffre qu'on ajoute : il ne peut pas être 0.
Et en écrivant ces lignes, je me rends compte qu'on peut faire encore plus simple : plutôt que de forcer le dernier chiffre, on peut forcer le premier Du coup, l'initialisation du tableau, au lieu d'être t[i] = 1 pour i = 0 et 0 sinon, on met t[i] = 1 pour 1 <= i <= 9 et 0 sinon, et on traite les n-1 chiffres suivants sans cas particulier pour le dernier
|
|