Combinatoire

[Cliffe]

Bonjour à tous,

J'avais déjà posé ce problème sur ce forum dans une autre section mais personne n'a réussi à le résoudre. Je le repose donc dans cette section :


Je souhaite créer des QCM.

J'ai n questions différentes.

Chaque QCM contient p questions.

Je doit avoir 25% de questions différentes entre 2 QCM.

Combien de QCM je peux faire ?

[beagle]

"Chaque QCM contient p questions"

je ne comprends pas,
j'en suis resté à QCM= 1 question à choix multiples de réponses
on choisit la réponse qui répond à la question

ici on a la réponse et un choix multiple de questions, j'ai bien rien compris?

[Cliffe]

Je vois QCM comme Questionnaire à choix multiples.

Il est composé de plusieurs questions qui ont chacune plusieurs réponses.

[TekMath]

Sans répondre à la question, une méthode avant d'attaque le cas général est de se donner un exemple consistant. Prenons n=10. Et faisons une disjonction des cas: on commence par p=10.

Si p=10 alors il n'est possible de faire qu'un seul QCM puisque toutes les questions auront été utilisées. Si p=9, 25% de 9 vaut 2.25 donc il faut se différencier par 3 questions ce qui est impossible là encore. Ainsi:

Si p=9 ou 10 on ne fait qu'un seul QCM.

Si p=8 les 25% correspondent à 2 questions. Numérotons les questions de 1 à 10. Les questionnaire ne prenant pas respectivement les questions (1,2) et (3,4) vérifient la question, il se différencie sur 25%, déjà 2 QCM sont possibles. On peut continuer en retirant les couples (5,6) (7,8) et (9,10). Cela donne 5 QCM qui se différencient comme convenu. Si je cherche à poser un autre QCM je n'aurais pas la possibilité de faire cette distinction. Par exemple, prenons le QCM:
(1,2,3,5,6,7,9,10) qui élimine le couple (4,8) il se trouve que si je le compare à:
(1,2,5,6,7,8,9,10) ils se différencie uniquement sur le 3.

Ma conjecture est que si p=8 il y a 5 QCM possibles.

Si p=7 les 25% correspondent à 1.75 donc 2 questions là encore mais avec 3 que l'on retire par QCM. J'ai essayé les combinaisons suivantes:
(1,2,3) (2,3,4) (3,4,5) (4,5,6) (5,6,7) (6,7,8) (7,8,9) (8,9,10)
ou chaque combinaison (i,j,k) signifie que je prend les 10 questions auxquelles je retire les numéros i,j,k. Là encore mon intuition m'indique que si je pose un ensemble à 7 éléments pris sur 10 il y aura l'un des 8 précédents avec lequel il partagera plus de 75% des questions.

Ma conjecture: si p=7 il y a 8 QCM possibles.

C'est en continuant ce genre d'exemples et en analysant la démarche et les résultats trouvés qu'on peut commencer à étudier le cas général.

[Cliffe]

Prenez :

avec pour mon exemple :

[Cliffe]

up

Personne ne parviens à résoudre ce problème ?

[TekMath]

up

Personne ne parviens à résoudre ce problème ?

où est le dernier entier plus grand que p sachant qu'on prend la partie entière à chaque fois.

J'ai bon?

[Cliffe]

Utilise la partie entière et les sommes ...

[Cliffe]

Sa donne ça ? :

[CENTER] [/CENTER]

[TekMath]

Je ne sais pas mais effectivement la somme se comprend avec les parties entières. En fait on a C(n,p) choix pour le premier questionnaire. Pour le deuxième on commence par retirer à l'entier n 25% de p pour s'assurer qu'il n'y a pas cela en commun avec tous les autres QCM.

Le deuxième QCM est donc un choix de p éléments toujours mais sur un ensemble à (n-0.25p) éléments. Là je me demande si je n'ai pas oublié le fait qu'il existe plusieurs façon de choisir ces (n-0.25p) éléments restants.

Du coup je serai tenté de rajouter le terme C(0.25*p,p) comme facteur, d'où la somme que tu as indiqué avec le facteur:

L'objectif du raisonnement est de fonctionner étape par étape, on prend un 1er QCM et on voit ce qui reste. Mais j'ai l'impression en faisant cela de donner 25% à chaque QCM par étape qui lui devient propre et non commun avec aucun autre, alors que l'objectif est que la comparaison se fasse deux par deux.

[Cliffe]

J'avais réussi à calculer pour 3 étapes.

A partir de 4, sa donne une combinaison de combinaison.

Et 5 étapes sa devient impossible :mur: