Problème 1015
Lors de la superfinale 2016 de ce concours de jeux mathématiques, il y avait autant de questions que de finalistes. Chaque question a été résolue par tous les concurrents sauf trois. Les organisateurs ont remarqué que si on prenait deux concurrents au hasard, ils n'avaient jamais, à eux deux, résolu l'ensemble des questions.- 1A. Combien y avait-il, au plus, de finalistes en 2016 ?
- 2A. Combien y avait-il, au moins, de finalistes en 2017 ?
Pour ce problème, le programme écrit prend en entrée la constante N, nombre de réponses (ou candidats), et la constante P, nombre de mauvaises réponses par question. Il recherche s'il existe une configuration qui respecte la contrainte que deux candidats ont résolu l'ensemble des questions (les questions 1A et 2A sont en fait identiques aux constantes près), et affiche le cas échéant le tableau correspondant (les lignes (resp. colonnes) sont les questions (resp. candidats) [ou l'inverse], et les cases grisées sont les mauvaises réponses).
Compte-tenu de la combinatoire (le programme contient une double récursivité entre les candidats et les questions), j'ai optimisé ce programme en remarquant qu'il y a toujours une symétrie entre les candidats et les questions, et en calculant au fur et à mesure le nombre de bonnes réponses par question, afin de ne pas avoir à reparcourir les réponses fixées (cases du tableau déjà valuées) au moment du test, pour savoir si un candidat peut répondre correctement. Par ailleurs, pour les valeurs "critiques" de N (12, 13, 14), j'ai pré-rempli à la main le début du tableau après avoir observé les patterns pour des valeurs de constantes plus petites.
Pour la question 2, le programme termine en 13 secondes pour N = 12 et 4 mauvaises réponses, en quelques heures (de mémoire) pour N = 13 (solution dessinée dessous) et en quelques jours pour N = 14 (pas de solution).
Par rapport à la solution des concepteurs, on peut ajouter qu'une borne max sur le nombre de questions (ou candidats) est 1 + P(P − 1) (avec P le nombre de mauvaises réponses par question) ; dans le meilleur des cas, ce nombre P est égal au nombre de mauvaises réponses par candidat. Ainsi, le nombre maximal de lignes (candidats) dans le tableau est (au plus) 1 (ligne arbitraire) + P (nombre de mauvaises réponses sur la ligne arbitraire) × (P − 1) (nombre de candidats restants qui répondent mal à cette question) : il s'agit de la multiplication car, au mieux, toutes les mauvaises réponses restantes se situent sur des lignes différentes. Pour 5 mauvaises réponses par questions, cela donne donc au maximum 21 questions. Bien que ce raisonnement ne prouve pas que ce maximum est atteignable, on sent intuitivement que c'est toujours le cas (je pense qu'il est possible de créer le tableau optimal par construction ; sur les premières lignes c'est très facile).
Le code est disponible ici.
La solution pour N = 13 et P = 4 est donnée ci-dessous :
Compte-tenu de la combinatoire (le programme contient une double récursivité entre les candidats et les questions), j'ai optimisé ce programme en remarquant qu'il y a toujours une symétrie entre les candidats et les questions, et en calculant au fur et à mesure le nombre de bonnes réponses par question, afin de ne pas avoir à reparcourir les réponses fixées (cases du tableau déjà valuées) au moment du test, pour savoir si un candidat peut répondre correctement. Par ailleurs, pour les valeurs "critiques" de N (12, 13, 14), j'ai pré-rempli à la main le début du tableau après avoir observé les patterns pour des valeurs de constantes plus petites.
Pour la question 2, le programme termine en 13 secondes pour N = 12 et 4 mauvaises réponses, en quelques heures (de mémoire) pour N = 13 (solution dessinée dessous) et en quelques jours pour N = 14 (pas de solution).
Par rapport à la solution des concepteurs, on peut ajouter qu'une borne max sur le nombre de questions (ou candidats) est 1 + P(P − 1) (avec P le nombre de mauvaises réponses par question) ; dans le meilleur des cas, ce nombre P est égal au nombre de mauvaises réponses par candidat. Ainsi, le nombre maximal de lignes (candidats) dans le tableau est (au plus) 1 (ligne arbitraire) + P (nombre de mauvaises réponses sur la ligne arbitraire) × (P − 1) (nombre de candidats restants qui répondent mal à cette question) : il s'agit de la multiplication car, au mieux, toutes les mauvaises réponses restantes se situent sur des lignes différentes. Pour 5 mauvaises réponses par questions, cela donne donc au maximum 21 questions. Bien que ce raisonnement ne prouve pas que ce maximum est atteignable, on sent intuitivement que c'est toujours le cas (je pense qu'il est possible de créer le tableau optimal par construction ; sur les premières lignes c'est très facile).
Le code est disponible ici.
La solution pour N = 13 et P = 4 est donnée ci-dessous :
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
- 1A. Il y a eu, en 2016, 7 finalistes, au plus.
- 2A. Il y a eu, en 2017, 14 finalistes, au moins.