Discussion :

[ERCO503]

Bonjour,

Ayant un sondage comportant N participants qui répondent sur une échelle d'entiers de 1 à 10, quelles sont toutes les distributions de résultats possibles qui résulteront en la même moyenne M?

Disons que je fais un exemple simplifié où N = 10, la moyenne M = 2.3 et l'échelle va de 1 à 3, alors les distributions possibles sont :

0, 7, 3
1, 5, 4
2, 3, 5
3, 1, 6

Le premier chiffre est le nombre de réponses "1"
Le deuxième chiffre est le nombre de réponses "2"
Le troisième chiffre est le nombre de réponses "3"

Validation :

(0*1 + 7*2 + 3*3)/10 = 2.3
(1*1 + 5*2 + 4*3)/10 = 2.3
(2*1 + 3*2 + 5*3)/10 = 2.3
(3*1 + 1*2 + 6*3)/10 = 2.3

Y a-t-il une façon mathématique permettant de lister les distributions possibles? Ou bien de savoir combien il y a de différentes possibilités?

C'est possible avec 3 choix de réponses, mais pour 10 choix de réponses?

Avec trois choix de réponses, de 1 à 3 :

T = N*M
R1 + 2*R2 + 3*R3 = T
R1 + R2 + R3 = N

Donc
R1 = R3 - (T - 2*N)
R2 = T - N - 2*R3
T - 2*N <= R3 <= (T - N)/2

Si T = 23 et N = 10
3 <= R3 <= 6.5

On énumère les entiers R3 de 3 à 6 et on peut calculer R1 et R2 à partir de là.

Par exemple, quelles seraient toutes les distributions possibles pour T = 315 et N = 46? (M = T/N)

[wiwaxia]

Bonjour,

Il faut apparemment déterminer le nombre de solutions possibles (x, y, z) pour les équations:
x + y + z = N
x + 2*y + 3*z = T
qui constituent un système indéterminé à un degré de liberté, dont les inconnues sont des entiers naturels, donc positifs ou nuls:
x = R₁, y = R₂, z = R₃ .

# Il faut d'abord délimiter l'ensemble des valeurs possibles pour chacune des variables, dont on sait déjà qu'elles vérifient:
x >= 0 , y >= 0 , z >= 0 .
On en déduit ainsi:
a) y + z = N - x >= 0 ; 2*y + 3*z = T - x >= 0 d'où: x <= N et x <= T , ce qui conduit à x_max = Min(N, T) = Min(46, 315) = 46 ;
b) de même: N - y >= 0 , T - 2*y >= 0 d'où: y_max = Min(N, T/2) = Min(46, 315/2) = 46 ;
c) et enfin: N - z >= 0 , T - 3*z >= 0 d'où: z_max = Min(N, T/3) = Min(46, 315/3) = 46 .

# L'inventaire des solutions devient alors évident, avec des instructions du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Nt:= 0;          // Initialisation du nombre de triplets
FOR x:= 0 TO Xmax DO
  FOR y:= 0 TO Ymax DO
    FOR z:= 0 TO Zmax DO
      BEGIN
        v:= x + y + z; w:= x + (2*y) + (3*z);
        IF ((v=N) AND (w=T)) THEN
          BEGIN
            Nt:= Nt + 1; s:= (10000*x) + (100*y) + z;      // On suppose x, y, z inférieurs à 100
            Liste[Nt]:= s                                  // Triplet mémorisé sous forme d'un entier au format LongInt au plus égal à 999999
          END
      END;

PS: il n'y a aucune solution numérique pour les dernières valeurs proposées, en raison du fait que
x + 2*y + 3*z <= x_max + 2*y_max + 3*z_max = 6*46 = 276 ,
et que la valeur de (T) est plus élevée (T = 315); l'égalité x + 2*y + 3*z = T ne peut donc être réalisée.
Mais ce cas particulier ne remet pas en cause la méthode proposée.

[ERCO503]

Bonjour,

Merci pour la réponse.

Malheureusement, désolé de mon erreur, j'avais oublié de préciser un élément important. Pour l'exemple T = 315 et N = 46, je cherche les solutions pour le cas à 10 variables (sondage d'échelle 1 à 10) et non 3.

Effectivement, pour l'exemple simplifié à 3 variables (échelle 1 à 3), il n'y a pas de solutions pour le cas T = 315 et N = 46 puisque le plus grand total possible serait que les 46 répondants aient tous choisi la valeur 3, donc le total maximal est 46*3 = 138. D'ailleurs, le total minimal est 46*1 = 46 (s'ils répondent tous la valeur 1).

Je n'avais pas donné tous les détails de mon exemples à 3 variables, mais effectivement R1 >= 0, R2 >= 0 et R3 >= 0, puisqu'ils représentent un nombre de répondants pour chaque valeur.

Avec 10 variables (échelles de 1 à 10), il y aura des solutions possibles. T max = 46*10 = 460 et T min = 46*1 = 46

[wiwaxia]

L'algorithme suggéré fonctionne, mais au prix d'un énorme gaspillage calculatoire; il conduit aux résultats obtenus, mais en proportion dérisoire, d'autant plus faible que les données sont plus élevées (quelques triplets sur dix mille à dix millions !).
On obtient ainsi, pour les combinaisons de caractéristiques (N, T = 2*N) où le rapport k = T/N correspond à la moyenne des 3 valeurs envisagées, et pour lesquelles x_max = y_max = N et z_max = (T DIV 3):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
 Xmax =   50  Ymax =   50  Zmax =   33  Ncalc =      88434  Ntrip =         26  Nt/Nc =  2.9E-0004
 Xmax =  100  Ymax =  100  Zmax =   66  Ncalc =     683467  Ntrip =         51  Nt/Nc =  7.5E-0005
 Xmax =  200  Ymax =  200  Zmax =  133  Ncalc =    5413734  Ntrip =        101  Nt/Nc =  1.9E-0005
 Xmax =  400  Ymax =  400  Zmax =  266  Ncalc =   42933867  Ntrip =        201  Nt/Nc =  4.7E-0006
 Xmax =  600  Ymax =  600  Zmax =  400  Ncalc =  144841601  Ntrip =        301  Nt/Nc =  2.1E-0006
 Xmax =  800  Ymax =  800  Zmax =  533  Ncalc =  342614934  Ntrip =        401  Nt/Nc =  1.2E-0006
 Xmax = 1000  Ymax = 1000  Zmax =  666  Ncalc =  668334667  Ntrip =        501  Nt/Nc =  7.5E-0007
 Xmax = 1200  Ymax = 1200  Zmax =  800  Ncalc = 1155363201  Ntrip =        601  Nt/Nc =  5.2E-0007
 Xmax = 1300  Ymax = 1300  Zmax =  866  Ncalc = 1467485067  Ntrip =        651  Nt/Nc =  4.4E-0007
 Xmax = 1400  Ymax = 1400  Zmax =  933  Ncalc = 1833256134  Ntrip =        701  Nt/Nc =  3.8E-0007

Le code implique un nombre de calculs N_calc = (x_max + 1)*(y_max + 1)*(z_max + 1) , soit environ (N³/3) dans le cas présent.

Le défaut rédhibitoire de l'inventaire improvisé (il était tard , ce qui vaut pour circonstance atténuante) est de ne pas tenir compte des restrictions imposées aux 3 termes du triplet, bien qu'elles soient utilisées lors de la détermination des valeurs maximales (x_max, y_max, z_max):

... les équations:
x + y + z = N
x + 2*y + 3*z = T
qui constituent un système indéterminé à un degré de liberté, dont les inconnues sont des entiers naturels, donc positifs ou nuls ...

Les triplets (x, y, z) dépendent donc d'un seul paramètre, et leur inventaire doit se ramener au parcours d'une boucle unique.

Les deux derniers termes admettent pour expression:
y = 3*N - T - 2*x
z = T - 2*N + x ,
et l'exclusion des valeurs négatives conduit à un meilleur encadrement du premier:
# (y >= 0) entraîne (2*x <= 3*N - T) d'où: (x <= (3*N - T)/2 ;
la restriction aux solutions entières donne x_max = (3*N - T) DIV 2 ;
# (z >= 0) entraîne (x >= 2*N - T) ce qui pour un entier naturel (x >= 0) devient: x_min = Max(0, (2*N - T)) .

Enfin les critères d'existence de solutions se déduisent simplement des restrictions précédentes: les bornes vérifiant nécessairement (2*x_max >= 2*x_min) , il vient:
# (3*N - T >= 2*(2N - T)) , qui donne: (T >= N) ,
# (3*N - T >= 0) , qui conduit à: (T <= 3*N) ;
d'où un encadrement de (T) conforme au bon sens, et correspondant à des distributions extrêmes où figurent exclusivement les valeurs (1) ou (3).

Un programme à coup sûr plus efficace et rapide découle des considérations précédentes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
FOR x:= Xmin TO Xmax DO <Calcul(y, z)>

Je n'ai pas le temps d'entrer dans les détails.

Un dénombrement des multiplets (X₁, X₂ ... X₁₀) étendu au cas de 10 valeurs consécutives, à partir des deux équations
X₁ + X₂ + ... X₁₀ = N
X₁ + 2*X₂ + ... + 10*X₁₀ = T
produira des calculs d'une longueur considérable.
L'extension de l'algorithme précédent conduirait logiquement à la construction de (10 - 2) = 8 boucles imbriquées, et à l'exécution d'environ N⁸ étapes élémentaires: là, je crains que cela ne coince un peu .
La prudence recommanderait de commencer par 5 valeurs, par exemple ...

[wiwaxia]

J'ai repris le programme précédent dans le cas de cinq valeurs: comme il comporte encore 3 boucles imbriquées (5 - 2), cela ne pouvait pas être pire.
Les résultats sont même apparus beaucoup plus rapidement, parce que j'avais oublié un filtre d'importance décisive; le taux de réponses positives atteint 37 à 47 % des valeurs calculées dans la partie centrale (T ~ 3*N).

Pour N = 1500 et T = 4500, le programme s'exécute en une vingtaine de secondes, et engrange environ 94 millions de distributions.



La fonction F₅(N, T) donnant le nombre de distributions est maximale en sa partie centrale, pour T = (Tmin + Tmax)/2 = (N + 5*N)/2 = 3*N , et présente une symétrie vis-à-vis de cette dernière: F₅(N, 3*N + h) = F₅(N, 3*N - h) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 
# N_Rep =       1500         T_Rep =       4500               NmaxD =   95000000
   Xmax = 1500  Ymax = 1125  Zmax =  900  Ncalc =  254223301  Ncomb =   94219626
 
# N_Rep =       1500         T_Rep =       4501               NmaxD =   95000000
   Xmax = 1500  Ymax = 1125  Zmax =  900  Ncalc =  254392576  Ncomb =   94219375
 
# N_Rep =       1500         T_Rep =       4499               NmaxD =   95000000
   Xmax = 1499  Ymax = 1124  Zmax =  899  Ncalc =  254054100  Ncomb =   94219375
 
# N_Rep =       1500         T_Rep =       4600               NmaxD =   95000000
   Xmax = 1500  Ymax = 1150  Zmax =  920  Ncalc =  271497216  Ncomb =   93614409
 
# N_Rep =       1500         T_Rep =       4400               NmaxD =   95000000
   Xmax = 1466  Ymax = 1100  Zmax =  880  Ncalc =  237672283  Ncomb =   93614409
 
# N_Rep =       1500         T_Rep =       5000               NmaxD =   95000000
   Xmax = 1500  Ymax = 1250  Zmax = 1000  Ncalc =  345095376  Ncomb =   81172709
 
# N_Rep =       1500         T_Rep =       4000               NmaxD =   95000000
   Xmax = 1333  Ymax = 1000  Zmax =  800  Ncalc =  178645712  Ncomb =   81172709

Cela fait irrésistiblement penser à une randonnée dans le triangle de Pascal. Le problème , c'est de connaître l'itinéraire ...

[wiwaxia]

Il faut que je teste 3 autres versions du programme, pour comparer les temps de calcul. Je suis un peu débordé, là.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# N-Val = 10   N_Rep =          2   T_Rep =         11   NmaxD =   15000000   Temps =       0.00  s
               Ncalc =         36   Ndist =          5
# N-Val = 10   N_Rep =          4   T_Rep =         22   NmaxD =   15000000   Temps =       0.00  s
               Ncalc =        425   Ndist =         43
# N-Val = 10   N_Rep =          6   T_Rep =         33   NmaxD =   15000000   Temps =       0.00  s
               Ncalc =       2660   Ndist =        227
# N-Val = 10   N_Rep =          8   T_Rep =         44   NmaxD =   15000000   Temps =       0.01  s
               Ncalc =      11616   Ndist =        910
# N-Val = 10   N_Rep =         10   T_Rep =         55   NmaxD =   15000000   Temps =       0.01  s
               Ncalc =      39977   Ndist =       2934
# N-Val = 10   N_Rep =         12   T_Rep =         66   NmaxD =   15000000   Temps =       0.03  s
               Ncalc =     116090   Ndist =       8150
# N-Val = 10   N_Rep =         14   T_Rep =         77   NmaxD =   15000000   Temps =       0.05  s
               Ncalc =     296581   Ndist =      20094
# N-Val = 10   N_Rep =         16   T_Rep =         88   NmaxD =   15000000   Temps =       0.16  s
               Ncalc =     685522   Ndist =      45207
# N-Val = 10   N_Rep =         18   T_Rep =         99   NmaxD =   15000000   Temps =       0.24  s
               Ncalc =    1461881   Ndist =      94257
# N-Val = 10   N_Rep =         20   T_Rep =        110   NmaxD =   15000000   Temps =       0.49  s
               Ncalc =    2917645   Ndist =     184717
# N-Val = 10   N_Rep =         24   T_Rep =        132   NmaxD =   15000000   Temps =       1.54  s
               Ncalc =    9921654   Ndist =     610358
# N-Val = 10   N_Rep =         28   T_Rep =        154   NmaxD =   15000000   Temps =       4.36  s
               Ncalc =   28644076   Ndist =    1724882
# N-Val = 10   N_Rep =         32   T_Rep =        176   NmaxD =   15000000   Temps =         11  s
               Ncalc =   72990478   Ndist =    4323349
# N-Val = 10   N_Rep =         36   T_Rep =        198   NmaxD =   15000000   Temps =         28  s
               Ncalc =  168561742   Ndist =    9853759
# N-Val = 10   N_Rep =         40   T_Rep =        220   NmaxD =   15000000   Temps =         54  s
               Ncalc =  359487066   Ndist =   20790704
# N-Val = 10   N_Rep =         44   T_Rep =        242   NmaxD =   15000000   Temps =        102  s
               Ncalc =  717899199   Ndist =   41150848
# N-Val = 10   N_Rep =         46   T_Rep =        253   NmaxD =   15000000   Temps =        139  s
               Ncalc =  993166033   Ndist =   56706832
# N-Val = 10   N_Rep =         46   T_Rep =        191   NmaxD =   15000000   Temps =        119  s
               Ncalc =  594182436   Ndist =   21976554
# N-Val = 10   N_Rep =         46   T_Rep =        315   NmaxD =   15000000   Temps =        139  s
               Ncalc = 1040125575   Ndist =   21976554