Petite énigme

Bon, bon, bon... En fait, le cas général se traite assez bien.

Considérons une population de $2n$ élèves à répartir en deux classes de $n$.

- Si $n = 2k \geq 2$ est pair, on répartit les élèves en quatre groupes de $k$, disons $A,B,C$ et $D$ et on procède comme dans mon message précédent. Cela donne une solution en $3$ coups.

Comme ci-dessus, on ne peut y arriver en $2$ coups car un élève $X$ ne connaît à chaque fois qu'au plus $n-1$ nouveaux élèves et $2(n-1) < 2n-1$.

Donc, si le nombre d'élèves est un multiple de $4$, le nombre minimal d'années est $3$.

- Si $n = 2k+1 \geq 3$ est impair, on isole deux élèves, disons $X$ et $Y$, et on répartit les $4k$ autres en $4$ groupes de $k$, disons $A,B,C$ et $D$. Les quatre répartitions annuelles suivantes montrent que l'objectif est réalisable en au maximum 4 ans :

$\{x\}\cup A \cup B$ et $\{y\} \cup C \cup D$

$\{x\}\cup A \cup C$ et $\{y\} \cup B \cup D$

$\{x\}\cup A \cup D$ et $\{y\} \cup B \cup C$

$\{x\}\cup A \cup \{y\}$ avec $k-1$ autres élèves arbitraires dans une classe, et tout le reste dans l'autre.

Par l'absurde : supposons que l'objectif soit réalisable en $3$ ans.
On considère donc une façon d'y arriver...

Soit $C_1 =\{x_1,...,x_{2k+1} \}$ et $C_2 = \{y_1,...,y_{2k+1} \}$ les classes de la première année.

La deuxième année, les $x_i$se divisent en deux groupes, selon la classe dans laquelle chacun de trouve. Sans perte de généralité, on peut supposer que $x_1,...,x_p$ d'une part et $x_{p+1},...,x_{2k+1}$ d'autre part forment ces deux groupes. Quitte à renuméroter, ils sont respectivement rejoints par $y_{p+1},...,y_{2k+1}$ et $y_1,...,y_{p}$ afin de former les deux classes.

La troisième année doit alors voir $x_1,...,x_p$ et $y_1,...,y_p$ dans une même classe, et $x_{p+1},...,x_{2k+1}, y_{p+1},....,y_{2k+1}$ dans une même classe. La taille des classes impose que $2p \leq 2k+1$ et $2(2k+1-p) \leq 2k+1$, ce qui conduit à $2p =2k+1$. Contradiction.

Ainsi, si le nombre d'élèves est congru à $2$ modulo $4$, le nombre minimal d'années est $4$.

Pierre.