Théorie > Combinatoire > Invariants et (mono)variants

Variants

Lorsqu'une fonction du problème semble intéressante, il n'est pas forcé qu'il s'agisse d'un invariant ou d'un monovariant pour qu'elle soit utile. En effet, la simple connaissance de comment elle varie peut parfois permettre d'avancer dans la résolution du problème. Pour illustrer cela, nous donnons la résolution du problème suivant, provenant de la Shortlist de l'IMO 2011 (il s'agit donc d'un problème qui aurait pu être posé à l'Olympiade Internationale, celui-ci n'est pas évident). Il ne s'agit pas d'un problème où une transformation est répétée, mais la technique utilisée pour le résoudre laisse fortement penser à celles que nous avons utilisées dans les sections précédentes. Les invariants et (mono)variants peuvent donc être subtilement cachés dans des problèmes de toute sorte.

Exemple : Supposons que $1000$ étudiants sont disposés en cercle. Prouver qu'il existe un entier $k$ avec $100 \leq k \leq 300$ tel qu'il existe un groupe contigu de $2k$ étudiants dont la première moitié contient autant de filles que la deuxième moitié.

Nous introduisons les variables $a_1, \ldots, a_{1000}$ qui représentent chacune un étudiant et vaut $1$ si celui-ci est une fille et $0$ sinon. On ne le dira plus, mais les indices supérieurs à $1000$ seront considérés modulo $1000$ (autrement dit, $a_{1001} = a_1$, $a_{1002} = a_2$,...) puisque les étudiants sont placés en cercle.
Nous notons alors
$$N(n, k) = a_n + \ldots + a_{n+k-1} - a_{n+k} - \ldots - a_{n+2k-1}.$$ L'intérêt de cette fonction $N(n, k)$ est qu'elle vaut $0$ exactement lorsque le groupe contigu de $2k$ personnes commençant en $a_n$ vérifie la thèse de l'énoncé. On procède donc, comme souvent, par l'absurde, en supposant que $N(n, k)$ ne vaut jamais $0$ pour $k \in [100, 300]$.
Notre idée est que, quand on passe d'un groupe contigu de $2k$ personnes au groupe contigu de $2k$ personnes juste décalé d'une personne, le nombre de filles ne change pas beaucoup. Autrement dit, les valeurs de $N(n, k)$ et $N(n+1, k)$ doivent être proches. En fait, on voit aisément que
$$N(n+1, k) - N(n, k) = -a_n + 2a_{n+k} - a_{n+2k}.$$ Cette valeur est toujours dans l'intervalle $[-2, 2]$. Pour $k$ fixé, on connaît donc assez bien comment $N(n, k)$ varie lorsque $n$ varie. On aimerait donc analyser la suite (qui forme un cycle)
$$N(1, k), \quad N(2, k), \quad \ldots \quad N(1000, k).$$ Une remarque intéressante est que la somme de ces $1000$ nombres est nulle! En effet, chaque $a_i$ apparaît $k$ fois positivement et $k$ fois négativement dans ces termes. On a donc un cycle de $1000$ nombres dont la somme vaut $0$ et tel que $N(n+1, k) - N(n, k) \in [-2, 2]$ pour tout $n$. On fixe maintenant $k = 100$ et on en déduit, les termes ne pouvant tous être du même signe, qu'il existe un certain $n_0$ tel que
$$N(n_0, 100) = 1 \quad \text{et} \quad N(n_0+1, 100) = -1.$$ Rappelons que nous cherchons une absurdité, c'est-à-dire certainement des valeurs de $n$ et $k$ telles que $N(n, k) = 0$. Nous en sommes proches puisque nous avons trouvé $-1$ et $1$. Examinons ce que ces valeurs représentent. Au vu de la relation exhibée plus haut, elles impliquent $a_{n_0} = a_{n_0 + 200} = 1$ et $a_{n_0 + 100} = 0$. Autrement dit, la situation est la suivante :
$$1, a_{n_0+1}, \ldots, a_{n_0+99}, 0, a_{n_0+101}, \ldots, a_{n_0+199}, 1$$ avec $a_{n_0+1} + \ldots + a_{n_0+99} = a_{n_0+101} + \ldots + a_{n_0+199}$. Nous n'avons jusqu'ici utilisé que la valeur $k = 100$, mais rappelons-nous qu'elle peut aller jusque $300$.
Nous avons donné $201$ étudiants ci-dessus, et en considérant ceux-ci et le suivant, on voit que ce suivant doit être une fille pour avoir $N(n_0, 101) \neq 0$. Similairement, l'élève précédant ces $201$ étudiants doit être une fille, d'où on a
$$1, 1, a_{n_0+1}, \ldots, a_{n_0+99}, 0, a_{n_0+101}, \ldots, a_{n_0+199}, 1, 1.$$ On peut alors utiliser $k = 102$ pour trouver que les deux autres étudiants aux extrémités sont également des filles, et ainsi de suite jusque $k = 300$ ce qui nous donne finalement
$$\underbrace{1, \ldots, 1}_{200 \text{ fois}}, 1, a_{n_0+1}, \ldots, a_{n_0+99}, 0, a_{n_0+101}, \ldots, a_{n_0+199}, 1, \underbrace{1, \ldots, 1}_{200 \text{ fois}}.$$ On a donc trouvé $200$ filles consécutives, c'est-à-dire un bloc de $200$ étudiants dont la première moitié contient autant de filles que la première : c'est une absurdité et cela termine le problème.