Du colmatage de fuites

L’Institut intergalactique est le temple de l’excellence, où exerce le redouté professeur Phi. Le directeur de l’institut se trouve confronté à un souci. Après une soirée studieuse, Epsilon et Alpha se dirigent vers le dortoir lorsqu’ils entendent un soupir sonore provenant d’une salle de classe : M. Lambda, l’éminent directeur de l’établissement, s’y lamente sur « tant de fourberie dans l’âme humaine » tandis qu’une version numérique de OK Campus titre sur « Les folles dépenses de M. Lambda ».

M. Lambda explique que le directoire est composé de huit professeurs auxquels il confie ses idées, ses visions et ses plans. Certaines informations ont pourtant été publiées malgré son interdiction d’en parler. La rédactrice en chef, Eldy der Agot, lui a révélé qu’elle disposait de deux informateurs parmi ces professeurs et que chacun ignorait l’existence de l’autre.

Eldy der Agot ne publie une information que si ses deux informateurs la lui ont tous deux confiée. M. Lambda veut identifier ces deux professeurs afin de les exclure du comité.

Alpha propose de confier une information différente à chacune des combinaisons de deux professeurs parmi les huit membres du directoire. Il suffirait alors d’observer laquelle des vingt-huit informations est publiée. M. Lambda juge cependant que vingt-huit informations sont trop nombreuses et souhaite en propager deux fois moins.

Epsilon estime qu’il existe plusieurs moyens de réduire le nombre d’informations à partager, mais que certaines devront nécessairement sortir. M. Lambda refuse de recourir à des infox et impose une contrainte supplémentaire : au maximum deux informations complémentaires pourront être publiées.

Epsilon appelle A 1, A 2, …, A 8 les huit membres du directoire. Avec des groupes de deux professeurs, une seule information peut être publiée, mais il faut C 8 2 = 28 informations, ou 27 si aucun renseignement n’est confié à l’un des couples. Elle envisage donc de former des groupes de trois professeurs et de confier une information précise à chacun, en cherchant à utiliser le moins de groupes possible.

Pour chaque indice i, I i désigne à la fois le groupe i et, par extension, l’information qui lui est confiée. Epsilon note : I 1 = {A 1, A 2, A 3}, I 2 = {A 2, A 3, A 4}, I 3 = {A 3, A 4, A 5}, I 4 = {A 4, A 5, A 6}, I 5 = {A 5, A 6, A 7}, I 6 = {A 6, A 7, A 8}.

Si les traîtres sont A 2 et A 3, les informations I 1 et I 2 seront publiées et permettront de les identifier. S’il s’agit de A 1 et A 2, seule I 1 sortira : une seconde étape pourra alors départager les trois membres du groupe, par exemple en confiant une information à {A 1, A 2}, une autre à {A 2, A 3} et aucune à {A 1, A 3}. Les traîtres seront ainsi identifiés en deux étapes, avec au maximum deux informations publiées.

M. Lambda remarque toutefois que, si les traîtres sont A 1 et A 8, aucune information ne sera publiée. Epsilon propose donc d’ajouter des groupes tout en respectant les contraintes fixées.