[RESOLU] casse-tête de dénombrement

[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 :
[INDENT]Combien de personnages différents peut-on créer dans le jeu Ultima Online ?[/INDENT]

Bonne chance :we:

[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 :we:

[nodgim]

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 :we:

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.

[nodgim]

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.

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

[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! :cry:

[Patastronch]

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 :we:

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 .

[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 ?

[nodgim]

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. :doh:

[wkta]

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 :we:

Vous prétendez qu'il y a "p-1 parmi n+p-1" possibilités d'écrire un nombre n avec p nombres.
[INDENT]
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
[/INDENT]

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. :ptdr:

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 ! :we:

[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

[wkta]

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 ?

[Patastronch]

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.

[ThSQ]

Ca revient à trouver le nombre de solution de

avec

Sans contraintes le nombre de solution est

Si u_i est le nombre de solutions avec 'i' nombres > 100


Le nombre cherché est d'après le principe d'inclusion-exclusion

[Patastronch]

...

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

[wkta]

:triste:

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é).

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.

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

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

[...] 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")

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.

[...] 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.

[Patastronch]

...

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.

[ThSQ]

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

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

[Patastronch]

Si u_i est le nombre de solutions avec 'i' nombres > 100

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

[Imod]

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

[ThSQ]

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

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