Shortlist 2010, C6

Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Canada

Concepts : Invariants et monovariants · Principe extrémal

Solution officielle : Shortlist officielle 2010 (avec solutions), p. 34 (page 35 du PDF)

Énoncé

Given a positive integer \(k\) and other two integers \(b > w > 1\). There are two strings of pearls, a string of \(b\) black pearls and a string of \(w\) white pearls. The length of a string is the number of pearls on it.

One cuts these strings in some steps by the following rules. In each step:

(i) The strings are ordered by their lengths in a non-increasing order. If there are some strings of equal lengths, then the white ones precede the black ones. Then \(k\) first ones (if they consist of more than one pearl) are chosen; if there are less than \(k\) strings longer than \(1\), then one chooses all of them.

(ii) Next, one cuts each chosen string into two parts differing in length by at most one.

(For instance, if there are strings of \(5, 4, 4, 2\) black pearls, strings of \(8, 4, 3\) white pearls and \(k = 4\), then the strings of \(8\) white, \(5\) black, \(4\) white and \(4\) black pearls are cut into the parts \((4, 4)\), \((3, 2)\), \((2, 2)\) and \((2, 2)\), respectively.)

The process stops immediately after the step when a first isolated white pearl appears. Prove that at this stage, there will still exist a string of at least two black pearls.

Indices : les idées clés

• Trois instants : \(A_s\) (premier fil de longueur \(1\)), \(A_t\) (premier instant avec plus de \(k\) fils) et \(A_f\) (toutes les perles noires isolées) ; il suffit qu'un fil blanc de longueur \(1\) apparaisse dans \(A_{f-1}\) ou avant.
• Comparaison invariante : tant que \(i \leq \min\{s, t\}\), il y a \(2^i\) fils de chaque couleur, et les plus longs/plus courts fils noirs dominent les blancs.
• Solution 2 : par récurrence, à chaque étape il existe un fil noir de longueur \(u\) et un fil blanc de longueur \(v\) avec \(u > v \geq 1\), ou bien \(2 \leq u \leq v < 2u\) et \(k - 1\) autres fils de longueur \(> v/2\) ; on suit le plus court fil blanc.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (deux solutions et une remarque).

Solution 1

Notons \(A_i\) la situation après la \(i\)-ième étape ; ainsi \(A_0\) est la situation initiale, et \(A_{i-1} \to A_i\) est la \(i\)-ième étape. On appelle \(m\)-fil un fil de \(m\) perles ; on parle de \(m\)-fil blanc ou de \(m\)-fil noir selon sa couleur.

On poursuit le processus jusqu'à ce que chaque fil soit formé d'une seule perle. On s'intéresse à trois moments du processus : (a) la première situation \(A_s\) où apparaît le premier \(1\)-fil (noir ou blanc) ; (b) la première situation \(A_t\) où le nombre total de fils dépasse \(k\) (si ce moment n'arrive jamais, on pose \(t = \infty\)) ; et (c) la première situation \(A_f\) où toutes les perles noires sont isolées. Il suffit de prouver que, dans \(A_{f-1}\) (ou avant), un \(1\)-fil blanc apparaît.

Commençons par quelques propriétés simples de ces situations. Évidemment \(s \leq f\). De plus, tous les fils noirs de \(A_{f-1}\) deviennent des perles isolées à la \(f\)-ième étape, donc ce sont tous des \(1\)- ou des \(2\)-fils noirs.

Remarquons ensuite qu'à chaque étape \(A_i \to A_{i+1}\) avec \(i \leq t - 1\), tous les \((> 1)\)-fils sont coupés, puisqu'il n'y a pas plus de \(k\) fils en tout ; si de plus \(i < s\), il n'y avait aucun \(1\)-fil, donc tous les fils sont coupés à cette étape.

Soient maintenant \(B_i\) et \(b_i\) les longueurs du plus long et du plus court fil noir de \(A_i\), et \(W_i\) et \(w_i\) les mêmes pour les fils blancs. Montrons par récurrence sur \(i \leq \min\{s, t\}\) que (i) la situation \(A_i\) contient exactement \(2^i\) fils noirs et \(2^i\) fils blancs, (ii) \(B_i \geq W_i\), et (iii) \(b_i \geq w_i\). Le cas de base \(i = 0\) est évident. Pour l'hérédité, si \(i \leq \min\{s, t\}\), alors à la \(i\)-ième étape chaque fil est coupé, donc l'affirmation (i) découle de l'hypothèse de récurrence ; ensuite, \(B_i = \lceil B_{i-1}/2 \rceil \geq \lceil W_{i-1}/2 \rceil = W_i\) et \(b_i = \lfloor b_{i-1}/2 \rfloor \geq \lfloor w_{i-1}/2 \rfloor = w_i\), ce qui établit (ii) et (iii).

Pour les nombres \(s\), \(t\), \(f\), deux cas sont possibles.

Cas 1. Supposons \(s \leq t\) ou \(f \leq t + 1\) (et donc \(s \leq t + 1\)) ; c'est en particulier le cas si \(t = \infty\). Alors, dans \(A_{s-1}\), on a \(B_{s-1} \geq W_{s-1}\), \(b_{s-1} \geq w_{s-1} > 1\), puisque \(s - 1 \leq \min\{s, t\}\). Si \(s = f\), alors \(A_{s-1}\) ne contient ni \(1\)-fil blanc ni \((> 2)\)-fil noir. Autrement dit, \(2 = B_{s-1} \geq W_{s-1} \geq b_{s-1} \geq w_{s-1} > 1\), donc tous ces nombres valent \(2\). Cela signifie que, dans \(A_{s-1}\), tous les fils contiennent \(2\) perles, et qu'il y a \(2^{s-1}\) fils noirs et \(2^{s-1}\) fils blancs, d'où \(b = 2 \cdot 2^{s-1} = w\). Cela contredit les conditions du problème.

On a donc \(s \leq f - 1\) et ainsi \(s \leq t\). Par conséquent, à la \(s\)-ième étape, chaque fil est coupé en deux. Si un \(1\)-fil noir apparaît à cette étape, alors, comme \(w_{s-1} \leq b_{s-1}\), un \(1\)-fil blanc apparaît aussi ; donc, dans tous les cas, à la \(s\)-ième étape apparaît un \(1\)-fil blanc, alors que toutes les perles noires ne sont pas isolées, comme voulu.

Cas 2. Supposons maintenant \(t + 1 \leq s\) et \(t + 2 \leq f\). Alors, dans \(A_t\), il y a exactement \(2^t\) fils blancs et \(2^t\) fils noirs, tous de longueur \(> 1\), et \(2^{t+1} > k \geq 2^t\) (la dernière inégalité vient de ce que \(2^t\) est le nombre total de fils de \(A_{t-1}\)). À la \((t + 1)\)-ième étape, exactement \(k\) fils sont coupés, dont au plus \(2^t\) sont noirs ; le nombre de fils blancs de \(A_{t+1}\) est donc au moins \(2^t + (k - 2^t) = k\). Comme le nombre de fils blancs ne diminue pas au cours du processus, il y a au moins \(k\) fils blancs dans \(A_{f-1}\) également.

Enfin, dans \(A_{f-1}\), aucun fil noir n'a plus de \(2\) perles, et au moins un \(2\)-fil noir est coupé à la \(f\)-ième étape. Par conséquent, au plus \(k - 1\) fils blancs sont coupés à cette étape ; il existe donc un fil blanc \(\mathcal{W}\) qui n'est pas coupé à la \(f\)-ième étape. D'autre part, comme un \(2\)-fil noir est coupé, tous les \((\geq 2)\)-fils blancs doivent aussi être coupés à la \(f\)-ième étape ; donc \(\mathcal{W}\) est une perle isolée. C'est exactement ce qu'il fallait. \(\blacksquare\)

Remarque. Dans cette solution, la condition \(b \neq w\) n'a servi qu'à éviter le cas \(b = w = 2^t\). Si un nombre \(b = w\) n'est pas une puissance de \(2\), l'énoncé du problème est donc encore vrai.

Solution 2

On reprend les notations introduites dans le premier paragraphe de la solution précédente. Montrons qu'à chaque étape, il existe un \(u\)-fil noir et un \(v\)-fil blanc tels que (i) \(u > v \geq 1\), ou bien (ii) \(2 \leq u \leq v < 2u\), et il existe de plus \(k - 1\) \((> v/2)\)-fils autres que ceux considérés ci-dessus.

Remarquons d'abord que cet énoncé implique celui du problème. En effet, dans les deux cas (i) et (ii), on a \(u > 1\) ; à chaque étape, il existe donc un \((\geq 2)\)-fil noir, et pour la dernière étape c'est exactement ce qu'il faut.

Prouvons maintenant l'affirmation par récurrence sur le numéro de l'étape. Évidemment, la condition (i) est vraie pour \(A_0\) puisque \(b > w\). Supposons l'énoncé vrai pour \(A_i\) et prouvons-le pour \(A_{i+1}\). Deux cas sont possibles.

Cas 1. Supposons que \(A_i\) contienne un \(u\)-fil noir et un \(v\)-fil blanc avec \(u > v\). On peut supposer que \(v\) est la longueur du plus court fil blanc de \(A_i\) ; comme on n'est pas à l'étape finale, \(v \geq 2\). À la \((i + 1)\)-ième étape, deux sous-cas peuvent se produire.

Sous-cas 1a. Supposons ou bien qu'aucun \(u\)-fil noir ne soit coupé, ou bien qu'un \(u\)-fil noir et un \(v\)-fil blanc soient tous deux coupés. Alors \(A_{i+1}\) contient ou bien un \(u\)-fil noir et un \((\leq v)\)-fil blanc (et (i) est vraie), ou bien un \(\lceil u/2 \rceil\)-fil noir et un \(\lfloor v/2 \rfloor\)-fil blanc. Dans ce dernier cas, \(u > v\) donne \(\lceil u/2 \rceil > \lfloor v/2 \rfloor\), et (i) est de nouveau vraie.

Sous-cas 1b. Supposons maintenant qu'un \(u\)-fil noir soit coupé et qu'aucun \(v\)-fil blanc ne le soit (donc tous les fils coupés sont plus longs que \(v\)). Si \(u' = \lceil u/2 \rceil > v\), la condition (i) est vérifiée puisqu'on a un \(u'\)-fil noir et un \(v\)-fil blanc dans \(A_{i+1}\). Sinon, remarquons que l'inégalité \(u > v \geq 2\) implique \(u' \geq 2\). De plus, en plus du \(u\)-fil noir fixé, \(k - 1\) autres \((\geq v + 1)\)-fils doivent être coupés à la \((i + 1)\)-ième étape, ce qui fournit au moins \(k - 1\) \((\geq \lceil (v + 1)/2 \rceil)\)-fils, et \(\lceil (v + 1)/2 \rceil > v/2\). On peut donc poser \(v' = v\), et l'on a \(u' \leq v < u \leq 2u'\) ; la condition (ii) est donc vérifiée pour \(A_{i+1}\).

Cas 2. Supposons au contraire que \(A_i\) contienne un \(u\)-fil noir, un \(v\)-fil blanc (\(2 \leq u \leq v < 2u\)) et un ensemble \(S\) de \(k - 1\) autres fils de longueur \(> v/2\) (donc \(> 1\)). À la \((i + 1)\)-ième étape, trois sous-cas peuvent se produire.

Sous-cas 2a. Supposons qu'un \(u\)-fil noir ne soit pas coupé et qu'un \(v\)-fil blanc soit coupé. Ce dernier donne un \(\lfloor v/2 \rfloor\)-fil blanc ; on a \(v' = \lfloor v/2 \rfloor < u\), et la condition (i) est vraie.

Sous-cas 2b. Supposons ensuite qu'aucun \(v\)-fil blanc ne soit coupé (et donc aucun \(u\)-fil noir non plus, puisque \(u \leq v\)). Alors les \(k\) fils coupés ont tous une longueur \(> v\), donc chacun donne un \((> v/2)\)-fil. Ainsi, dans \(A_{i+1}\), il existe \(k \geq k - 1\) \((> v/2)\)-fils autres que les \(u\)- et \(v\)-fils considérés, et la condition (ii) est vérifiée.

Sous-cas 2c. Dans le cas restant, tous les \(u\)-fils noirs sont coupés. Cela signifie que tous les \((\geq u)\)-fils sont aussi coupés, donc notre \(v\)-fil blanc l'est. Dans \(A_{i+1}\), il existe donc un \(\lceil u/2 \rceil\)-fil noir et un \(\lfloor v/2 \rfloor\)-fil blanc. Si \(u' = \lceil u/2 \rceil > \lfloor v/2 \rfloor = v'\), la condition (i) est remplie. Sinon, \(u' \leq v' < u \leq 2u'\). Dans ce cas, montrons que \(u' \geq 2\). Si au contraire \(u' = 1\) (et donc \(u = 2\)), alors tous les \((\geq 2)\)-fils noirs et blancs doivent être coupés à la \((i + 1)\)-ième étape, et parmi eux il y a au moins un \(u\)-fil noir, un \(v\)-fil blanc et les \(k - 1\) fils de \(S\) (\(k + 1\) fils en tout). C'est impossible.

On obtient donc \(2 \leq u' \leq v' < 2u'\). Pour obtenir (ii), il reste à vérifier que \(A_{i+1}\) contient un ensemble \(S'\) de \(k - 1\) autres fils de longueur \(> v'/2\). Ce seront exactement les fils obtenus à partir des éléments de \(S\). Plus précisément, chaque \(s \in S\) a été coupé à la \((i + 1)\)-ième étape ou non. Dans le premier cas, on met dans \(S'\) le plus long des fils obtenus à partir de \(s\) ; sinon, on met \(s\) lui-même dans \(S'\). Les \(k - 1\) fils de \(S'\) ont tous une longueur \(> v/2 \geq v'\), comme voulu. \(\blacksquare\)