Mathématiques - casse-tête de dénombrement

casse-tête de dénombrement
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: wkta

Je vous présente un problème réel que j'ai essayé de résoudre et qui est plus difficile qu'il n'en a l'air. Ultima Online est un jeu vidéo se jouant sur Internet. Il est considéré comme l'un des jeux les plus riches et complexes qui soient.

Dans ce jeu, le joueur construit son personnage en distribuant 700 points de compétence parmi 49 compétences différentes. Toutefois, une unique compétence ne peut dépasser la valeur 100.

Exemples :

La première idée du joueur est de choisir 7 compétences et d'y placer 100 points.
Les joueurs expérimentés aiment se risquer à quelques "panachages" en affectant, par exemple, 100 points à six compétences, 80 à une septième, et 20 à une dernière.
Pour rire, on peut faire un personnage avec 14 dans toutes les compétences du jeu puis 28 dans sa compétence préférée. (48*14+28 = 700, le compte est bon)

Enigme :

Combien de personnages différents peut-on créer dans le jeu Ultima Online ?

Bonne chance

Posted by: lapras

salut
On peut utilise la formule :
il y a (n+p-1 ; p-1) possibilités d'écrire n=700 comme somme de p nombres
apres on a plus qu'a faire varier p et sommer

Posted by: nodgim

Citation:

Posté par lapras

salut
On peut utilise la formule :
il y a (n+p-1 ; p-1) possibilités d'écrire n=700 comme somme de p nombres
apres on a plus qu'a faire varier p et sommer

Je crains que ce ne soit légèrement plus compliqué. Si on met 600 points dans 6 compétences données, et si on répartit les 100 points restants dans les 43 compétences restantes, c'est déja un sacré problème de trouver toutes les combinaisons!
C'est l'immense problème de la partition d'un nombre en sommes.
Hardy-Ramanujan ont trouvé une solution extrêmement complexe, un peu améliorée par la suite, mais elle a l'inconvénient d'être presque aussi longue que la solution par récurrence. Je sais qu'un américain s'est attelé à la tàche sur ce sujet, ses résultats ont été publiés dans un livre, je n'en connais pas la teneur.

Posted by: nodgim

Citation:

Posté par nodgim

Je rectifie ma première version, il ne sagit pas tout à fait d'une sommation. J'y réfléchis un peu...

Posted by: nodgim

Donc, plus complexe que la sommation!
Par exemple, 7 points, à distribuer dans 4 compétences, peuvent être décomposés en 11 sommes:
2221, 3211, 331, 322, 4111, 421, 43, 511, 52, 61, 7.
Chacune de ces décompositions est réparties de plusieurs façons dans les 4 compétences. Nombre respectif de distributions pour chaque décomposition:
4,12,12,12,4,24,12,12,12,12,4 soit 120 distributions possibles.

Bien plus grand que C(7,4) mais bien plus petit que 7!

Posted by: Patastronch

Citation:

Posté par lapras

salut
On peut utilise la formule :
il y a (n+p-1 ; p-1) possibilités d'écrire n=700 comme somme de p nombres
apres on a plus qu'a faire varier p et sommer

Presque, il faut prendre en compte le fait que 100 est une borne pour chacun de tes p nombres.
Il faut donc calculer le nombres de maniere de sommer a 700 avec des nombres compris entre 0 et 100 (et non entre 0 et 700) et en faisant les distinctions entre chaque permutations. Par exemple si on a 2 points , il faut différentier 0+2 de 2+0 .

Posted by: alben

Bonjour,
Si l'on néglige la contrainte <101, la formule de Lapras est exacte, il n'y a pas besoin de sommer, le résultat est directement "48 parmi 748", soit 15.10^75.
C'est énorme et je ne pense pas que la contrainte élimine beaucoup de cas.
On doit pouvoir estimer ces derniers ?

Posted by: nodgim

Citation:

Posté par alben

Bonjour,
Si l'on néglige la contrainte <101, la formule de Lapras est exacte, il n'y a pas besoin de sommer, le résultat est directement "48 parmi 748", soit 15.10^75.
C'est énorme et je ne pense pas que la contrainte élimine beaucoup de cas.
On doit pouvoir estimer ces derniers ?

Exact, ça marche, bien sûr à la contrainte près.

Posted by: wkta

Citation:

Posté par lapras

On peut utilise la formule :
il y a (n+p-1 ; p-1) possibilités d'écrire n=700 comme somme de p nombres
apres on a plus qu'a faire varier p et sommer

Vous prétendez qu'il y a "p-1 parmi n+p-1" possibilités d'écrire un nombre n avec p nombres.

Voyons ce que donne votre formule avec n = 2

On admet qu'il n'est pas possible d'écrire un entier n en moins de 1 nombre, ni de l'écrire en plus de n nombres entiers.
écrire 2 en 1 nombre (n=2, p=1)
"1-1 parmi 2+1-1" = "0 parmi 2" = 1
écrire 2 en 2 nombres(n=2, p=2)
"2-1 parmi 2+2-1" = "1 parmi 3" = 3

On somme : 1+3 = 4

Comment pouvez-vous raisonnablement considérer que cette formule "marche" ?! 2 peut être partagé en deux sommes : 2 et 1+1 et non en 4.
Par la suite, il faudrait dénombrer les permutations possibles de 2 puis de 1 et 1 (l'ensemble des partages possibles, en fait) dans un "vecteur" à 49 composantes...

on obtient 49 (possibilités de placer le chiffre 2, avec des 0 partout ailleurs)
+ "2 parmi 49" (possibilités de placer deux chiffres 1, avec des 0 partout ailleurs)
= 49 + 1176 = 1225 ce qui est loin de votre résultat.

Dans mon énoncé, n=700 et p appartient à l'ensemle { 7, ... 49 }. (Donc la contrainte a beaucoup d'importance !) Merci de relire le problème. J'avais prévenu qu'il est plus difficile qu'il n'en a l'air.

Citation:

Posté par alben

le résultat est directement "48 parmi 748", soit 15.10^75. C'est énorme et je ne pense pas que la contrainte élimine beaucoup de cas.

Comment justifiez vous cela ? Une unique contrainte peut faire passer un ensemble de solutions de l'intervalle [ -infini, +infini ] à l'ensemble vide.
Des affirmations intuitives portées à de telles échelles de grandeur sont absurdes, à mon humble avis. Quoiqu'il en soit, votre réponse est fausse, car vous utilisez la formule donnée par lapras qui est elle même fausse, comme le prouve mon contre-exemple.

Essayez encore !

Posted by: Imod

Exposer un problème , s'absenter pendant dix jours et revenir pour noter les copies avec un petit commentaire : à revoir au plus vite !!!!
Curieuse façon de procéder .

Imod

Posted by: wkta

Citation:

Posté par Imod

Exposer un problème , s'absenter pendant dix jours et revenir pour noter les copies avec un petit commentaire : à revoir au plus vite !!!!
Curieuse façon de procéder .

Imod

Sans vouloir vous manquer de respect, à quoi sert votre message ?

Posted by: Patastronch

Citation:

Posté par wkta

Vous prétendez qu'il y a "p-1 parmi n+p-1" possibilités d'écrire un nombre n avec p nombres.

Voyons ce que donne votre formule avec n = 2

On admet qu'il n'est pas possible d'écrire un entier n en moins de 1 nombre, ni de l'écrire en plus de n nombres entiers.

* écrire 2 en 1 nombre (n=2, p=1)
"1-1 parmi 2+1-1" = "0 parmi 2" = 1
* écrire 2 en 2 nombres(n=2, p=2)
"2-1 parmi 2+2-1" = "1 parmi 3" = 3

On somme : 1+3 = 4

Comment pouvez-vous raisonnablement considérer que cette formule "marche" ?! 2 peut être partagé en deux sommes : 2 et 1+1 et non en 4.

2+0 est a différentier de 0+2. Premiere remarque.
Deuxieme remarque, le nombre de possibilité d'ecrire 2 avec 2 nombres n'est pas la sommes du nombre de possibilité d'ecrire 2 avec 1 nombre et du nombre de possibilité de l'ecrire avec 2 nombres. Donc on somme pas comme tu le clame abusivement, on garde juste ton 3.
Oh miracle, le 3 correspond bien aux 3 possibilités : 0+2, 1+1 et 2+0.

Bon deja que le probeme est assez ininteressant mais si en plus l'auteur ne fiat aucun effort et se permet de descendre les intervenants parcequ'il comprends rien a ce qui est dit, ca se fera sans moi.

Posted by: ThSQ

Ca revient à trouver le nombre de solution de

$\sum_1^{49} a_i = 700$ avec $0 \leq a_i \leq 100$

Sans contraintes le nombre de solution est $u_0 = C_{700+49-1}^{49-1}$

Si u_i est le nombre de solutions avec 'i' nombres > 100
$u_i = C_{49}^i C_{700 - 100*i +49-1}^{49-1}$

Le nombre cherché est $u_0 - u_1 + u_2 - u_3 ...$ d'après le principe d'inclusion-exclusion

Posted by: Patastronch

Citation:

Posté par ThSQ

...

Je comprends pas le sens de ton u_i et (donc) son calcul. Tu peux eclaircir stp ?

Posted by: wkta

J'avoue que je ne comprends pas en quoi "je descends" quelqu'un ? Si je me suis mal exprimé je m'en excuse sincèrement.

Je voulais donner un contre-exemple clair et précis en re-précisant les données pour éviter des hors-sujets (qui surviennent lorsque l'on ignore une partie de l'énoncé).

Citation:

Posté par Patastronch

2+0 est a différentier de 0+2. Premiere remarque.

Oui, biensûr. 0+2 doit être différencié de 2+0 mais il ne s'agit pas d'écrire le partage de 2 et de commuter les chiffres. Il s'agit d'attribuer une valeur séparée à 49 composantes. En suivant ta logique, tu dois comprendre que 0+0+0+...+0+2 (48 zéros puis 2) est à différencier de 0+0+...+2+0. (47 zéros puis 2 puis 0) Une notation plus adaptée pour modéliser une instance est un vecteur à 49 composantes, de nombres entre 0 et 100.

Citation:

Posté par Patastronch

Donc on somme pas comme tu le clame abusivement, on garde juste ton 3.

Sommer n'est pas mon idée, la preuve :

Citation:

Posté par lapras

[...] apres on a plus qu'a faire varier p et sommer

Les personnes qui, par la suite, ont suggéré de ne PAS sommer, utilisaient de toute manière la formule donnée par lapras, qui ne répond pas au problème, pour les raisons explicitées dans ma précédente réponse. (on ne dénombre pas les possibilités d'attribuer des points, on dénombre "autre chose")

Citation:

Posté par Patastronch

Bon deja que le probeme est assez ininteressant

J'accorde à tout le monde le droit de juger mon sujet inintéressant. Pas de souci. Toutefois, j'ai tendance à penser que quelqu'un de mature s'abstiendrait tout simplement de poster sur un sujet qu'il juge inintéressant.

Citation:

Posté par Patastronch

[...] mais si en plus l'auteur ne fiat aucun effort et se permet de descendre les intervenants parcequ'il comprends rien a ce qui est dit, ca se fera sans moi.

Je peux t'assurer que j'ai porté beaucoup d'attention à ce qui a été dit, et je ne comprends absolument pas en quoi je descends les intervenants (ai-je insulté quelqu'un ou est-ce le vouvoiement qui n'est pas d'usage ici ? je ne vois pas désolé). Dommage. Salut.

Posted by: Patastronch

Citation:

Posté par wkta

...

Aucune importance, pas envie de rentrer dans un débat dont la finalité ne m'interesse que tres peu et dont les arguments des 2 cotés risquent de rimer avec mauvaise foi.
Par contre l'idée de ThSQ semble etre la bonne j'aimerais comprendre la fin de son raisonnement.

Posted by: ThSQ

<blablablah pacificateur>Peace and love men ...

J'ai pas lu toutes vos passionnantes discussions mais je crois que plutôt que de l'arrogance unilatérale il y a beaucoup d'incompréhension multilatérale ...
Internet et son absence de "checksum/error detection coding" visuel fait qu'un excès d'humour ou de passion est vite mal interprété.</blablablah pacificateur>

Pour revenir à nos moutons. Il y a une formule, bien connue, si on ne prend pas de contraintes. u_i c'est le nombre de solutions si on impose 'i' contraintes (à savoir 'i' a_j >= 100).

Posted by: Patastronch

Citation:

Posté par ThSQ

Si u_i est le nombre de solutions avec 'i' nombres > 100
$u_i = C_{49}^i C_{700 - 100*i +49-1}^{49-1}$

Bon je suppose que c'est pour i>0 sinon si on a i=0 nombre superieur a 100 la formule renvoit le nombre totale de possibilités sans la contrainte. Dit moi si je me trompe mais j'ai l'impression que ta formule ne différentie pas les 2 cas suivants (pour i=1) : 700,0,...,0 et 699,1,0,...,0

Si c'est pas le cas dit le moi que je me prenne le chou a comprendre ton expression.

Ce que je comprends pas également c'est le calcul final :
Pourquoi c'est u_0-u_1+u_2-u_3... et non u_0-u_1-u_2-u_3... ?

Posted by: Imod

Citation:

Posté par wkta

Sans vouloir vous manquer de respect, à quoi sert votre message ?

Pour votre problème ? Sans doute à rien ! J'attendais simplement un petit message de courtoisie à l'égard de ceux qui avaient pris la peine de répondre et pas seulement l'étalage de leurs fautes . Désolé pour ma grossièreté !

Imod

Posted by: ThSQ

Citation:

Posté par Patastronch

u_1 c'est il y a au moins un a_i hors borne donc si je comprends bien la formule ne différentie pas tes deux cas.

Et, à mon avis, c'est u_0-u_1+u_2-u_3 bicoze PIE

Posted by: wkta

Citation:

Posté par Imod

[...] J'attendais simplement un petit message de courtoisie à l'égard de ceux qui avaient pris la peine de répondre et pas seulement l'étalage de leurs fautes [...]

Vous avez raison ! Mais où avais-je la tête ?!
Merci à tous, merci beaucoup pour vos réponses !!

Voilà où j'en suis :

J'ai bien compris l'utilisation du principe d'inclusion-exclusion (son utilisation s'avère nécessaire, bien joué ThSQ !) mais quelqu'un peut-il me dire où trouver (ou me rappeler) la justification de $u_o$ s'il vous plaît ?

D'autre part, j'ai l'impression (pour l'instant je ne peux l'affirmer vu que je ne sais pas justifier $u_o$ ) que les $u_i$ dénombrent les solutions avec i composantes exactement égales à 100, non pas i composantes strictement supérieures à 100.
Cette intuition me vient premièrement de l'observation de ( 700-100*i + 49-1 ) qui joue le rôle de "n" dans le deuxième terme de l'équation définissant $u_i$ Deuxièmement, en calculant $u_7$ , on remarque que
$u_7 = C_{49}^7 C_{700-100*7+49-1}^{49-1}$
$\Rightarrow u_7 = C_{49}^7 C_{49-1}^{49-1}$
$\Rightarrow u_7 = C_{49}^7$
Ce nombre est égal au nombre de possibilités de choisir 7 compétences parmi 49 pour y placer exactement 100 points.

S'il y a effectivement erreur dans la définition de $u_i$ , $u_0 + [ -u_1 +u_2 -u_3 +...]$ donnerait un nombre bien trop grand par rapport au nombre recherché, car ce dénombrement contiendrait encore beaucoup de combinaisons avec des $a_i > 100$ , ce que l'on ne souhaite pas. Suis-je dans le vrai ?

Posted by: ffpower

Imagine 748 batonnnets alignés.Si on selectionne 48 et qu on les retire,ca te donne 49 groupes de batonnets et ca correspond a une decompositon de 700.Avoir toutes les decompositions revient a voir le nb de facons d enlever 48 batonnets parmi les 748,d ou la formule..

Posted by: ThSQ

Citation:

Posté par wkta

[INDENT]i composantes exactement égales à 100

Mon idée c'était au moins 'i' égales ou supérieures à 100.