1

Stage de l’Olympiade Française de Mathématiques

13 - 18 février 2017
2
Chapitre 1

Déroulement du stage

Le stage de février 2017 a accueilli 42 élèves dont 39 internes, sélectionnés d’après 1 ou 2 tests
qui ont eu lieu en novembre 2016 et janvier 2017.

La liste des 31 élèves du groupe A (seniors) était :

Paul Cahen, Aline Cahuzac, Yohann D’Anello, Joanne Dumont, Théodore Fougereux,
Héloïse Gachet, Gael Gallot, Olivier Garconnet, Linda Gutsche, Ilyes Hamdi, Rodrigue Haya
Enriquez, Cindy Hua, Tristan Humbert, Yakob Kahane, Nathan Kessler, Léonie Kittel, Alexan-
dra Kortchemski, Marc Lamberet, Arthur Léonard, Joris Leroy-Savin, Rémi Lesbats, Katia
Michielsen, Tanguy Olympie, Marie Peeters, Xavier Pigé, Martin Rakovsky, Timothée Roc-
quet, Etienne Rossignol, Baptiste Serraille, Joachim Studnia, Mathis Wetterwald.

La liste des 11 élèves du groupe B (juniors) était :

Sacha Arroues-Paykin, Justin Cahuzac, Noémie Cerrina, Daniel Cortild, Evelyne Le Bezvoët,
Charles Liu, Anna Luchnikova, Sophia Maissouradze, Etienne Massart, Dominic Olimid, Em-
ilie Zheng.

Les élèves étaient encadrés par : Pierre Bornsztein, Thomas Budzinski, Guillaume Conchon-
Kerjan, Claude Deschamps, David Gontier, Saeed Hadikhanloo, Vincent Jugé, Adrien Lemercier,
Matthieu Lequesne, Matthieu Piquerez, Jean-Louis Tu.

Une partie des documents du stage a été rassemblée ici.

3
4 CHAPITRE 1. DÉROULEMENT DU STAGE

Programme par date – stage du 13 au 18 février 2017

9h-11h puis 11h15-12h30 14h-16h puis 16h15-17h30

groupe B groupe A groupe B groupe A
arrivée entre 10h et 12h30 :
accueil par Jean-Louis au foyer
de Cachan, et David à la gare de Arithmétique Géométrie
lundi Lyon (David) (Adrien)

Géométrie Combinatoire Arithmétique

mardi (Adrien) Algèbre (Pierre) (Pierre) (Matthieu P)
Algèbre Combinatoire
mercredi (Matthieu L) (David) Test (Guillaume) Test (JL)
Arithmétique Combinatoire Géométrie
jeudi (Saeed) (Claude) Algèbre (JL) (Saeed)

Géométrie Combinatoire Arithmétique

vendredi (Saeed) Algèbre (Claude) (Thomas) (Vincent)
Exercices divers (9h-12h) :
Guillaume déjeuner à 12h, départs avant
samedi Présent pour la sortie : Vincent 14h.

Horaires des repas : petit déjeuner 8h-8h30, déjeuner 12h30-13h, dîner

18h45-19h15. Exception : le déjeuner du samedi a lieu à 12h.
Chapitre 2

Cours du groupe A (seniors)

2.1 Algèbre groupe A (Pierre)

Exercice 1. Soit x1 , ..., x100 des réels positifs ou nuls tels que

xi + xi+1 + xi+2 ≤ 1

pour i = 1, 2, ..., 100 (avec x101 = x1 et x102 = x2 ).

Déterminer la valeur maximale de

100
X
S= xi xi+2 .
i=1

Solution. La contrainte fait intervenir trois termes consécutifs, donc on va s’intéresser à

deux termes consécutifs de la somme S, disons xi xi+2 + xi+1 xi+3 .
D’après la contrainte, on a xi + xi+1 + xi+2 ≤ 1 et xi+1 + xi+2 + xi+3 ≤ 1. Gardons les termes
communs. On écrit alors que xi ≤ 1 − xi+1 − xi+2 et que xi+3 ≤ 1 − xi+1 − xi+2 , et ainsi
xi xi+2 + xi+1 xi+3 = xi+2 (1 − xi+1 − xi+2 ) + xi+1 (1 − xi+1 − xi+2 )
= (xi+2 + xi+1 )(1 − xi+1 − xi+2 )
= 14 − (xi+2 + xi+1 − 12 )2
≤ 14 avec égalité si et seulement si xi+2 + xi+1 = 12 , ainsi que xi ≤ 12 et
xi+3 ≤ 12 .
On groupe ainsi les termes de S par paquets de deux termes consécutifs, et il vient S ≤
100
2
× 14 .
Mais, d’après ci-dessus, il est facile de vérifier que l’égalité est obtenue pour x2i = 0 et
x2i+1 = 12 .
Le maximum cherché est donc 25 2
.

Exercice 2. Soit f :]0, 1[−→]0, 1[ définie par

f (x) = x + 12 si x < 1

f (x) = 2
f (x) = x2 si x ≥ 12

5
6 CHAPITRE 2. COURS DU GROUPE A (SENIORS)

Soit a et b deux réels tels que 0 < a < b < 1. On pose alors a0 = a, b0 = b et an =
f (an−1 ), bn = f (bn−1 ) pour tout entier n > 0.
Prouver qu’il existe un entier n > 0 tel que

(an − an−1 )(bn − bn−1 ) < 0.

Solution. Soit x ∈]0, 1[.

Si x < 12 , on a f (x) − x = 21 > 0.
Si x ≥ 21 , on a f (x) − x = x2 − x < 0.
Par suite, on a (an − an−1 )(bn − bn−1 ) = (f (an−1 ) − an−1 )(f (bn−1 ) − bn−1 ) < 0 si et seulement
si an−1 et bn−1 sont l’un dans I1 =]0; 12 [ et l’autre dans I2 = [ 21 , 1[.

Par l’absurde : Supposons que, pour tout entier k ≥ 0, les nombres ak et bk soient toujours
dans un même de ces deux intervalles.

Pour tout k ≥ 0, on pose dk = |ak − bk |. On doit donc avoir dk < 21 . (1)

Or, si ak , bk ∈ I1 , on a clairement dk+1 = dk .
Et, si ak , bk ∈ I2 , on a :

1 1
min(ak , bk ) ≥ 2
et max(ak , bk ) = min(ak , bk ) + dk ≥ 2
+ dk .

Par suite

dk+1 = |ak+1 − bk+1 |

= |(ak − bk )(ak + bk )|
≥ |ak − bk |( 21 + 21 + dk )
= dk (1 + dk )

En particulier, la suite (dk ) est croissante, et on a donc dk ≥ d0 > 0 pour tout k ≥ 0.

En fait, plus précisément :
Si ak , bk ∈ I2 alors

dk+2 ≥ dk+1 ≥ dk (1 + dk ) ≥ dk (1 + d0 ).

Et, si ak , bk ∈ I1 alors ak+1 , bk+1 ∈ I2 et on a

dk+2 ≥ dk+1 (1 + dk+1 ) ≥ dk (1 + d0 ).

Ainsi, on a dk+2 ≥ dk (1 + d0 ) pour tout k ≥ 0.

Une récurrence immédiate conduit à d2m ≥ d0 (1 + d0 )m pour tout m ≥ 0.
Or, comme 1 + d0 > 1, on a lim d2m = +∞, en contradiction avec (1).
m→+∞

Exercice 3. Soit a1 , a2 , a3 , ... une suite infinie de réels strictement positifs tels que

kak
ak+1 ≥ , pour tout k ≥ 1.
a2k +k−1
2.1. ALGÈBRE GROUPE A (PIERRE) 7

Prouver que a1 + a2 + · · · + an ≥ n, pour tout n ≥ 2.

Solution. Pour tout k ≥ 1, la contrainte se réécrit

k a2k + k − 1 k−1 k k−1

≤ = ak + et ainsi ak ≥ − .
ak+1 ak ak ak+1 ak

Pour n ≥ 2, en sommant membre à membre ces différentes inégalités pour k = 1, 2, ..., n,

et après simplification par dominos, il vient
n
a1 + a2 + ... + an ≥ . (*)
an+1

On prouve alors le résultat demandé par récurrence sur n ≥ 2 :

1
- Pour n = 2, d’après la contrainte pour k = 1, on a a1 + a2 ≥ a1 + ≥ 2.
a1
- Supposons maintenant que l’inégalité cherchée soit établie pour n ≥ 2.
Si an+1 ≥ 1 alors (a1 + a2 + ... + an ) + an+1 ≥ n + 1, d’après l’hypothèse de récurrence.
Si an+1 < 1 alors, d’après (*), on a
n n−1 1
(a1 + a2 + ... + an ) + an+1 ≥ + an+1 = +( + an+1 ) > n − 1 + 2, d’où la con-
an+1 an+1 an+1
clusion.
Remarque. L’initialisation et l’hérédité ci-dessus montrent qu’il n’y a égalité que lorsque
ai = 1 pour tout i.

Exercice 4. Soit n ≥ 1 un entier, et a1 , a2 , ..., an , b1 , b2 , ..., bn des réels distincts. Dans un

tableau n × n, dans la case située sur la ligne i et la colonne j, on écrit le nombre ai + bj .
Il se trouve que, pour chaque ligne, le produit des nombres inscrits dans cette ligne est le
même.
Prouver que, pour chaque colonne, le produit des nombres inscrits dans cette ligne est le
même.

Solution. L’énoncé nous dit qu’il existe un réel c tel qu’on ait

(ai + b1 )(ai + b2 ) · · · (ai + bn ) = c, pour tout i.

Soit donc P (x) = (x + b1 )(x + b2 ) · · · (x + bn ).

On définit ainsi un polynôme P de degré n dont les racines sont manifestement tous les
−bj , et tel que P (ai ) = c pour tout i.
Mais alors, le polynôme Q(x) = P (x) − c admet chacun des ai comme racine et s’écrit donc
Q(x) = (x − a1 )(x − a2 ) · · · (x − an ).
Par suite, pour tout j, on a Q(−bj ) = P (−bj ) − c = −c,
et donc (a1 + bj )(a2 + bj ) · · · (an + bj ) = (−1)n+1 c, d’où la conclusion.

Exercice 5. Soit n ≥ 3 un entier. Soit f et g deux polynômes à coefficients réels tels que les
points du plan de coordonnées respectives (f (1), g(1)), (f (2), g(2)), · · · , (f (n), g(n)) soient les
sommets d’un polygone régulier convexe dans le sens antihoraire.
Prouver que l’un des polynômes f et g est de degré supérieur ou égal à n − 1.
8 CHAPITRE 2. COURS DU GROUPE A (SENIORS)

Solution. Quitte à ajouter des constantes à f et g, on peut supposer que le n-gone est centré
iπ
sur l’origine. On pose h(x) = f (x) + ig(x) et ζ = e n . Alors h(m + 1) = ζh(m), pour m =
1, 2, · · · , n − 1.
On en déduit que le polynôme P (X) = h(X + 1) − ζh(X) admet au moins n − 1 racines
distinctes. De plus, si h est de degré d et de coefficient dominant ad , le degré de P est au plus
celui de h et le coefficient de X d dans P est ad (1 − ζ) 6= 0, donc P est de degré d. En particulier,
P n’est pas le polynôme nul, et on a d ≥ n − 1.
Or :

max(deg f, deg g) = deg h = deg P = d ≥ n − 1,

ce qui conclut.

Exercice 6. a) Soit A, B et C trois polynômes deux à deux premiers entre eux, tels que
A + B = C. Prouver que le degré de chacun d’entre eux est inférieur au nombre de racines
distinctes de ABC.
b) Soit a, b, c des entiers strictement positifs, et P, Q, R des polynômes à coefficients com-
plexes, deux à deux premiers entre eux et non constants tels que

P a + Qb = Rc .
1 1 1
Prouver que + + > 1.
a b c
Solution. a) On pose
k
Y l
Y m
Y
ai bi
A(X) = (x − pi ) , B(X) = (x − qi ) , C(X) = (x − ri )ci .
i=1 i=1 i=1

A(x) B(x)
Puisque A + B = C, on a + = 1, pour tout x distinct des ri . Après dérivation, il
C(x) C(x)
vient :
k m l m
A(x) X ai X ci B(x) X bi X ci
( − )=− ( − ).
C(x) i=1 x − pi i=1
x − ri C(x) i=1 x − qi i=1
x − ri
A(x)
On en déduit que B(x) peut s’écrire comme le quotient de deux polynômes de degrés ne
dépassant pas k + l + m − 1. En particulier, puisque A et B sont premiers entre eux, on
deg A ≤ k + l + m − 1.
On obtient des résultats analoques pour B et C, ce qui conclut.
b) On utilise le lemme pour A = P a , B = Qb et C = Rc . Ainsi a deg P < deg P + deg Q +
1 deg P
deg R, d’où > .
a deg P + deg Q + deg R
De même

1 deg Q 1 deg R
> et >
b deg P + deg Q + deg R c deg P + deg Q + deg R
2.1. ALGÈBRE GROUPE A (PIERRE) 9

1 1 1
et finalement + + > 1.
a b c
Exercice 7. Soit k ≥ 2 un entier. On considère une partition de N en k suites arithmétiques
infinies (ai + ndi )n≥0 pour i = 1, 2, · · · , k.
Prouver que

1 1 1 a1 a2 ak k−1
+ + ··· + = 1 et + + ··· + = .
d1 d2 dk d1 d2 dk 2

Solution. Approche combinatoire. On suppose que N est la réunion disjointe des ai + di N

lorsque i décrit {1, ..., k}.
On note m un multiple commun des di . Ainsi, pour tout i fixé, on a m = ri di et N est la
réunion disjointe des j + ri N lorsque j décrit {0, 1, ..., ri − 1}. On en déduit que ai + di N est la
réunion disjointe des ai + di (j + ri N) = (ai + jdi ) + mN.
Par conséquent, N est la réunion disjointe des (ai + jdi ) + mN lorsque i décrit {1, ..., k} et
j dé crit {0, 1, ..., ri − 1}. Or, toutes ces suites arithmétiques ont la m ême raison m, ce qui
implique que les ai + jdi décrivent exactement {0, 1, ..., m − 1}.
k i −1
rX k
X m(m − 1) X
On en déduit que (ai + jdi ) = et que ri = m (puisque, pour chaque
i=1 j=0=1
2 i=1
i, il y a ri valeurs pour ai + jdi ,).
La première égalité donne
k k
m(m − 1) X ri (ri − 1) X ai m m(ri − 1)
= (ai ri + di ) = ( + ).
2 i=1
2 i=1
di 2
k k
X ai m − 1 X ri − 1 k−1
Compte-tenu de la seconde égalité, on a alors = − = , comme
i=1
di 2 i=1
2 2
désiré.

Approche algébrique. On note que, compte-tenu de la partition de N, pour tout x ∈ [0, 1[, on
a
+∞ k +∞ X xai k
1 X
n
XX
ai +ndi
= x = x =
1 − x n=0 i=1 n=0 i=1
1 − xdi
k k
X xai (1 − x) X xai
et donc 1 = = . (1)
i=1
1 − xdi i=1
1 + x + ... + xdi −1

k
X 1
En faisant tendre x vers 1, il vient = 1. (2)
d
i=1 i
Puis, après dérivation de (1), on obtient que
k
X ai xai−1 (1 + x + ... + xdi −1 ) − xai (1 + 2x + ... + (di − 1)xdi −2 )
=0
i=1
(1 + x + ... + xdi −1 )2
10 CHAPITRE 2. COURS DU GROUPE A (SENIORS)

pour tout x ∈ [0, 1[.

On fait à nouveau tendre x vers 1 dans cette égalité. Alors :

k di (di −1) k k
X ai d i − 2
X ai X 1 1
0= = − ( − ).
i=1
d2i i=1
di i=1
2 2d i

k k
X ai X 1 1 k−1
D’après (2), on en déduit que = ( − )= .
i=1
di i=1
2 2di 2

Exercice 8. Soit P un polynôme à coefficients réels, de degré n ≥ 1.

a) Prouver que P ne peut s’écrire comme la somme d’au plus n fonctions périodiques.
b) Prouver que P peut s’écrire comme la somme de n + 1 fonctions périodiques.

Solution. a) On va raisonner par récurrence sur n ≥ 1.

Clairement, un polynôme de degré 1 n’est pas une fonction périodique donc la conclusion
est établie pour n = 1.
Supposons que l’affirmation soit vraie pour un certain n ≥ 1 fixé. Soit alors P un polynôme
à coefficients réels, de degré n + 1.
n+1
X
Par l’absurde : supposons que P = fi où, pour tout i ∈ {1, ..., n + 1}, la fonction fi
i=1
est périodique de période hi > 0 (certaines fonctions fi peuvent être identiquement nulles
puisqu’on ne demande qu’au plus n + 1 fonctions périodiques).
Soit alors Q(X) = P (X + hn+1 ) − P (X).
Il est facile de vérifier que Q est un polynôme à coefficients réels de degré n, que pour tout
réel x, on a
n+1
X n
X
Q(x) = [fi (x + hn+1 ) − f (x)] = [fi (x + hn+1 ) − f (x)]
i=1 i=1

et que, pour tout i ∈ {1, ..., n}, la fonction gi : x 7−→ fi (x + hn+1 ) − f (x) est périodique de
période hi . Ainsi, Q peut s’écrire comme la somme de n fonctions périodiques, en contradic-
tion avec l’hypothèse de récurrence.
Finalement, P ne peut s’écrire comme la somme d’au plus n fonctions périodiques, ce qui
prouve l’affirmation est vraie pour n + 1, et achève la démonstration.

b) On commence par noter que pour tout entier k ≥ 1 et tous réels a1 , ..., ak+1 , lorsque l’on
développe (a1 + a2 + ... + ak+1 )k , aucun terme obtenu ne contient tous les ai . Ainsi, on peut
les répartir en k + 1 paquets deux à deux sans terme commun : le premier paquet formé de
tous les termes qui ne contiennent pas a1 (soit donc (a2 + ... + ak+1 )k ), le second paquet formé
de tous les termes non encore pris et qui ne contiennent pas a2 , le troisième paquet formé de
tous les termes non encore pris et qui ne contiennent pas a3 , et ainsi de suite...
Considérons maintenant une base B = {ei /i ∈ I} de R en tant que Q-espace vectoriel (une
telle base est appelée Base de Hamel, et son existence nécessite l’axiome du choix). Quitte à
changer ei en −ei , on peut toujours supposer que ei > 0 pour tout i ∈ I.
2.1. ALGÈBRE GROUPE A (PIERRE) 11

Ainsi, tout réel x s’écrit de façon

Xunique comme combinaison linéaire finie à coefficients
rationnels des éléments de B : x = xi ei .
i∈I
De plus, puisqu’une réunion dénombrable d’ensembles dénombrables est dénombrable et
que R n’est pas dénombrable, B est alors une famille non dénombrable et, en particulier, on
peut considérer une sous-famille {ei /i ∈ N∗ } de B.
Soit k ≥ 1 un entier. Pour tout réel x, avec les notations ci-dessus et en choisissant ai = xi ei
X k
X
pour i ≤ k, et ak+1 = xi ei − xi ei , on note fi (x) la somme des termes du paquet numéro
i∈I i=1
k+1
X
k
i. Il est alors clair que P (X) = X s’écrit P = fi où, pour tout i ∈ {1, ..., k + 1}, la fonction
i=1
fi est périodique de période ei puisque la coordonnée xi n’apparaît pas dans fi (x).
Or, si f et g sont T -périodiques il en est de même de h = af + bg + c pour tous réels a, b, c.
Xn
Par suite, pour tout entier n ≥ 1, si P (X) = αi X i alors, en utilisant le résultat pour chaque
i=0
monôme et puisque les périodes utilisées pour chacun ne sont que parmi e1 , ..., en+1 , on en
déduit que P peut s’écrire comme la somme de n + 1 fonctions périodiques, ce qui conclut.
12 CHAPITRE 2. COURS DU GROUPE A (SENIORS)
Chapitre 3

Cours du groupe B (juniors)

3.1 Combinatoire groupe B (Pierre)

Exercice 1 (Erdös-Szekeres-Klein). Soit A, B, C, D, E des points du plan, trois jamais alignés.
Prouver que quatre d’entre eux sont les sommets d’un quadrilatère convexe.

Solution. Si l’enveloppe convexe des cinq points est un quadrilatère ou un pentagone, c’est
déjà gagné. D’autre part, puisque les points ne sont pas alignés, cette enveloppe convexe ne
peut être un segment. Il reste donc à étudier le cas où l’enveloppe convexe est un triangle,
disons ABC, avec les points D et E à l’intérieur. La droite (DE), qui ne peut passer par un
des sommets (sinon on aurait trois points alignés), rencontre alors deux des côtés du triangle,
disons ]AB[ et ]AC[. Mais alors, les points B, C, D, E sont, dans un ordre bien choisi, les
sommets d’un quadrilatère convexe.

Remarque. Erdös et Szekeres ont montré que, pour tout entier n ≥ 3, il existe un entier
k tel que tout ensemble d’au moins k points du plan en contienne n qui sont les sommets
d’un n-gone convexe. Si on note f (n) le plus petit entier k ayant cette propriété, on sait que
f (n) = 2n−2 + 1 pour n = 3, 4, 5, 6.
On conjecture que cette égalité est vraie pour tout n ≥ 3.

Exercice 2. Soit n ≥ 4 un entier et A1 , ..., An des points du plan, trois jamais alignés, tels que
quatre quelconques d’entre eux sont toujours les sommets d’un quadrilatère convexe. Alors,
les points A1 , ..., An sont, dans un certain ordre, les sommets d’un n-gone convexe.

Solution. Soit C l’enveloppe convexe des n points. Par l’absurde : supposons que C ne soit
pas un n-gone. Sans perte de généralité, on peut alors supposer que A1 est un sommet de C
et que An n’en est pas un. Alors, An est à l’intérieur de C (il ne peut être sur le bord sinon
il y aurait trois des Ai qui seraient alignés). On effectue une triangulation de C à partir des
diagonales issues de A1 et, quitte à renuméroter, on peut supposer que An soit à l’intérieur
(comme ci-dessus) du triangle A1 A2 A3 . Mais alors, les points A1 , A2 , A3 , An ne sont pas les
sommets d’un quadrilatère convexe, en contradiction avec l’énoncé. D’où le résultat.

Exercice 3. Soit P un polygone convexe à n sommets du plan. On triangule P à l’aide

de certaines de ses diagonales. On colorie en rouge les triangles qui ont deux côtés qui sont

13
14 CHAPITRE 3. COURS DU GROUPE B (JUNIORS)

également des côtés de P, en vert ceux qui ont un seul côté commun avec P, et en bleu ceux
qui n’ont aucun côté commun avec P.
Prouver que, quelle que soit la triangulation choisie, il y aura toujours exactement deux
triangles rouges de plus que de triangles bleus.
Solution. Si la triangulation fait intervenir k triangles, la somme des angles intérieurs de
ces triangles est égale à kπ, et elle est aussi égale à la somme des angles intérieurs de P, c.à.d.
(n − 2)π. Donc k = n − 2.
Ainsi, toute triangulation fait intervenir n − 2 triangles.
Soit b, r, v les nombres de triangles bleus, rouges et verts, respectivement.
On a donc b + r + v = n − 2.
Mais tout côté de P appartient soit à un triangle rouge soit à un triangle vert. Et récipro-
quement, tout triangle rouge utilise deux côtés de P alors que tout triangle vert en utilise un
seul. Par suite, on a 2r + v = n.
Et donc r + (n − 2 − b) = n, c.à.d. r = b + 2.
Exercice 4. On donne 4000 points dans le plan, trois quelconques jamais alignés. Démon-
trer que l’on peut construire 1000 quadrilatères deux à deux disjoints, non nécessairement
convexes, et dont les sommets sont les points données.
Solution. Il n’y a qu’un nombre fini de points donc on peut considérer un repère orthog-
onal dans lequel les 4000 points ont des abscisses deux à deux distinctes. On les numérote
alors P1 , ..., P4000 par abscisses croissantes. Pour tout 1 ≤ i ≤ 1000, on regroupe alors les
quatre points P4i−3 , P4i−2 , P4i−1 , P4i . Ces quatres points ne sont pas alignés donc ils sont les
sommets d’un quadrilatère, pas forcément convexe, et notre numérotation assure que deux
quelconques des quadrilatères ainsi construits ne s’intersectent pas.
Exercice 5. On donne n > 0 points dans le plan de sorte qu’un triangle formé par trois quel-
conques d’entre eux soit toujours d’aire ne dépassant pas 1. Prouver que l’on peut recouvrir
ces n points par un triangle d’aire 4.
Solution. Si n ≤ 3 ou si tous les points sont alignés, il n’y a rien à faire. On suppose donc
que n > 3 et que les points considérés ne sont pas tous alignés.
Soit alors A, B, C trois des points, non alignés, tels que le triangle ABC soit d’aire maxi-
male (et donc cette aire ne dépasse pas 1). On note ∆A la droite parallèle à (BC) passant par
A, et on définit de même les droites ∆B et ∆C . Les droites ∆A et ∆B se rencontrent en C 0 , et
on définit de même les points A0 et B 0 . La maximalité de ABC assure alors que tous les points
sont à l’intérieur ou sur les bords du triangle A0 B 0 C 0 . Et, par construction, les points A, B, C
sont les milieux des côtés de A0 B 0 C 0 , ce qui prouve que A0 B 0 C 0 est d’aire ne dépassant pas 4.
Si l’on veut chipoter un peu, on peut ensuite effectuer une homothétie de centre A0 de rapport
adéquat pour obtenir un triangle recouvrant et d’aire exactement 4.
Exercice 6. Soit P un polygone convexe à n sommets dans le plan. Prouver qu’il existe au
plus n(2n−5)
3
triangles d’aire 1 dont les sommets sont des sommets de P.
Solution. Si A et B sont deux points fixés, les points M du plan tels que le triangle ABM
ait pour aire 1 sont les points de deux droites parallèles à (AB), et situées de part et d’autre
2
de (AB) à une distance h = AB .
3.1. COMBINATOIRE GROUPE B (PIERRE) 15

Par suite, si, parmi les sommets de P, il y a plus de quatre tels points M , alors le principe
des tiroirs assure qu’au moins trois de ces points appartiennent à une même de ces deux
droites, et sont donc alignés, ce qui est impossible puisqu’un polygone convexe ne contient
jamais trois points alignés.
Par suite, pour A et B fixés, il n’existe qu’au plus 4 autres sommets tels que ABM soit
d’aire 1, au plus deux de chaque côté de (AB).
Considérons maintenant deux sommets A et B de P qui forment la base d’un éventuel
triangle d’aire 1. Comme il y a trois choix possible pour la base d’un triangle, chaque triangle
que l’on va mettre en évidence sera donc compté trois fois.
- Si A et B sont consécutifs : Tous les autres sommets sont situés d’un même côté de (AB).
D’après ci-dessus, A et B ne déterminent ainsi qu’au plus deux triangles d’aire 1.
Il y a n choix de deux sommets consécutifs (autant que de côtés), ce qui nous donne au
plus 2n triangles d’aire 1 dans ce cas.
- Si A et B sont séparés par un seul sommet C de P : ce sommet C peut éventuellement
former, avec A et B, un triangle d’aire 1. D’autre part, comme ci-dessus, il y a au plus deux
autres sommets qui forment avec A et B des triangles d’aire 1. Cela fournit ainsi en tout au
plus trois triangles d’aire 1.
Or, il y a exactement n choix de deux sommets séparés par un seul sommet (autant que de
choix du sommet intermédiaire). On a donc au plus 3n triangles dans ce cas.
- Si A et B sont séparés par au moins deux sommets de P : cette fois, il y a au plus quatre
triangles d’aire 1 dont A et B sont des sommets (deux choix pour le troisième sommet, de part
et d’autre de (AB)).
Or, il y a n(n−1)
2
− 2n choix de tels paires (tous les choix sauf ceux déjà considérés dans les
cas précédents), et donc au plus 2n(n − 1) − 8n = 2n2 − 10n triangles d’aire 1 dans ce cas.
Finalement, au total, cela fournit au plus (2n2 − 10n) + 2n + 3n = n(2n − 5) triangles
d’aire 1. D’après la remarque initiale, chacun des triangles d’aire 1 est compté trois fois dans
le raisonnement ci-dessus. Il y a donc au plus n(2n−5)
3
triangles d’aire 1 dont les sommets sont
des sommets de P.

Exercice 7. Dans le plan, on considère un polygone convexe à 2000 sommets. Prouver qu’il
est possible de choisir 1998 points du plan de sorte que tout triangle dont les trois sommets
sont des sommets du polygone contienne exactement un des points choisis en son intérieur.

Solution. On remplace tout de suite 2000 et 1998 par n et n − 2.

Puisqu’il n’y a qu’un nombre fini de sommets, on peut considérer un repère orthonormal
du plan dans lequel les n points ont des abscisses deux à deux distinctes, et on les numérote
P1 , P2 , ..., Pn dans l’ordre des abscisses croissantes, avec Pi (xi , yi ) pour tout i. Pour tous i, j, k
distincts, on note d(Pk , (Pi Pj )) la distance de Pk à la droite (Pi Pj ). Comme il n’y a qu’un
nombre fini de points et que trois ne sont jamais alignés, il n’y a qu’un nombre fini de telles
distances, et elles sont toutes strictement positives. On peut alors noter d la plus petite de ces
distances, et on a d > 0.
Pour tout i ∈ {2, ..., n − 1}, comme les Pj sont les sommets d’un polygone convexe, ex-
actement un des deux points de coordonnées (xi , yi ± d2 ) est à l’intérieur du polygone et on le
16 CHAPITRE 3. COURS DU GROUPE B (JUNIORS)

note Mi (pour i ∈ {1, n}, notre choix de repère entraine que, dans chaque cas, les deux points
correspondants sont à l’extérieur du polygone). On marque alors les n − 2 points Mi ainsi
définis.
Pour tout i ∈ {2, ..., n − 1}, et pour tous a, b, c ∈ {1, ..., n}\{i}, le point Pi est à l’extérieur du
triangle Pa Pb Pc donc, si Mi était à l’intérieur de Pa Pb Pc l’un des côtés du triangle traverserait
le segment [Pi Mi ], en contradiction avec Pi Mi = d2 qui est strictement inférieure à la distance
de Pi aux droites supports des côtés de Pa Pb Pc . Ainsi, Mi est à l’extérieur du triangle Pa Pb Pc .
D’autre part, notre numérotation assure que Mi est intérieur à Pi Pj Pk si et seulement si j <
i < k ou k < i < j.
Finalement, chacun des triangles Pa Pb Pc possède un et un seul des points marqués en son
intérieur et, si 1 ≤ a < b < c ≤ n, ce point est Mb .

Exercice 8. Soit n ≥ 1 un entier. On dit qu’un ensemble S de points du plan est bien réparti
si, pour tout k ∈ {1, ..., n}, il existe une droite qui contienne exactement k points de S.
Déterminer le nombre minimal f (n) de points que contienne un ensemble bien réparti.

Solution. Considérons un ensemble bien réparti S (s’il en existe). Alors, pour tout k ∈
{1, ..., n}, il existe une droite ∆k qui contient exactement k points de S. Evidemment, si k 6=
k 0 , les droites ∆k et ∆k0 ne peuvent être confondues, et ont donc au plus un point de S en
commun. Par suite, sur ∆n il y a n points de S, sur ∆n−1 il y a au moins n − 2 points de S
non déjà considérés avec ∆n , sur ∆n−2 il y a au moins n − 4 points de S non déjà considérés
avec ∆n ou ∆n−1 , et ainsi de suite... pour tout k, sur ∆n−k il y a au moins n − 2k points de
S non déjà considérés avec les droites ∆i où i > n − k. Cela assure que S contient au moins
n + (n − 2) + (n − 4) + ... + ε, où ε = 0 si n est pair et ε = 1 sinon. Plus précisément, si n = 2p
est pair, l’ensemble S contient au moins
p p p
X X X
(2p − 2k) = 2 (p − k) = 2 i = p(p + 1)
k=0 k=0 i=0

points, et cela nous dit que f (2p) ≥ p(p + 1).

Si n = 2p + 1 est impair, l’ensemble S contient au moins
p p
X X
(2p + 1 − 2k) = p + 1 + 2 (p − k) = (p + 1)2
k=0 k=0

points, et cela nous dit que f (2p + 1) ≥ (p + 1)2 .

On pose alors g(2p) = p(p + 1) et g(2p + 1) = (p + 1)2 pour tout p ≥ 0.
Il nous reste à prouver que nos estimations sont optimales, c.à.d. que f (n) = g(n), en
construisant des ensembles bien répartis adéquats. Pour cela, on raisonne par récurrence sur
n.
On a trivialement que f (1) = 1. Supposons que pour un certain entier n ≥ 1, on dispose
d’un ensemble S bien équilibré de g(n) points. On note toujours ∆k une droite qui contient
exactement k points de S. Comme il n’y a qu’un nombre fini de points dans S et de droites
∆k , on peut choisir une droite ∆ qui ne passe par aucun point de S et n’est parallèle avec
aucune des droites ∆k . Ainsi, pour tout k, la droite ∆ rencontre ∆k en un point Ak qui n’est
3.1. COMBINATOIRE GROUPE B (PIERRE) 17

pas dans S et, quitte à translater ∆, on peut toujours supposer que les points Ak sont deux à
deux distincts. Deux cas se présentent alors :
- Si n = 2p est pair, on considère l’ensemble S 0 réunion des éléments de S et des points
Ak pour k ∈ {p + 1, ..., 2p}. Dans ces conditions, si k ≤ p alors ∆k rencontre encore S 0 en
exactement k points. Si k ≥ p + 1 alors ∆k rencontre maintenant S 0 en exactement k + 1 points.
La droite ∆ quant à elle, rencontre S 0 en exactement p points. Pour obtenir un ensemble bien
réparti pour la valeur n + 1, il suffit alors d’ajouter à S 0 un point quelconque de ∆ qui ne soit
sur aucune des droites ∆k ni déjà dans S 0 . On note que cela nous fournit un ensemble bien
équilibré de g(2p) + p + 1 = (p + 1)2 = g(2p + 1).
- Si n = 2p + 1 est impair, on montre de même qu’en ajoutant à S les points Ak pour
k ∈ {p + 1, ..., 2p + 1}, on obtient directement un ensemble bien réparti S 0 pour la valeur n + 1
et qui contient g(2p + 1) + p + 1 = (p + 1)(p + 2) = g(2p + 2) points.
Ainsi, pour tout n ≥ 1, il existe un ensemble bien équilibré pour la valeur n et qui contient
exactement g(n) points. Cela prouve que f (n) ≤ g(n) pour tout n ≥ 1 et donc que, compte-
tenu de l’inégalité prouvée ci-dessus, on a f (n) = g(n) pour tout n ≥ 1.
Finalement, pour tout p ≥ 0, on a f (2p) = p(p + 1) et f (2p + 1) = (p + 1)2 .

Exercice 9. Soit n ≥ 4 un entier et S = {P1 , ..., Pn } un ensemble de points du plan, trois

jamais alignés et quatre jamais cocycliques. Pour t ∈ {1, ..., n}, on note at le nombre de cercles
circonscrits à un triangle de la forme Pi Pj Pk qui contiennent Pt en son intérieur. On pose
m(S) = a1 + ... + an .
Prouver qu’il existe un entier strictement positif f (n), qui ne dépende que de n, tel que
m(S) ≤ f (n) avec égalité si et seulement si les points de S sont les sommets d’un n-gone
convexe.
n


Solution. On va prouver que f (n) = 2 4
.
Soit A, B, C, D quatre des points de S. On pose nA = 1 si A est à l’intérieur ou sur le bord
du cercle circonscrit à BCD, et nA = 0 sinon. Les nombres nB , nC , nD sont définis de manière
analogue. Puisque ces points ne sont pas alignés, l’enveloppe convexe de l’ensemble qui les
contient est soit un triangle soit un quadrilatère.
Si c’est un triangle, sans perte de généralité, on peut supposer que D est à l’intérieur du
triangle ABC. Dans ces conditions, parmi les cercles qui passent par trois des points, seul le
cercle circonscrit à ABC contient le quatrième des points. Ainsi, on a nA = nB = nC = 0 et
nD = 1.
Si c’est un quadrilatère, disons ABCD, on pose α = DAB,
\ β = ABC, [ γ = BCD, \ δ = CDA\
et on a α + β + γ + δ = 2π. Or, puisque les quatre points ne sont pas cocycliques, on a
α + γ > π ou β + δ > π, mais pas les deux à la fois. Sans perte de généralité, on suppose que
\ = γ > π − α = π − BAD,
α + γ > π et ainsi BCD \ ce qui assure que C est à l’intérieur du
cercle circonscrit à ABD, et donc que nC = 1. On prouve de même que nA = 1 et, puisque
β + δ < π, un raisonnement analogue montre que nB = nD = 0. Ainsi, dans ce cas, on a
nA + nB + nC + nD = 2.
Finalement, pour tout groupe de quatre points dans S, disons A, B, C, D et avec les nota-
tions ci-dessus, on a nA + nB + nC + nD ≤ 2 avec égalité si et seulement si A, B, C, D sont les
18 CHAPITRE 3. COURS DU GROUPE B (JUNIORS)

sommets d’un quadrilatère convexe. Il y a n4 choix possibles d’un groupe de

n

quatre points
de S d’où, en sommant les inégalités du type ci-dessus, il vient m(S) ≤ 2 4 , avec égalité si
et seulement si quatre points quelconques de S sont toujours les sommets d’un quadrilatère
convexe. D’après l’exercice n◦ 2, cette dernière condition est équivalente à ce que les points de
S sont les sommets d’un n-gone convexe, ce qui conclut.

Exercice 10. Soit S un ensemble de 1980 points du plan, deux quelconques toujours à une
distance au moins égale à 1 l’un de l’autre. Prouver que l’on peut trouver√220 de ces points
tels que deux quelconques soient toujours à une distance au moins égale à 3 l’un de l’autre.

Solution. On va prouver un peu mieux, à savoir que dans tout ensemble S de n points du
plan, deux quelconques toujours à une distance au moins égale à 1 l’un de l’autre, on peut
trouver au moins n7 de ces points tels que deux quelconques soient toujours à une distance au
√
moins égale à 3 l’un de l’autre.
Soit donc S un ensemble de n points du plan, deux quelconques toujours à une distance au
moins égale à 1 l’un de l’autre. Puisque S est fini, on peut trouver un repère orthonormé dans
lequel les ordonnées des points de S sont toutes distinctes. Soit P le point de S d’ordonnée √
maximale. Alors, tout autre point de S qui serait à une distance strictement inférieure à 3
de P appartient à la √demi-couronne de centre P et dont les demi-cercles limites sont ceux de
rayon 1 et de rayon 3, ce dernier étant exclu. On divise cette demi-couronne en 6 secteurs
correspondant à un angle en P de 30◦ . Si deux points de S appartenaient à un même de
ces secteurs, leur distance mutuelle serait strictement inférieure à la distance AB, où A est
sur le demi-cercle de rayon 1 et sur une des√demi-droites issues de P qui délimite le secteur,
alors que B est sur le demi-cercle de rayon 3 et sur l’autre des demi-droites issues de P qui
délimite le secteur. Or, il est facile de vérifier que AB = 1. Ainsi, il est impossible que deux
points de S appartienne à√un même secteur, ce qui prouve qu’au plus 6 points de S sont à
une distance inférieure à 3 de P . On choisit donc P , puis on "l’élimine", ainsi que les au
plus six points précédents. Puis, on recommence le raisonnement sur l’ensemble des points
restants. En suivant cet algorithme, qui s’arrêtera évidemment après un nombre fini d’étapes,
l’ensemble des points choisis (un à chaque étape) fournit bien un sous-ensemble√ de S avec au
n
moins 7 points, deux quelconques toujours à une distance au moins égale à 3 l’un de l’autre.

Exercice 11. Un ensemble M de points du plan est dit obtus lorsque trois points quelcon-
ques de M sont les sommets d’un triangle obtus, éventuellement aplati.
a) Prouver que pour tout ensemble M fini et obtus, il existe un point P du plan n’appartenant
pas à M et tel que M ∪ {P } soit obtus.
b) Cela reste-t-il vrai si M n’est plus supposé fini?

Solution. a) On note que, si A, B, P sont trois points du plan tels que P n’appartienne pas
à la bande D(A, B) délimitée par les droites perpendiculaires à (AB) respectivement en A et
en B, alors AP B est obtus en A ou en B (selon la plus grande des deux distances AP et BP ).
Soit alors un ensemble M = {A1 , ..., An } fini et obtus, dont on peut toujours supposer
qu’il contienne au moins trois points. Puisque M est fini, par paires, les éléments de M ne
déterminent qu’un nombre fini de directions. On peut ainsi trouver une droite ∆ qui n’est
perpendiculaire ni parallèle à aucune des droites (Ai Aj ). Dans ces conditions, chacune des
bandes D(Ai , Aj ) ne peut convrir qu’un segment borné de ∆ et, puisqu’il n’y a qu’un nombre
3.2. ALGÈBRE GROUPE B (JEAN-LOUIS) 19

fini de telles bandes, on peut trouver un point P sur ∆ qui n’est recouvert par aucune des
bandes. D’après notre remarque initiale, pour un tel point P , chacun des triangles Ai Aj P est
obtus, ce qui assure que M ∪ {P } est encore obtus.
b) Non. Il suffit de choisir M comme l’ensemble des points d’une droite d. Pour tout autre
point P du plan, il existe deux points A, B ∈ d tels que ABP soit équilatéral, d’où M ∪ {P }
n’est pas obtus.

Remarque. Si on impose que trois points d’un ensemble obtus ne soit jamais alignés, le
raisonnement du a) s’adapte sans difficulté car les droites (Ai Aj ) ne rencontrent ∆ que selon
un nombre fini de points, ce qui n’élimine qu’un nombre fini de points de ∆. Pour le b), on
peut choisir les points d’un demi-cercle en ne prenant qu’un seule des extrémités.

3.2 Algèbre groupe B (Jean-Louis)

La plupart des exercices nécessitent uniquement de connaître l’identité (a + b)2 = a2 + 2ab + b2
et l’IAG : Pn
n √ a
Pn 1 6 n a1 · · · an 6 i=1 i .
i=1 ai n
Par ailleurs, si a, b, c sont des réels et f une fonction à trois variables, on notera
X
f (a, b, c) = f (a, b, c) + f (b, c, a) + f (c, a, b).
cyc
P
Si g est une fonction à une variable, on note g(a) = g(a) + g(b) + g(c).

Exercice 1 Déterminer la valeur maximale possible de a1 a2 · · · a100 + (1 − a1 )(2 − a2 ) · · · (100 −

a100 ) sous la condition que pour tout k, ak est un nombre vérifiant 0 6 ak 6 k.
Exercice 2 Soient a, b, c des nombres réels tels que a2 + c2 6 4b. Montrer que pour tout x, on a
x4 + ax3 + bx2 + cx + 1 > 0.
Exercice 3 Montrer que si a1 , . . . , an sont des nombres réels positifs vérifiant a1 · · · an = 1 alors
(1 + a1 )(1 + a2 ) · · · (1 + an ) > 2n .
Exercice 4 Soient a1 , . . . , a4 des réels strictement positifs. Montrer que
a1 a2 a3 a4 a1 a2 a3 a4
+ + + 6 + + + .
a1 + a2 a2 + a3 a3 + a4 a4 + a1 a2 + a3 a3 + a4 a4 + a1 a1 + a2

Exercice 5 Déterminer le minimum de 2(a2 + b2 + c2 ) + 5abc sous la condition que a, b, c sont

des réels positifs vérifiant a + b + c = 3.
Exercice 6 Soient a, b, c, d, x, y, z, t des réels positifs tels que a + b + c + d = x + y + z + t = 1 et
x, y, z, t ∈ [0, 12 ]. Montrer que ax + by + cz + dt > 54abcd.
Exercice 7 Déterminer tous les entiers x, y, z tels que x2 + y 2 + z 2 + 3 < xy + 3y + 2z.
1
Exercice 8 Montrer que si a, b, c sont des réels strictement positifs tels que a + b + c = 4
alors
P 29b3 −a3
cyc ab+6b2 6 1.
20 CHAPITRE 3. COURS DU GROUPE B (JUNIORS)

Exercice 9 Déterminer la valeur maximale possible de c − a lorsque a 6 b 6 c sont des réels

vérifiant a + b + c = a3 + b3 + c3 − 3abc = 2.
2 3
P

Exercice 10 Déterminer la valeur minimale de cyc 5a + b+c lorsque a, b, c sont positifs et
2 2 2
vérifient a + b + c = 3.
Indications de solutions : Q Q Q
Solution de l’exercice 1 On pose ak + bk = k. On a ak + bk 6 (ak + bk ) (développer le
second membre), donc l’expression est majorée par 100!. Il y a égalité lorsque ∀k, ak = 0, ou
bien ∀k, ak = k.
Solution de l’exercice 2 L’expression est minorée par x4 + ax3 + (a2 + c2 )x2 /4 + cx + 1 = x2 (x +
a 2
2
) + ( cx
2
+ 1)2 .
√
Solution de l’exercice 3 Utiliser 1 + ai > 2 ai .
P ai+1 1 1 4
Solution de l’exercice 4 Ajouter aux deux membres et utiliser a+b + c+d > a+b+c+d .
ai + ai+1
Solution de l’exercice 5 On peut supposer a 6 b 6 c. On fixe c (donc a + b est fixé). L’expression
vaut 2(a + b)2 + (5c − 4)ab. Comme c > 4/5, l’expression est minimale lorsque a = 0. Elle vaut
alors 2(b2 + c2 ), qui est minimale lorsque b = c = 3/2. Le minimum vaut 9.
Solution de l’exercice 6 On peut supposer a 6 b 6 c 6 d. A x + y fixé, l’expression ax + by
est minimale lorsque x est le plus grand possible. On raisonne de même sur (x, z) et (x, t),
et on se ramène ainsi à x = 21 , et de même à y = 12 . Le problème revient donc à montrer
que a + b > 108abcd. Or, à a + b et c + d fixés, abcd est maximum lorsque a = b et c = d.
Donc le problème revient à montrer que 1 > 54ac2 sous la condition a + c = 21 , ou encore
a + 2c + 2c = 12 =⇒ a · 2c · 2c 6 216
1
. C’est une conséquence de l’IAG.
Solution de l’exercice 7 Cela revient à résoudre x2 + y 2 + z 2 + 4 6 xy + 3y + 2z, ou encore
(x − y2 )2 + 3( y2 − 1)2 + (z − 1)2 6 0. On trouve (x, y, z) = (1, 2, 1).
Solution de l’exercice 8 On a a3 + b3 = (a + b)(a2 − ab + b2 ) > ab(a + b) donc il suffit d’utiliser
P 30b3 − ab(a + b) P P
que cyc 2
= cyc 5b − a = 4 a = 1.
ab + 6b
Solution de l’exercice 9 On a (a + b + c)(a2 + b2 + c2 − ab − bc − ca) = 2 donc a + b + c = 2 et
ab + bc + ca = 1. Cette dernière égalité s’écrit 1 = b(2 − b) + ca donc (c − a)2 = (c + a)2 − 4ac =
(2 − b)2 − 4(1 − b(2 − b)) = 4b − 3b2 = 34 − 3(b − 23 )2 dont la valeur maximale est 4/3, donc le
maximum de c − a est √23 .
Solution de l’exercice 10 C’est 648. On utilise l’IAG
1/6
2a5

2
a+a+a+a+a+ > 216
b+c b+c
donc 3
√ a4

2
5a + > 216 2 √
b+c a ab + ac
√ ( a2 ) 2
P
D’après l’inégalité des mauvais élèves, la somme est minorée par 216 2 P √ .
P √ a ab + ac
Enfin, on utilise Cauchy-Schwarz : ( a ab + ac)2 6 a2 2ab 6 2( a2 )2 , ce qui con-
P P P
clut.
3.3. COMBINATOIRE GROUPE B (THOMAS) 21

3.3 Combinatoire groupe B (Thomas)

Le cours reprenait quasiment le contenu d’un ancien cours de Pierre Bornsztein que l’on re-
produit ici pour plus de commodit
- Énoncés -
Exercice 11 On dispose de 21 allumettes. Chacun à son tour, l’un des deux joueurs prend 1, 2
ou 3 allumettes. Celui qui prend la dernière allumette gagne.
Déterminer celui des deux joueurs qui possède une stratégie gagnante.
Exercice 12 On dispose d’un jeu complet de dominos. Deux joueurs jouent, chacun à son
tour, selon la règle suivante : Le joueur choisit un domino parmi ceux non encore utilisés, et
le place à l’une des extrémités de la chaîne déjà formée, de sorte que deux dominos adjacents
aient toujours les mêmes numéros marqués sur leurs cases adjacentes.
Le premier qui ne peut jouer perd.
Déterminer celui des deux joueurs qui possède une stratégie gagnante.
Exercice 13
a) Sur un tableau 2012 × 2012 formé exclusivement de cases blanches, Alice et Bob jouent
au jeu suivant : Alice commence par noircir la case en haut à gauche. Bob doit alors
noircir une case non encore noircie et adjacente (i.e. ayant un côté commun) à celle que
vient de noircir Alice. Puis c’est au tour d’Alice de jouer, et de noircir une case blanche
adjacente à la case précédemment noircie par Bob, et ainsi de suite. Lorsqu’un joueur ne
peut plus jouer, il a perdu.
Déterminer lequel des deux joueurs possède une stratégie gagnante.
b) Et s’ils jouaient sur un tableau 2011 × 2011 ?

Exercice 14 Partant de 0, Alice et Bob ajoutent chacun leur tour à la quantité en cours un
nombre de leur choix parmi {1, 2, ..., 10}. Celui qui atteint 100 gagne.
Qui a une stratégie gagnante?
Exercice 15 On place un jeton sur la case C1 d’un échiquier classique. Deux joueurs le dépla-
cent à tour de rôle, en respectant la règle suivante : à chaque tour, on peut déplacer le jeton
d’autant de cases que l’on veut, mais au moins une, soit vers la droite, soit vers le haut soit
en diagonale vers la droite et vers le haut. Celui des deux joueurs qui amène le jeton en H8
gagne.
Déterminer lequel des deux joueurs a une stratégie gagnante.
Exercice 16 Sur la table se trouvent 1999 jetons. Tour à tour, Albert et Barbara doivent enlever
au moins un jeton et au plus la moitié des jetons restants au moment où ils jouent. Le joueur
qui laisse un unique jeton sur la table perd la partie. C’est Albert qui commence. Déterminer
lequel des deux joueurs possède une stratégie gagnante et décrire une telle stratégie.
Exercice 17 Alice et Bob jouent aux échecs, mais en ayant le droit d’enchaîner deux coups par
tour. C’est Alice qui commence. Prouver qu’elle peut s’assurer de ne pas perdre.
Exercice 18 On inscrit n = 2 sur un tableau. A tour de rôle, Alice (la première) et Bob ajoutent
un diviseur d du nombre n qui est inscrit au moment où ils jouent, avec 0 < d < n (et laissent
donc n + d).
22 CHAPITRE 3. COURS DU GROUPE B (JUNIORS)

a) Le premier joueur qui fait dépasser 20112012 perd. Qui a une stratégie gagnante?

b) Le premier joueur qui fait dépasser 20122011 perd. Qui a une stratégie gagnante?

Exercice 19 Une plaquette de chocolat est un rectangle de m × n carrés-unité. Seul le carré

en bas à gauche est empoisonné. A tour de rôle, Achille, en premier, et Béatrice découpe la
plaquette selon la règle suivante : on choisit un carré c et prend tout le rectangle dont c est
le coin inférieur gauche (il se peut que certains des carrés de ce rectangle aient déjà été pris
auparavant). Evidemment, celui des deux qui prend le carré empoisonné perd.
Quel est celui qui a une stratégie gagnante?
Exercice 20 Soit n > 0 un entier. A tour de rôle, Alice et Bob écrivent au tableau un entier
strictement positif et ne dépassant pas n. Aucun nombre n’est effacé, et il est interdit d’écrire
un nombre qui divise un nombre déjà écrit au tableau. C’est Alice qui commence et le premier
qui ne peut plus jouer perd la partie. Qui a une stratégie gagnante?

- Corrigés -

Solution de l’exercice 11 Le premier joueur prend une seule allumette à son premier coup. Puis,
à chaque coup suivant, si son adversaire vient de prendre a allumettes, il en choisit alors 4 − a.
Ainsi, après chacun de ses coups, le nombre d’allumettes prises augmente de 4. En particulier,
le premier joueur prendra la 21ième , et gagne ainsi la partie. C’est un exemple de stratégie
basée sur le principe “si tu peux jouer, alors je pourrais jouer après toi”. Dans un jeu qui
doit nécessairement s’arrêter, un joueur qui possède une telle stratégie est alors sûr de gagner,
puisqu’il ne sera pas le premier à être bloqué...
La difficulté est de trouver la façon adéquate de jouer : si l’exemple est ici assez simple, il
peut ne pas paraître évident tout de suite qu’une bonne façon de jouer est de compléter à 4 ce
qu’a fait son adversaire au coup précédent...
Nous verrons ci-dessous une autre façon d’analyser la situation, qui rendra la solution
trouvée plus naturelle.
Solution de l’exercice 12 On peut trouver une stratégie du même type pour le premier joueur,
mais un peu plus subtile :
Le premier joueur choisit le domino (0, 0). Alors, le second joueur est obligé de choisir un
domino (0, a) (qu’il peut évidemment placer en (a, 0)) avec a 6= 0. Le premier joueur choisit
alors le domino (a, a). Dans cette situation, on constate que l’on a la propriété suivante :
pour tout entier k, le domino (0, k) est encore disponible si et seulement si le domino (a, k)
est encore disponible. De plus, le second joueur ne peut choisir un double.
Donc, à partir de maintenant, si le second joueur choisit un domino, il est forcément de la
forme (0, k) ou (a, k) et le premier peut alors choisir à son tour suivant celui de ces dominos
qui reste disponible, et le mettre à la suite du domino du second joueur. Ce faisant, le sec-
ond joueur se retrouve dans une situation où la propriété ci-dessus est à nouveau vraie. En
procédant ainsi, le premier joueur est sûr de ne pas être le premier bloqué et donc de gagner
la partie
Solution de l’exercice 13
3.3. COMBINATOIRE GROUPE B (THOMAS) 23

a) Là encore, on peut trouver une stratégie de ce type, mais pour le second joueur. Celui-
ci doit imaginer que le tableau est pavé par des dominos, ce qui possible puisqu’il y
a un nombre pair de cases. Un tel pavage étant fixé une fois pour toutes, la stratégie
de Bob est alors très simple : il “complète” à chaque fois le domino que vient juste de
commencer à colorier Alice. Ainsi, à son premier coup, il colorie la case qui forme un
domino avec la case en haut à gauche. Alice est alors obligée de noircir une case d’un
domino non encore utilisé, ce qui laisse à Bob la possibilité de compléter à nouveau le
domino à son prochain coup. À chacun de ses coups, Alice est alors obligée “d’ouvrir”
un domino, pour autant qu’elle puisse jouer, et laisse à Bob la possibilité de jouer en le
complétant.
S’il adopte cette stratégie, c’est donc Alice qui va être bloquée la première, et Bob qui va
gagner la partie.
b) Cette fois, c’est Alice qui possède une stratégie gagnante : c’est exactement la même
qu’au a), mais en ne considérant que le pavage du tableau dont on a éliminé la case en
haut à gauche (il est facile de vérifier qu’une fois cette case éliminée, un tel pavage existe
puisque 2011 − 1 = 2010 est pair).
Remarque.
On aura évidemment observé que les valeurs 2012 ou 2011 sont anecdotiques, dans le sens
où seule la parité du nombre choisi est importante.
Nous allons maintenant nous intéresser à une deuxième approche : l’analyse des positions
gagnantes, le plus souvent à partir de ce qui est supposé être la fin du jeu (on parle alors
d’analyse rétrograde). Une position est dite gagnante lorsque le joueur qui doit jouer à partir de
cette position est sûr de gagner (en jouant au mieux évidemment). Si le jeu doit nécessaire-
ment se terminer avec la victoire de l’un ou de l’autre, les positions qui ne sont pas gagnantes
sont alors perdantes.
Revenons sur l’exercice 1 :
Les positions 1, 2, 3 sont évidemment gagnantes puisque le joueur à qui c’est le tour peut
prendre toutes les allumettes d’un seul coup. Mais la position 4 est perdante car le joueur qui
doit jouer est obligé de laisser 1, 2 ou 3 allumettes et donne ainsi une position gagnante à son
adversaire. Du coup, les positions 5, 6, 7 sont gagnantes puisque le joueur concerné peut ne
laisser que 4 allumettes et donne ainsi une position perdante. On en déduit que la position 8
est perdante.
Et ainsi de suite, on prouve que les positions perdantes sont exactement les multiples de 4.
En y regardant de plus près, on constate que cela correspond à la stratégie décrite initialement.
Solution de l’exercice 14
C’est Alice, qui commence, qui a une stratégie gagnante. Pour le prouver, on va étudier
les positions (i.e. les quantités obtenues) gagnantes de ce jeu :
Clairement, 100 est perdante (le jeu vient de se terminer par la victoire de l’adversaire...). Et
donc, les quantités 90, 91, ..., 99 sont gagnantes (un joueur qui part d’une telle quantité gagne
à son prochain coup). Par suite, 89 est perdante, puisque le joueur qui doit alors jouer laissera
une quantité égale à l’un des nombres 90, 91, ..., 99.
Comme ci-dessus, on en déduit que 79, 80, ..., 88 sont gagnantes. Puis, que 78 est perdante.
Et ainsi de suite, on vérifie facilement que les positions perdantes sont de 11 en 11, à savoir
100, 89, 78, 67, 56, 45, 34, 23, 12, 1.
24 CHAPITRE 3. COURS DU GROUPE B (JUNIORS)

Puisque 1 est perdante, Alice commence par choisir 1, laisse donc une position perdante à
Bob, et assure alors sa victoire en pouvant rester à chaque coup sur des positions gagnantes.

Généralisation.
Si l’on joue avec les entiers de 1 à n, et qu’à chaque coup on ajoute un nombre entre 1 et p, le
raisonnement ci-dessus s’adapte en tout point pour montrer que les positions perdantes sont
tous les entiers de la forme n − k(p + 1). Si n = q(p + 1) + r est la division euclidienne de n par
p + 1, alors r ∈ {0, ..., p} et les positions perdantes sont les entiers de la forme (q − k)(p + 1) + r,
avec 0 ≤ k ≤ q.
En particulier :
- Si r = 0, la position perdante la plus proche du départ (hormis 0) est p + 1. Le premier
joueur ne peut l’atteindre à son premier coup, et quel que soit ce premier coup, le second
joueur, lui, pourra s’y placer. C’est donc le second joueur qui a une stratégie gagnante.
- Si r 6= 0, le premier joueur peut alors se placer en r à son premier coup et assurer sa
victoire comme ci-dessus.
Solution de l’exercice 15 Si le jeton est au départ en C1, c’est le premier joueur qui possède une
stratégie gagnante.
En fait, pour toute case de départ, via une analyse des positions, on peut déterminer lequel
des deux joueurs a une stratégie gagnante : la case H8 est perdante puisque le joueur qui doit
jouer alors que le jeton est dans cette case vient juste de perdre... Du coup, toutes les cases de
la ligne n◦ 8 ou de la colonne H ou de la diagonale A1 − H8 sont des positions gagnantes. Mais
alors, les positions F 7 et G6 sont perdantes puisqu’un joueur qui doit jouer à partir d’une
telle case met forcément le jeton sur une des cases gagnantes ci-dessus. On en déduit que
toutes les cases non encore déterminées dans les colonnes, lignes ou diagonales respectives
de ces deux cases sont gagnantes. Comme ci-dessus, cela entraine que les cases C5 et E3
sont perdantes. De même, les cases non encore déterminées dans les lignes, colonnes ou
diagonales respectives de ces deux cases sont alors gagnantes. Par suite, les cases A4 et D1
sont perdantes, et les autres sont gagnantes.
En particulier, la case C1 est gagnante. Donc, le premier joueur possède une stratégie
gagnante, décrite ci-dessus : son premier coup consiste à amener le jeton en D1 (ou C5) qui
est perdante puis, selon le coup du second joueur à amener à chaque fois le jeton dans des
positions perdantes.
Solution de l’exercice 16 C’est Albert qui possède une stratégie gagnante. Analysons les posi-
tions :
Clairement, 1 est gagnante (puisque le joueur qui doit jouer vient de gagner la partie...), et
2 est perdante car celui qui doit jouer est obligé de laisser un seul jeton et perd la partie. On
en déduit que 3 et 4 sont gagnantes (le joueur peut laisser 2 jetons et donne ainsi une position
perdante à son adversaire). Du coup, 5 est perdante car le joueur doit alors laisser 3 ou 4
jetons, et donne alors une position gagnante à son adversaire. Cela entraine que 6, 7, 8, 9, 10
sont gagnantes (le joueur laisse alors 5, qui est perdante), mais que 11 est perdante (le joueur
est obligé de laisser 6, 7, 8, 9 ou 10 qui sont gagnantes).
Afin d’éviter de tout faire à la main, il est judicieux de prendre un peu de hauteur. Pour
cela, on constate que si k est perdante alors k + 1, k + 2, ..., 2k sont gagnantes (le joueur laisse
alors k, dont on vient de dire qu’elle était supposée perdante), et 2k + 1 est perdante (le joueur
est obligé de laisser k + 1, k + 2, ..., 2k − 1 ou 2k, qui sont gagnantes). Cela permet de déter-
3.3. COMBINATOIRE GROUPE B (THOMAS) 25

miner les positions perdantes (et les positions gagnantes) de proche en proche, mais plus
rapidement... Ainsi, les positions perdantes sont
2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, ...
Et donc, 1999 est gagnante, ce qui conclut.

Remarque.
De façon plus générale, à l’aide de ce que l’on vient de faire, on peut prouver que les
positions perdantes sont les nombres de la forme 3 × 2n − 1, où n ≥ 0 est un entier.
Solution de l’exercice 17 Qu’Alice soit assurée de ne pas perdre, c’est dire que Bob ne possède
pas de stratégie gagnante.
Par l’absurde : supposons que Bob ait une stratégie gagnante.
Alors Alice commence par déplacer son cavalier de B1 en A3 et retour. C’est donc Bob
qui doit jouer, comme s’il était le premier joueur. Or, puisque le second joueur possède une
stratégie gagnante, Alice peut l’utiliser et donc s’assurer de battre Bob. Ainsi, Bob possède
une stratégie gagnante mais est sûr de perdre. Contradiction.
Donc, Bob n’a pas de stratégie gagnante, ce qui assure qu’Alice est sûre de pouvoir éviter
de perdre.

Remarques.
Attention, qu’Alice soit sûre de ne pas perdre ne signifie pas qu’elle soit sûre de gagner,
car il pourrait y avoir partie nulle... De plus, nous n’avons finalement pas décrit de stratégie
adéquate pour Alice.
Cela dit, l’exemple ci-dessus est un exemple de ce que l’on peut appeler un “vol de stratégie”
: afin de prouver qu’un joueur ne possède pas de stratégie gagnante, on suppose (par l’absurde)
qu’il en a une et on prouve que l’autre joueur peut l’utiliser à son tour (i.e. la lui voler), d’où
la contradiction.
Pour que tout fonctionne au mieux, et que l’on soit assuré que l’un des joueurs ait effective-
ment une stratégie gagnante (là, on a juste prouvé qu’un joueur n’en avait pas, ce qui n’est pas
du tout pareil), il serait idéal que l’on soit sûr que le jeu se finisse, jamais sur une partie nulle,
et qu’il soit possible de prouver que, pour un tel jeu, l’un des deux joueurs possède toujours
une stratégie gagnante (du coup, si on a éliminé une possibilité, c’est donc que l’autre joueur
possède la stratégie désirée). Et justement, c’est exactement ce que dit le théorème suivant,
dû à Zermelo :

Théorème (Zermelo)

Dans un jeu fini à deux joueurs, à information parfaite et n’ayant que deux issues possibles
(à savoir la victoire du joueur n◦ 1 ou la victoire du joueur n◦ 2), l’un des deux joueurs possède
une stratégie gagnante.

Quelques précisions : dire que le jeu est fini signifie que l’arbre de toutes les positions
possibles, aussi gigantesque soit-il, est tout de même fini, et dire qu’il est à information parfaite
signifie que l’on exclut toute intervention du hasard (ainsi, on ne parle pas ici de la plupart
des jeux de dés, par exemple).
Pour ceux qui voudraient en savoir plus et, en particulier, lire la démonstration de ce
théorème, que nous n’allons pas faire ici, peuvent se reporter à l’adresse suivante :
26 CHAPITRE 3. COURS DU GROUPE B (JUNIORS)

http://www.math.ens.fr/culturemath/maths/pdf/jeux/strategies.pdf
Disons juste, qu’en gros, il s’agit de remonter l’arbre de toutes les positions possibles du
jeu, à partir des feuilles (les situations finales) pour remonter à la racine (la position de départ)
en controlant à chaque étape lequel des deux joueurs est en position gagnante. C’est, en plus
raffiné, ce que nous avons fait dans les exercices précédents.

On constate que le type d’approche ci-dessus est “non constructive” dans la mesure où
l’on ne décrit pas ce que serait alors une stratégie gagnante. Il peut alors être un peu diffi-
cile d’accepter l’idée que l’on sache qu’un joueur donné ait une stratégie gagnante sans pour
autant être capable d’en expliciter une...
Et pourtant, c’est bien ce que l’on va voir dans les exercices ci-dessous :
Solution de l’exercice 18

a) Bon, là, on peut encore s’en sortir facilement. En effet, Alice peut décider d’ajouter 1 à
chaque tour. Ce faisant, il est facile de vérifier qu’elle laisse un nombre impair à Bob, qui
est donc obligé de choisir un nombre d impair et de laisser alors un nombre pair. Quel
que soit ce nombre pair, soit Bob vient de perdre (et donc le premier vient de gagner)
soit il vient de laisser un nombre qui est strictement inférieur à 20112012 (qui est impair!).
Ainsi, en ajoutant à nouveau 1, Alice ne dépasse toujours pas 20112012 et laisse encore un
nombre impair à Bob.
On retrouve une stratégie du type “si tu peux jouer, alors moi aussi”, qui assure que ce
n’est pas Alice qui va être bloquée la première. Or, il est clair que le jeu se finira après
un nombre fini de coups (pas plus de 20112012 − 1 coups) et que l’un des deux joueurs
finira par gagner.
Ainsi, c’est Alice qui possède une stratégie gagnante, et celle-ci est particulièrement sim-
ple à mettre en oeuvre...

b) En fait, quel que soit le nombre N ≥ 6 que l’on ne doit pas dépasser, c’est toujours Alice
qui possède une stratégie gagnante. Evidemment, si N est impair, la stratégie du a)
fonctionne parfaitement. Par contre, dans le cas où N est pair, si Alice décide de jouer
de cette façon, il est facile pour Bob de faire de même et de gagner, ce qui montre que
la façon de jouer d’Alice est alors une stratégie...perdante! Alice va donc devoir trouver
autre chose. Mais le théorème de Zermelo lui dit qu’elle a bien raison d’y croire : en
effet, comme on l’a signalé ci-dessus, le jeu est clairement fini, sans partie nulle et à
information parfaite, donc l’un des deux joueurs possède une stratégie gagnante.

Par l’absurde : supposons que Bob ait une stratégie gagnante.

Lors de son premier tour, Alice est obligée de laisser n = 3 (elle ne peut choisir que
d = 1). Du coup, Bob est obligé de choisir d = 1 et laisse n = 4. Á partir de là, deux
options sont possibles pour Alice : laisser n = 5 ou n = 6.
Mais, puisque Bob possède une stratégie gagnante, c’est donc que si Alice laisse n = 5,
Bob qui est alors obligé de laisser n = 6 va gagner. Cela assure que le joueur qui laisse
n = 6 gagne. Dans ces conditions, Alice peut choisir de directement laisser n = 6 puis,
en utilisant la stratégie de Bob, gagner la partie. Cela contredit donc que Bob possède
une stratégie gagnante.
3.3. COMBINATOIRE GROUPE B (THOMAS) 27

Ainsi, Bob n’a pas de stratégie gagnante, et le théorème de Zermelo assure que c’est donc
Alice qui en possède une. Par contre, à la différence du a), sauf à étudier toutes les parties
possibles, il paraît difficile de donner une description simple d’une telle stratégie...

Solution de l’exercice 19 Il est évident que si m = n = 1, le premier joueur va perdre... On

suppose donc que m ≥ 2 ou n ≥ 2.

Clairement, nous sommes face à un jeu pour lequel le théorème de Zermelo s’applique.
L’un des deux joueurs possède donc une stratégie gagnante.
Par l’absurde : supposons que ce soit Béatrice.
Si Achille choisit le carré situé en haut et à gauche, il laisse la plaque quasi entière à Béa-
trice qui, à partir de cette position, possède une stratégie qui va lui assurer la victoire. En
particulier, selon cette stratégie, Béatrice va choisir un carré c et découper le “rectangle” cor-
respondant. On note qu’à ce rectangle il manque en fait exactement le carré choisi par Achille
pour être complet. Mais alors, Achille pourrait dès le départ choisir le carré c et découper le
rectangle tout entier, et laisser ainsi Béatrice dans la position exacte dans laquelle lui-même se
trouvait selon sa première option. Il n’a alors plus qu’à suivre la stratégie gagnante de Béa-
trice pour gagner lui-même, privant ainsi celle-ci de la victoire qu’elle était assurée d’obtenir,
ce qui est absurde.
Ainsi, Béatrice n’a pas de stratégie gagnante, et c’est donc Achille qui en possède une.

Remarque.
Ce jeu est connu sous le nom de Chomp et a été inventé par le mathématicien David Gale.
Sauf dans certain cas très simples (par exemple, si m = 1 auquel cas le premier joueur ne
laisse directement que le carré empoisonné), on ne connaît pas de description d’une stratégie
gagnante sans recours à un ordinateur afin d’analyser toutes les positions possibles.
Solution de l’exercice 20 C’est Alice qui posède une stratégie gagnante. Le raisonnement est
très proche de celui de l’exercice précédent.
D’après le théorème de Zermelo, nous savons que l’un des deux joueurs possède une telle
stratégie. Par l’absurde : supposons que ce soit Bob.
Si Alice écrivait 1, Bob écrirait alors un certain nombre k de façon à suivre sa stratégie et
à assurer sa victoire. Mais alors, Alice peut directement écrire k, ce qui interdit à chacun des
deux joueurs d’écrire ultérieurement 1, et laisse donc Alice dans la situation exacte où était
Bob lorsqu’il suivait sa stratégie. En suivant cette même stratégie, Alice a donc assurer sa
victoire, en contradiction avec notre hypothèse.
Ainsi, Bob n’a pas de stratégie gagnante et, selon ce qui a été dit au départ, c’est donc
qu’Alice en a une.