38e Olympiade mathématique du Canada

Mercredi, 29 mars, 2006

Solutions aux problèmes 2006 de OMC

1. Soit f (n, k) le nombre de façons de distribuer k biscuits à n enfants de sorte que chaque enfant reçoive au plus 2
biscuits. Par exemple, si n = 3, alors f (3, 7) = 0, f (3, 6) = 1 et f (3, 4) = 6.
Déterminer la valeur de

f (2006, 1) + f (2006, 4) + f (2006, 7) + · · · + f (2006, 1000) + f (2006, 1003) .

Commentaire. Malheuresement, il avait une erreur dans l’énoncé de ce problème. Il était prévu que la somme continuait
jusqu’à f (2006, 4012).

Solution 1. Le nombre de façons de distribuer k biscuits à 2006 enfants est égal au nombre de façons de distribuer 0
biscuit à un enfant particulier et k au reste, plus le nombre de façons de distribuer 1 biscuit à l’enfant particulier et k − 1
au reste, plus le nombre de façons de distribuer 2 biscuits à l’enfant particulier et k − 2 au reste. Ainsi, f (2006, k) =
f (2005, k) + f (2005, k − 1) + f (2005, k − 2), d’où la somme demandée est
1003
X
1+ f (2005, k) .
k=1
¡n¢
Dans l’évaluation de f (n, k), supposons qu’il y a r enfants qui reçoivent 2 biscuits ; ces r enfants peuvent être choisis de r
façons. Alors il y a k − 2r biscuits desquels au plus un est donné pour chacun des n − r enfants. Par conséquent,
bk/2c µ ¶µ ¶ ∞ µ ¶µ ¶
X n n−r X n n−r
f (n, k) = = ,
r=0
r k − 2r r=0
r k − 2r
¡x¢
avec y = 0 si x < y et si y < 0. La réponse est
1003
XX ∞ µ ¶µ ¶ ∞ µ
X ¶ 1003 µ ¶
2005 2005 − r 2005 X 2005 − r
= .
r k − 2r r k − 2r
k=0 r=0 r=0 k=0

Solution 2. Le nombre cherché est la somme des coefficients des termes dont les degrés n’excédent pas 1003 dans l’expansion
de (1 + x + x2 )2005 , qui est égal au coefficient de x1003 dans l’expansion de

(1 + x + x2 )2005 (1 + x + · · · + x1003 ) = [(1 − x3 )2005 (1 − x)−2005 ](1 − x1004 )(1 − x)−1

= (1 − x3 )2005 (1 − x)−2006 − (1 − x3 )2005 (1 − x)−2006 x1004 .

Comme le degré de chaque terme dans l’expansion du deuxième membre du côté droit excède 1003, on cherche alors le
coefficient de x1003 dans l’expansion du premier membre:
2005
X µ ¶ ∞ µ ¶
3 2005 −2006 i 2005 3i X j −2006
(1 − x ) (1 − x) = (−1) x (−1) xj
i=0
i j=0
j

1
 2005
XX ∞ µ ¶µ ¶
2005 2005 + j 3i+j
= (−1)i x
i=0 j=0
i j
∞ µ 2005
X X µ ¶µ ¶¶
2005 2005 + k − 3i
= (−1)i xk .
i=1
i 2005
k=0

Le nombre cherché est alors

334
X µ ¶µ ¶ X334
2005 3008 − 3i (3008 − 3i)!
(−1)i = (−1)i .
i=1
i 2005 i=1
i!(2005 − i)!(1003 − 3i)!
¡3008−3i¢
(Noter que 2005 = 0 lorsque i ≥ 335.)

2. Soit ABC un triangle acutangle (triangle dont les angles sont aigus). Inscrire un rectangle DEF G dans ce triangle de
sorte que D est sur AB, E est sur AC et F et G sont sur BC. Décrire le lieu des points d’intersection des diagonales de tous
les rectangles DEF G possibles (c’est-à-dire décrire la courbe occupée par ces points).

Solution. Le lieu cherché est le segment de droite joignant le point milieu M de BC au point milieu K de la hauteur
AH. Remarquer qu’un segment de droite DE avec D sur AB et E sur AC détermine un rectangle inscrit; le point milieu F
de DE est sur la médiane AM , tandis que le point milieu de la perpendiculaire à BC issue de F est le centre du rectangle.
Celui-ci est sur la médiane M K du triangle AM H.
Réciproquement, n’importe quel point P sur M K est le centre d’un triangle ayant une base sur BC et dont la hauteur
est égale au double de la distance du point K à BC.

3. Dans un arrangement rectangulaire de nombres réels non négatifs à m lignes et n colonnes, chaque ligne et chaque
colonne contient au moins un élément positif. De plus, si l’intersection d’une ligne et d’une colonne est un élément positif,
alors la somme de leurs éléments est la même. Démontrer que m = n.

Solution 1. Considérons tout d’abord le cas où toutes les lignes possèdent la même somme positive s; ceci comprend la
situation particulière où m = 1. Alors chaque colonne ayant un élément positif en commun avec une autre ligne doit avoir
aussi une somme égale à s. Par conséquent, la somme de toutes les entrées dans la matrice est ms = ns, d’où m = n.
On montre le cas général par induction sur m. Le cas m = 1 étant déjà réglé. Supposons qu’on a un tableau m × n
dont les lignes n’ont pas toutes la même somme. Soit r < m le nombre des lignes qui ont la même somme s, et chacune des
autres lignes a une somme différente. Alors chaque colonne partageant une entrée positive avec une de ces lignes doit aussi
avoir s comme somme. Supposons qu’il y a c colonnes avec une somme s. La situation est essentiellement inchangée si on
permute les lignes et puis les colonnes de sorte que les premières r lignes et les premières c colonnes aient s comme somme.
Puisque toutes les entrées qui sont dans les r premières lignes et non pas dans les c premières colonnes et toutes les entrées
qui sont dans les c premières colonnes et non pas dans les r premières lignes doivent être 0, on peut partitionner le tableau
en une sous-matrice de format r × c dans lequel toutes les lignes et les colonnes ont la somme s et qui satisfait l’hypothse
du problme, deux sous-matrices rectangulaires formés d’entrées nulles dans le coin supérieur droit et le coin inférieur gauche
et une sous-matrice de format (m − r) × (n − c) dans le coin inférieur droit qui satisfait les conditions du problème. Par
l’hypothèse d’induction, on voit que r = c, d’où m = n.

Solution 2. [Y. Zhao] Dénotons par aij l’entrée de la ième ligne et la jième colonne du tableau, et posons S = {(i, j) :
aij > 0}. Supposons que ri est la somme de la ième ligne et que cj est la somme de la jième colonne. Alors ri = cj chaque
fois que (i, j) ∈ S. On a alors
X aij X aij
{ : (i, j) ∈ S} = { : (i, j) ∈ S} .
ri cj

On calcule la somme de chaque côté séparément.

X aij X aij Xm n m µ ¶ m
1 X X 1 X
{ : (i, j) ∈ S} = { : 1 ≤ i ≤ m, 1 ≤ j ≤ n} = aij = ri = 1=m.
ri ri r
i=1 i j=1 i=1
ri i=1

X aij X aij Xn m n µ ¶ n
1 X X 1 X
{ : (i, j) ∈ S} = { : 1 ≤ i ≤ m, 1 ≤ j ≤ n} = aij = cj = 1=n.
cj cj c
j=1 j i=1 j=1
cj j=1

2
D’où m = n.
Commentaire. La deuxième solution peut être rendue plus claire et plus élégante en définissant uij = aij /ri pour tout
(i, j). Si aij = 0, alors uij = 0. Si aij > 0, alors, par hypothèse, uij = aij /cj , une relation qui est satisfaite pour tout (i, j).
On trouve que
Xn Xn
uij = 1 et uij = 1
j=1 i=1

pour 1 ≤ i ≤ m et 1 ≤ j ≤ n, de sorte que (uij ) est un tableau de format m × n dont la somme sur chaque ligne et chaque
colonne est égale à 1. Ainsi
m µX
X n ¶ X n µX
X m ¶
m= uij = {uij : 1 ≤ i ≤ m, 1 ≤ j ≤ n} = uij =n
i=1 j=1 j=1 i=1

(étant la somme de toutes les entrées du tableau).

4. Considérer un tournoi composé de 2n + 1 équipes. Chaque équipe rencontre les autres équipes exactement une fois.
On dit que trois équipes X, Y et Z forment un triplet cyclique si X défait Y , Y défait Z, et Z défait X. Il y a aucune égalité.
(a) Déterminer le nombre minimum de triplets cycliques possibles.
(b) Déterminer le nombre maximum de triplets cycliques possibles.

Solution 1. (a) Le minimum est 0, ce qui est réalisé par un tournoi dans lequel l’équipe Ti défait l’équipe Tj si et seulement
si i > j.
(b) N’importe quel ensemble de trois équipes constitue soit un triplet cyclique soit un “triplet dominé” dans lequel un
équipe défait
¡ ¢les deux autres; dénotons par c le nombre des triplets cycliques et par d celui des triplets dominés. ¡xi ¢ Alors
c + d = 2n+1 . Supposons que l’équipe Ti défait xi autres équipes; alors il est l’équipe gagnant dans exactement 2 triplets
3 P2n+1 ¡ ¢
dominés. Remarquer que i=1 xi = 2n+1 2 , le nombre total des jeux. Alors

Xµ
2n+1
xi
¶ 2n+1
1 X 2 1 2n + 1
µ ¶
d= = xi − .
i=1
2 2 i=1 2 2
P2n+1 P2n+1
Par l’inégalité de Cauchy-Schwarz, (2n + 1) i=1 x2i ≥ ( i=1 xi )2 = n2 (2n + 1)2 , d’où
µ ¶ 2n+1
X µxi ¶ µ2n + 1¶ n2 (2n + 1) 1 µ2n + 1¶ n(n + 1)(2n + 1)
2n + 1
c= − ≤ − + = .
3 i=1
2 3 2 2 2 6

Pour trouver la borne supérieure, supposons que les équipes sont T1 = T2n+2 , T2 = T2n+3 , · · ·, Ti = T2n+1+i , · · ·,
T2n+1 = T4n+2 . Pour chaque i, supposons que l’équipe Ti défait Ti+1 , Ti+2 , · · · , Ti+n et perd à Ti+n+1 , · · · , Ti+2n . On doit
vérifier que c’est une attribution cohérente des victoires et des pertes, puisque le résultat pour chaque paire d’équipes est
défini deux fois. On peut voir ceci en remarquant que (2n + 1 + i) − (i + j) = 2n + 1 − j ≥ n + 1 for 1 ≤ j ≤ n . Les triplets
cycliques sont: (Ti , Ti+j , Ti+j+k ) où 1 ≤ j ≤ n et (2n + 1 + i) − (i + j + k) ≤ n, i.e., lorsque 1 ≤ j ≤ n et n + 1 − j ≤ k ≤ n.
Pour tout i, ceci donne 1 + 2 + · · · + n = 12 n(n + 1) triplets cycliques. Lorsqu’on couvre toutes les valeurs de i, chaque triplet
cyclique est compté trois fois, d’où le nombre de triplets cycliques est
µ ¶
2n + 1 n(n + 1) n(n + 1)(2n + 1)
= .
3 2 6

Solution 2. [S. Eastwood] (b) Soit t le nombre de triplets cycliques et u celui de triplets ordonnés d’équipes (X, Y, Z) où
X défait Y et Y défait Z. Chaque triplet cyclique produit trois triplets ordonnés tandis que les autres triplets en produisent
exactement un. Le nombre total de triplets est
µ ¶
2n + 1 n(4n2 − 1)
= .
3 3

3
Le nombre de triplets non-cycliques est
n(4n2 − 1)
−t .
3
Alors µ ¶
n(4n2 − 1)
u = 3t + −t =⇒
3
3u − n(4n2 − 1) u − (2n + 1)n2 n(n + 1)(2n + 1)
t= = + .
6 2 6
Si l’équipe Y défait a équipes et perd contre b autres, alors le nombre de triplets ordonnés ayant Y comme composante
centrale est ab. Comme a + b = 2n, on a ab ≤ n2 par l’inégalité des moyennes arithmético-géométriques. D’où u ≤ (2n + 1)n2
et par conséquent
n(n + 1)(2n + 1)
t≤ .
6
Le maximum est atteint quand u = (2n + 1)n2, ce qui peut se produire lorsqu’on arrange touts les équipes en cercle avec
chaque équipe défiant exactement les n équipes dans le sens horaire.
Pn
Commentaire. Le fait que le maximum est i=1 i2 est assez intéressant; exsite-t-il un argument clair qui donne la réponse
sous cette forme?

5. Les sommets d’un triangle rectangle ABC inscrit dans un cercle divisent la circonférence du cercle en trois arcs. L’angle
droit du triangle est en A, alors l’arc opposé BC est un demi-cercle tandis que les arcs AB et AC sont supplémentaires. Pour
chaque arc, on trace une tangente de sorte que son point de tangence est le point milieu du segment de droite défini par les
intersections de la tangente avec l’extension des segments de droite AB et AC. Plus précisement, le point D sur l’arc BC
est le point-milieu du segment de droite D0 D00 où D0 et D00 sont les intersections de la tangente à D avec les droites AB et
AC, respectivement. Pareillement pour le point E sur l’arc AC et pour F sur l’arc AB.
Démontrer que le triangle DEF est équilatérale.

Solution 1. Un prime indique le point d’intersection d’une tangente avec AB et un double prime indique le point où cette
tangente rencontre AC. On sait que DD0 = DD00 , EE 0 = EE 00 et F F 0 = F F 00 . On doit montrer que l’arc EF est le tier de
la circonférence ainsi que l’arc DBF .
AF est la médiane à l’hypothèse du triangle rectangle AF 0 F 00 , de sorte que F F 0 = F A et alors

arc AF = 2∠F 00 F A = 2(∠F F 0 A + ∠F AF 0 ) = 4∠F AF 0 = 4∠F AB = 2 arc BF ,

ainsi arc F A = (2/3) arc BF A. De même, arc AE = (2/3) arc AEC. Par conséquent, arc F E est 2/3 du demi-cercle, ou
1/3 de la circonférence comme demandé.
Tant qu’à l’arc DBF , arc BD = 2∠BAD = ∠BAD + ∠BD0 D = ∠ADD00 = (1/2) arc ACD. Mais, arc BF = (1/2) arc
AF , donc arc DBF = (1/2) arc F AED. Alors, arc DBF est 1/3 de la circonférence et la preuve est complète.

4
 Solution 2. Comme AE 0 E 00 est un triangle rectangle, AE = EE 0 = EE 00 d’où ∠CAE = ∠CE 00 E. De plus, AD = D0 D =
DD00 , donc ∠CDD00 = ∠CAD = ∠CD00 D. Comme EADC est un quadrilatère cyclique,

180◦ = ∠EAD + ∠ECD

= ∠DAC + ∠CAE + ∠ECA + ∠ACD
= ∠DAC + ∠CAE + ∠CEE 00 + ∠CE 00 E + ∠CDD00 + ∠CD00 D
= ∠DAC + ∠CAE + ∠CAE + ∠CAE + ∠CAD + ∠CAD
= 3(∠DAC + ∠DAE) = 3(∠DAE)

Alors ∠DF E = ∠DAE = 60◦ . De même, ∠DEF = 60◦ . Ceci implique que le triangle DEF is équilatérale.