Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

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

  • |
  • Répondre

#0 Pub

 #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 ? big_smile

 #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 roll

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 smile

 #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 smile

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

Code:

int n = 4, i, j, k;
int[] res = new int[n * 9 + 1];
res[0] = 1;
for (i = 1; i < n; i++)
   for (j = n * 9; j >= 0; j--)
      for (k = 1; k <= 9 && k <= j; k++) res[j] += res[j - k];
for (j = n * 9; j >= 0; j--)
   for (k = 1, res[j] = 0; k <= 9 && k <= j; k++) res[j] += res[j - k];

 #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 smile
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


Code:

long i, j, k;
long n = 4;
long[] res = new long[n * 9 + 1];
for (i = 1; i <= 9; i++) res[i] = 1;
for (i = 1; i < n; i++)
    for (j = n * 9; j >= 0; j--)
        for (k = 1; k <= 9 && k <= j; k++)
            res[j] += res[j - k];
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete