Analyse combinatoire

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
rhdt
Messages: 1
Enregistré le: 31 Jan 2021, 21:27

analyse combinatoire

par rhdt » 31 Jan 2021, 21:34

Bonjour! Je n'arrive pas à trouver la solution pour la question suivante: Parmi tous les entiers de 1 à 1 000 000, combien y en a-t-il dont la somme des chiffres est égale à 10?



GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: analyse combinatoire

par GaBuZoMeu » 01 Fév 2021, 10:52

Bonjour,

Ça revient à compter les 6-uplets d'entiers naturels de somme 10, en retirant les 6-uplets constitués d'un 10 et de cinq 0, qui sont faciles à compter.

phyelec
Membre Rationnel
Messages: 946
Enregistré le: 06 Mar 2020, 18:47

Re: analyse combinatoire

par phyelec » 01 Fév 2021, 15:44

Bonjour,

@GaBuZoMeu,j'ai compris que c'était :

Pisigma
Habitué(e)
Messages: 3063
Enregistré le: 22 Déc 2014, 01:38

Re: analyse combinatoire

par Pisigma » 02 Fév 2021, 15:46

Bonjour,

à l'aide d'un PGM en Python, je trouve 2997

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: analyse combinatoire

par fatal_error » 02 Fév 2021, 16:41

hi,

pas besoin de programme
pour faire le compte des (x_1,...x_6) de somme 10 on peut appliquer stars and bars https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

idem
la vie est une fête :)

Pisigma
Habitué(e)
Messages: 3063
Enregistré le: 22 Déc 2014, 01:38

Re: analyse combinatoire

par Pisigma » 02 Fév 2021, 18:26

@fatal_error

déjà j'ai un bugg dans mon pgm (écrit en vitesse sans trop réfléchir!!) puisque je ne trouve pas la même valeur.

Quant à ce que tu proposes, je ne connaissais pas. Pourrais-tu m'en dire un peu plus?

Merci d'avance

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: analyse combinatoire

par GaBuZoMeu » 02 Fév 2021, 18:33

Bonjour,

Plutôt que de faire l'exo à la place du demandeur, lisez soigneusement ce que j'ai écrit : il faut retirer les 6-uplets constitué d'un 10 et de cinq 0. ;)

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

Re: analyse combinatoire

par mathelot » 02 Fév 2021, 18:37

bjr,
je trouve 3087 en dénombrant à la main. Je peux lister les résultats si le total est faux..
Modifié en dernier par mathelot le 02 Fév 2021, 23:23, modifié 1 fois.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: analyse combinatoire

par GaBuZoMeu » 02 Fév 2021, 18:39

C'est faux, mathelot.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: analyse combinatoire

par fatal_error » 02 Fév 2021, 18:42

nan mais je suis ok avec toi Pisigma
3003 - 6 == 2997

evidemment le programme est trivial
Code: Tout sélectionner

let ok = 0
for (let a = 0; a <= 9; ++a) {
  for (let b = 0; b <= 9; ++b) {
    for (let c = 0; c <= 9; ++c) {
      for (let d = 0; d <= 9; ++d) {
        for (let e = 0; e <= 9; ++e) {
          for (let f = 0; f <= 9; ++f) {
            if (a+b+c+d+e+f === 10) {
              ok++
            }
          }
        }
      }
    }
  }
}
console.log('ok : ', ok)


Pourrais-tu m'en dire un peu plus?

je pense pas faire mieux que wiki mais bon

l'idée c'est juste de considérer 6 containeurs
un pool de 10 elem
et on repartit ce pool dans les 6 containeurs (du coup ben la somme du compte des elem des containeurs vaut tjs 10...)
pour assigner les containeurs on rajoute 5 virtuels containeurs aux 10x:
xxxxxxxxxxooooo
le premier o prend tout ce qui est à gauche (ici 10)
xoxxxxxoxoxxxooo (ici le deuxieme o prend 5)
et on prend 5 et pas 6o car le "dernier" containeur est à droite du dernier o

au final il suffit alors de "piocher" 5o parmi les 15 positions (idem k-1, n+k-1)
la vie est une fête :)

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

Re: analyse combinatoire

par mathelot » 02 Fév 2021, 18:44

GaBuZoMeu a écrit:lisez soigneusement ce que j'ai écrit : il faut retirer les 6-uplets constitué d'un 10 et de cinq 0. ;)


Ces 6-uplets, la somme de leurs chiffres vaut 1 ? pourquoi les retirer d'un ensemble de nombres dont la somme des chiffres vaut 10?
Modifié en dernier par mathelot le 02 Fév 2021, 19:34, modifié 1 fois.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: analyse combinatoire

par GaBuZoMeu » 02 Fév 2021, 18:46

Enfin voyons mathelot, 10 est un chiffre pour toi ? Pour ta gouverne, les chiffres sont 0,1,2,...,9.

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

Re: analyse combinatoire

par mathelot » 02 Fév 2021, 18:59

GaBuZoMeu a écrit:Bonjour,

Ça revient à compter les 6-uplets d'entiers naturels de somme 10, en retirant les 6-uplets constitués d'un 10 et de cinq 0, qui sont faciles à compter.



je n'ai pas compris cette assertion ci-dessus : peux tu me donner un exemple d'un 6-uplet que tu retires ?

phyelec
Membre Rationnel
Messages: 946
Enregistré le: 06 Mar 2020, 18:47

Re: analyse combinatoire

par phyelec » 02 Fév 2021, 19:45

Bonjour,

pour , voici ce que j'ai trouvé :
- de 1 à 100 , il y 9 nombre dont la somme des chiffres vaut 10
- de 100 à 1000 , il y 54 nombre dont la somme des chiffres vaut 10
- de 1000 à 10000 , il y 219 nombre dont la somme des chiffres vaut 10
- de 10000 à 100000 , il y 714 nombre dont la somme des chiffres vaut 10
- de 100000 à 100000, il y 2001 nombre dont la somme des chiffres vaut 10
donc 2997 au total, même résultat que Fatal_error et Pisigma

j'ai fais un programme sous Scilab :
---------------------------------------------------------------------------------------------------------------------
//initialisation nombre de 1 à 100
n1=1
n=100
nb=0
for i=n1:n
sti=string(i);
s1=0;
for j=1:length(sti)
a=part(sti,j);
s=strtod(a)+s1;
s1=s;
end ;
if s==10 then nb=nb+1; end ;
end
S=zeros(5) //matrice par tranches avec le nombre de fois que la somme vaut 10
c=zeros(9,5) //matrice des colonnes par tranches avec le nombre de fois que la somme vaut 10
S(1)=nb //S(1)=9
disp("nb=",nb)

//les autres par tranches avec la boucle sur i :
//de 100 à 1000
//de 1000 à 10000
//de 10000 à 100000
//de 100000 à 1000000
//
//total = 9 +54 +219 +714 +2001 +5004 = 8001//
k=2 //indice de colonne , la colonne 1 est celle 100 à 1000
for i=2:5
s0=S(i-1)+1 //somme de la tranche précédente +1
c(1,k-1)=s0 //le premier chiffre de chaque colonne de chaque tranche
s=c(1,k-1) // initialisation de l'itération de la somme de la colonne
l=0 //indice de ligne
for j=2:9 //pour remplir les colonnes de c et calculer la somme de la tranche
a=c(j-1,k-1)
l=l+1 //indice de ligne pour parcourir la colonne précédente
if i==2 then b=1, else b=c(l,i-2),end; //de1 à 100 on a 1 cas par dizaine ( sauf de 0 à 10)
S(i)=a-b
c(j,k-1)=S(i)
s=S(i)+s //somme de la tranche à chaque itération
end
S(i)=s somme
end
--------------------------------------------------------------------------------------------------------------

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: analyse combinatoire

par GaBuZoMeu » 02 Fév 2021, 20:59

mathelot a écrit:je n'ai pas compris cette assertion ci-dessus : peux tu me donner un exemple d'un 6-uplet que tu retires ?

Ce n'est pourtant pas compliqué ! Le 6-uplet d'entiers (0,0,0,10,0,0) de somme 10 n'est pas bon car 10 n'est pas un chiffre.

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

Re: analyse combinatoire

par mathelot » 02 Fév 2021, 21:09

j'ai compris. Merci pour ta réponse.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: analyse combinatoire

par fatal_error » 02 Fév 2021, 21:56

@phyelec
toujours en allant dans la voie du basique, on peut juste itérer de 0 à 100000 et compter par tranche
Code: Tout sélectionner
const sums = {}
;[100,1000,10000,100000,1000000].reduce((left, right) => {
  for (let i = left; i < right; ++i) {
    const sum = String(i).split('').map(x => parseInt(x, 10)).reduce((s, i) => s + i, 0)
    if (sum === 10) {
      sums[left] = (sums[left] || 0) + 1
    }
  }
  return right
}, 0)
console.log('sums', sums)
console.log('total', Object.values(sums).reduce((s, i) => s + i, 0))
/*
sums { '0': 9, '100': 54, '1000': 219, '10000': 714, '100000': 2001 }
total 2997
*/
la vie est une fête :)

Pisigma
Habitué(e)
Messages: 3063
Enregistré le: 22 Déc 2014, 01:38

Re: analyse combinatoire

par Pisigma » 02 Fév 2021, 22:22

@fatal_error : merci pour les infos :)

phyelec
Membre Rationnel
Messages: 946
Enregistré le: 06 Mar 2020, 18:47

Re: analyse combinatoire

par phyelec » 02 Fév 2021, 23:30

@fatal_error : tout à fait d'accord.

phyelec
Membre Rationnel
Messages: 946
Enregistré le: 06 Mar 2020, 18:47

Re: analyse combinatoire

par phyelec » 03 Fév 2021, 00:43

@fatal_error : voici quelques informations sur mon programme.

Dans mon programme je n'additionne pas les chiffres des nombres pour savoir si leur somme vaut 10.
J'ai d'abord calculer le nombre dont la somme des chiffres vaut 10 de 1 à 100 en allant de 10 en 10 (sous-tranche de 10)
puis la somme des chiffres valant 10 de 100 à 1000 en allant de 100 en 100 etc.., pour ce faire
j'ai remarqué que la somme des chiffres valant 10 de la première sous tranche (de la tranche en cours) vaut la somme de la tranche précédente +1. Les autres valeurs de la tranches en cours de sous tranches valent la valeur précédente de tranche-en-cours moins la valeur de la sous tranche précédente ( luis corresponds)
54=55+1
45=55-10
36=45-9
........
Du coup, il y a très peu de calcul et cela va très vite.




j'espère ne pas vous ennuyer en vous donnant plus de détail sur mon programme.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 21 invités

cron

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite