Liste des liens
vers tous les exercices
de ce site
sur les olympiades

Quelques énoncés 2008 particuliers à chaque académie

 Pour l'instant 6 énoncés : Caen 1, Caen 2, Montpellier 1, Montpellier 2, Versailles 1, Versailles 2


Caen 1

A chaque sommet d'un triangle équilatéral de 48m de côté est attaché une chèvre à l'aide d'une corde. Les secteurs angulaires décrits par les chèvres, supposées ponctuelles, ne peuvent se croiser (au plus tangents) et sont intérieurs au triangle.

1) Chaque chèvre a une corde de 24 m de longueur. Quelle est la superficie que les trois chèvres peuvent brouter?

2) Une des trois chèvres a une corde de 32 m de longueur. Quelle est la superficie que les trois chèvres peuvent brouter?

3) Aucune chèvre ne peut avoir une corde plus longue que la distance qui sépare son point d'attache du côté opposé. Déterminer la superficie maximale que les trois chévres peuvent brouter.


-vers une solution-


Caen 2

Les 2 expériences décrites ci-dessous sont indépendantes.

1) A l'intérieur d'un cylindre rempli d'eau, on emboîte parfaitement 3 sphères de telle sorte que la hauteur de l'ensemble des 3 sphères soit égale à la hauteur du cylindre. Ce qui signifie que le rayon des sphères est le même que celui du cylindre.
La quantité d'eau restant à l'intérieur du cylindre peut-elle être de 1 litre?

2) A l'intérieur d'un cylindre rempli d'eau, on emboîte parfaitement une sphère puis un cône de révolution de même rayon que celui du cylindre de telle sorte que la hauteur de l'ensemble cône-sphère soit égale à la hauteur du cylindre. La quantité d'eau restant à l'intérieur du cylindre est de 1 litre.
a) Sachant que le rayon du cylindre est de 5cm, calculer la hauteur du cylindre.
b) Sachant que la hauteur du cylindre est 20cm, déterminer le rayon du cylindre.

    On pourra utiliser les formules suivantes :
  • Volume du cylindre : pR2h
  • Volume du cône de révolution : (1/3)pR2h
  • Volume de la sphère : (4/3)pR3

-vers une solution-


Montpellier 1

On construit une suite de nombres rangés dans un ordre croissant, constitués des seuls chiffres 0, 2 et 8.
Le permier nombre est ainsi 0 qui est de rang 1, le deuxième est 2 qui est de rang 2, le troisième est 8 qui est de rang 3, et ainsi de suite.
Le tableau suivant donne les dix premiers termes de cette suite :
rang12345678910
nombre028202228808288200

1) Quel est le plus grand nombre qui s'écrit avec exactement un 0, un 2, un 8? Préciser son rang.

2) Quel est le rang, en fonction de l'entier naturel non nul n, du nombre qui s'écrit exactement avec n chiffres 8 (et pas d'autre chiffre que 8)?

3) Déterminer le rang du nombre 2008.

4) Comment s'écrit le nombre qui est de rang 2008? Justifier.


-vers une solution-


Montpellier 2

1) Construire un triangle rectangle ABC tel que la hauteur, la bissectrice, la médiane issues de A partagent, dans cet ordre, l'angle de sommet A en quatre angles de mêmes mesures.
Vous préciserez les mesures des trois angles du triangle.

2) Prouvez qu'un triangle ayant un de ses angles partagé en quatre angles de mêmes mesures par la hauteur, la bissectrice et la médiane issues de cet angle, dans cet ordre, est obligatoirement rectangle.

On rappelle les formules suivantes :

  • l'aire du triangle MNP est (1/2)×PN×PM×sin(angle(MPN))
  • sin(2a)=2sinacosa
  • sina=sinb Û a=b+2kp, k dans Z, ou a=p-b+2kp, k dans Z

Ici, je ne donne pas de solution, car cet exercice n'est autre que celui de Dijon (n°2) 2004 (et donc j'ai déjà donné) : plus précisément la question 1 ci-dessus correspond à la remarque que j'avais alors faite, et la question 2 ci-dessus correspond exactement à l'énoncé de Dijon 2004, mais avec une autre aide.


Versailles 1

Soit n un entier naturel strictement supérieur à 1.
On écrit les nombres entiers, de 1 à n, dans l'ordre croissant, puis dans un ordre quelconque. On obtient ainsi deux listes, L1={1 ; 2; ... ; n} et L2={x1 ; x2 ; ... ; xn}.
On calcule ensuite les distances entre 1 et x1, entre 2 et x2, ... , entre n et xn.
Le tableau suivant donne un exemple dans le cas n=5 :

Liste L112345
Liste L242153
Distances30212

1) Dans le cas n=4, puis n=5, donner un exemple de liste L2 telles que toutes les distances soient distinctes deux à deux.

2) On suppose que n=6. Montrer que, quelque soit la liste L2, au moins deux des distances obtenues sont égales.

3) Plus généralement, montrer que s'il existe une liste L2 telle que toutes les distances sont deux à deux distinctes, alors n est un multiple de 4 ou n-1 est un multiple de 4.


-vers une solution-


Versailles 2


Soit n un entier naturel supérieur ou égal à 2.
Un damier carré est divisé en n2 cases carrées de côté 1.
On recouvre certaines de ces cases par des dominos rectangles de largeur 1 et de longueur 2.
Chaque domino recouvre exactement deux cases ayant un côté commun (disposées l'une à côté de l'autre ou l'une sous l'autre).
Aucun domino ne sort du damier et aucune case n'est recouverte par plus d'un domino.
Certaines cases peuvent ne pas être recouvertes, mais il n'est pas possible d'ajouter un domino et aucun des dominos placés ne peut glisser (parallélement à un des côtés du damier) vers une case non recouverte.
Un tel recouvrement est dit rigide
L'objet du roblème est d'étudier le nombre maximal de cases non recouvertes dans le cas d'un recouvrement rigide.

1) On considère un recouvrement rigide du damier de côté n.
a) Prouver qu'il n'y a aucune case non recouverte parmi celles qui forment les bords du damier.
b) Prouver que dans tout sous-damier carré de 2×2 cases, il n'y a pas plus d'une case non recouverte.
c) Prouver que dans tout sous-damier rectangle de 5×2 cases, il n'y a pas plus de deux cases non recouvertes.

2) Donner un exemple de recouvrement rigide du damier carré 7×7 où 5 cases ne sont pas recouvertes.

3) Prouver que dans un recouvrement rigide du damier n×n, il n'y a pas plus de n(n+5)/5 cases non recouvertes.

4) Prouver que, pour tout n supérieur ou égal à 7, on peut trouver un recouvrement rigide avec au moins (n-6)2/5 cases non recouvertes.
Si un élève a trouvé cette question le jour de l'épreuve, qu'on me le dise!

5) On note f(n) le plus grand nombre de cases non recouvertes dans un recouvrement rigide n×n. Vers quelle limite tend f(n)/n2?


-vers une solution-


Fin des énoncés

Les solutions

Solution Caen 1

L'aire d'un secteur angulaire de rayon r et d'angle q (en radians) est qr2/2 (puisque cette aire est proportionnelle à l'angle, et que dans le cas d'un angle de p radians, cette aire est pr2/2).

1) Dans ce cas, les trois secteurs sont tangents deux à deux et la superficie broutée est 3×(p/3)×242/2=288p@904,778 m2.

2) La superficie que peuvent brouter les trois chèvres est en fait la superficie maximale qu'elles peuvent prouver, et cette superficie est obtenue lorsque les deux autres chèvres broutent un secteur tangent à celui de la chèvre ayant une corde de 32 m : ces deux autres secteurs auront donc 48-32=16 pour rayon et comme 16+16£48 ils ne se recouvriront pas entre eux.
Cette superficie broutée est donc (p/3)×322/2+2×(p/3)162/2=256p@804,247 m2.

3) Soit L la longueur de la corde d'une chèvre : pour cette longueur L, la superficie maximale que peuvent prouver les trois chèvres, est obtenue lorsque les deux autres chèvres broutent un secteur tangent à celui de la chèvre ayant une corde de L m.
Cette aire est A(L)=(p/3)×L2/2+2×(p/3)(48-L)2/2=(p/2)(L2-64L+1536)=(p/2)((L-32)2+512) m2.
Bien entendu, la formule donnée ci-dessus pour A(L) n'est valable que si le secteur de rayon L reste intérieur au triangle, ce qui correspond à l'hypothèse "aucune chèvre ne peut avoir une corde plus longue que la distance qui sépare son point d'attache du côté opposé" ; donc L doit être inférieur ou égal à la hauteur du triangle (équilatéral de côté 48) qui est 48Ö3/2, ce qui donne L£24Ö3=h.
Mais il doit en être de même pour les deux autres secteurs de rayon 48-L, ce qui donne 48-L£h, soit 48-h£L ; en outre ces deux secteurs ne doivent pas se recouvrir, donc il faut aussi que 2×(48-L)£48, soit 24£L.
Comme 48-h<24, ces trois conditions se résument par 24£L£h.

Il s'agit donc de trouver la valeur maximale de A(L)=(p/2)((L-32)2+512), sachant que 24£L£h.
On remarquera que si L=24 on retrouve Q1, et si L=32, on retrouve Q2.
Notons aussi que cette écriture sous forme canonique de A(L) montre tout de suite que sa valeur minimale est obtenue pour L=32 (question Q2), puisque A(L)³(p/2)(512)=A(32).
La valeur maximale de A(L) correspond évidemment à (L-32)2=|L-32|2 maximum, donc à |L-32|=d(L,32) maximum (attention : la fonction x->x2 n'est pas croissante sur R : elle est croissante que sur R+, cad deux nombres positifs sont rangés dans le même ordre que leurs carrés).

La plus grande valeur de A(L) est donc obtenue lorsque L=h, et alors |L-32|=h-32 : la superficie maximum broutée par les trois chèvres est A(h)=(p/2)((24Ö3-32)2+512)=96(17-8Ö3)p@948,085 m2.

-retour énoncé-


Solution Caen 2

1) Notons H la hauteur du cylindre, R son rayon, qui est aussi le rayon des 3 sphères.
On a donc H=6R.
Le volume d'eau restant est Vr=pR2H-3×(4/3)pR3=2pR3.
Si H et R sont en cm, ce volume est en cm3 ; comme 1 litre c'est 1000 cm3, la question est de savoir si on peut avoir 2pR3=1000, soit R3=500/p.
A ce niveau, je rappelle qu'en 1ière S on ne connaît pas encore les racines nièmes.
La fonction x->f(x)=x3-500/p est dérivable sur [0;6], est strictement croissante sur cet intervalle, f(0)<0, f(6)>0, donc elle s'annule, une seule fois, sur cet intervalle, c'est-à-dire il existe un unique R entre 0 et 6cm tel que f(R)=0, donc tel que le volume Vr restant d'eau soit égal à 1000cm3=1 litre.

2) Notons H la hauteur du cylindre, R son rayon qui est celui de la sphère et du cône, la hauteur de ce dernier étant h.
On a donc H=2R+h.
Le volume d'eau restant est Vr=pR2H-(4/3)pR3-(1/3)pR2h=pR2(H-4R/3-h/3)=2pR2(H-R)/3.
Note : puisque H=2R+h, c'est que H>2R, ainsi Vr est bien positif.
Par hypothèse Vr=1000 cm3, et donc R2(H-R)=1500/p (H et R étant en cm).

a) Si R=5cm, 25(H-5)=1500/p et donc H=60/p+5@24,098 cm.

b) Si H=20cm, R2(20-R)=1500/p Û R3-20R2+1500/p=0.
R est donc solution d'une équation du 3ième degré, avec la condition 0<R<H/2=10!
Je ne vois pas comment on peut déterminer R, car tout de même, déterminer R (voir énoncé) sous-entend trouver la valeur exacte de R, ce qui me semble impossible, même pour quelqu'un dont le bagage mathématique est plus important qu'un élève de 1ière S (la méthode de Cardan est ici illusoire, surtout qu'en plus les coefficients de cette équation ne sont pas rationnels).
Tout au plus, on peut déterminer une valeur approchée de R, qui est, rappelons le à chercher entre 0 et 10 :
la fonction x->f(x)=x3-20x2+1500/p est dérivable, strictement décroissante sur [0;10], puisque f '(x)=x(3x-40), et f(0)>0, f(10)<0 : f s'annule, une seule fois, sur cet intervalle, c'est-à-dire il existe un seul R entre 0 et 10 tel que f(R)=0.
Par encadrements successifs (dichotomie par exemple), on trouve que R@5,7983 cm.
Note : l'équation du 3ième degré ci-dessus a en fait deux autres solutions réelles, approximativement -4,42 et 18,62, valeurs qui sont bien en dehors de [0;10].

-retour énoncé-


Solution Montpellier 1

1) Ecrivons les termes de cette suite, par lignes de 3 :

028
202228
808288
200202208
220222228
280282288
800802808
820822828
880882888
200020022008
202020222028
Donc, 820 (le plus grand nombre de cette suite avec exactement un 0, un 2, et un 8) a pour rang 22

Avant de "s'attaquer" véritablement aux autres questions, si on observe ce tableau, on remarque que pour obtenir tous les nombres de n+1 chiffres (n³1), il suffit de prendre tous ceux ayant au plus n chiffres (et, parmi eux, pour ceux ayant moins de n chiffres, de rajouter devant des 0 pour obtenir exactement n chiffres) et de mettre au début soit 2, soit 8 ; ce qui se traduit, en notant un le nombre des nombres de la suite ayant exactement n chiffres, par un+1=2(u1+u2+...+un).
Donc un+2=2(u1+u2+...+un+1)=2(u1+u2+...+un)+2un+1=3un+1, cela pour n³1 : finalement un+1=3un pour n³2, c'est-à-dire la suite (u) est géométrique à partir du rang 2, et donc pour n³2, un=2×3n-1 (cf cours, un=u2×3n-2=6×3n-2), et pour n³1 on a u1+u2+...+un=3n (puisque c'est un+1/2).
Par exemple, u2=6, u3=18, u4=54, u5=162 ; par contre u1=3 n'est pas égal à 2×30=2.

Remarque 1 : autre façon de montrer que la suite (u) est géométrique à partir du rang 2.
Les un+1 nombres de la suite ayant n+1 chiffres se répartissent en trois catégories :

Si aux kn nombres se terminant par 0, on ôte ce 0, on obtient évidemment kn nombres de la suite ayant exactement n chiffres, et en fait on obtient tous les nombres à n chiffres de la suite ; en effet si a est un nombre à n chffres de la suite, comme n³2, ce nombre ne peut commencer par 0 et alors "a0" (le nombre obtenu en ajoutant 0 à la fin de l'écriture décimale de a) est un nombre de la suite avec exactement n+1 chiffres, et se terminant par 0 : il fait donc partie des kn nombres ci-dessus.
Donc kn=un, de même k'n=un, k''n=un, et ainsi un+1=3un, pour n³2 : on retrouve bien que la suite (u) est géométrique à partir du rang 2.

Remarque 2 : vérifions, à partir du fait que pour n³2 on a un=2×3n-1, que pour n³1 on a un+1=2(u1+u2+...+un) :

Rappel : pour q¹1, 1+q+q2+...+qm=(1-qm+1)/(1-q).

2) Le nombre de la suite s'écrivant avec exactement n(³1) chiffres 8 est le plus grand nombre de cette suite avec n chiffres : son rang est donc u1+...+un=un+1/2=3n.

3) Après 888, il y a 2000, 2002, 2008, donc 2008 a pour rang 33+3=30.

4) 36<2008<37=2187.
2187 étant le rang de 8888888, pour trouver le nombre dont le rang est 2008, il faut donc "reculer" de 179 nombres (de 2008, compris, à 2187, compris, il y a 2187-2008+1=180 nombres) :

Le nombre de la suite dont le rang est 2008 est 8808200

-retour énoncé-


Solution Versailles 1

1) Par commodité, je dirai qu'une liste L2 est solution si pour cette liste, les n distances sont distinctes deux à deux.

Quelques remarques préliminaires simples :

Essayons de voir ce que donne x1=n et xn=2 pour n=4 et n=5.

2) Bien entendu, il s'agit de donner ici une explication qui ne consiste pas à faire la preuve de la question 3) dans le cas n=6, ni à examiner les 6×5×4×3×2×1=720 listes L2 possibles!!

Mais la preuve de la question 3 étant tellement simple, on peut tout à fait "zapper" ce qui suit pour aller directement à la solution de la question 3! D'ailleurs je me demande ce qu'ont fait les correcteurs dans le cas où un candidat ayant réussi à prouver la question 3, se contente de l'appliquer pour traiter la 2ième question!

Cf les remarques préliminaires de la question 1), nécessairement, si une liste L2 est solution alors x1=6 ou x6=1.
En fait, il suffit de montrer qu'il n'y a pas de liste L2 solution pour x1=6, car alors obligatoirement il en sera de même pour x6=1 : en effet s'il existe une solution pour x6=1, alors son "inverse", pour laquelle x1=6, est aussi solution (puisque les distances obtenues pour ces deux listes sont les mêmes : voir question précédente pour l'illustration de solutions "inverses" dans les cas n=4 et 5).
On va donc montrer que si x6=1, toutes les listes L2 pour lesquelles il y a les distances 5, 4, 3, 2, 0, il ne peut y avoir la distance 1 : ceci prouvera que toute liste L2 avec x6=1 ne peut être solution, et, cf ce qui vient d'être dit il en sera de même pour les listes L2 avec x6=1 et donc aucune liste L2 ne peut être solution (et ainsi, évidemment, toute liste L2 posséde au moins deux distances égales).
Ces listes se répartissent en quatre catégories, selon le i donnant la distance 0 (xi=i), ce i ne pouvant être que 2 ou 3 ou 4 ou 5, puisque x1=6.

3) Cette fois, pas de souci : ca va être beaucoup plus rapide, c'est même presque instantané ... à condition d'avoir l'idée!

Si L2 est une solution, la somme des n distances obtenues est S=0+1+2+ ... + (n-1)=(n-1)n/2 (cf cours sur progression arithmétique).

Chacune de ces n distances est d(i,xi), pour i décrivant {1 ; 2 ; ... ; n}


Bien sûr S=S1+S2, mais S1-S2 est en fait la somme de tous les i-xi, soit 1+2+...+n-(x1+x2+...+xn)=0.
Et donc S1=S2, soit S=2S1 et ainsi S est un entier pair.
Donc si L2 est solution, nécessairement (n-1)n/2 est pair, cad (n-1)n/2=2k avec k entier naturel, soit (n-1)n=4k, cad (n-1)n doit être un multiple de 4 ; mais n-1 et n sont deux entiers consécutifs, donc un seul d'entre eux est pair : Finalement, L2 est solution entraîne que (n-1)n/2 est pair, cad n multiple de 4 ou n-1 multiple de 4.

Bien entendu, ce n'est pas le cas de n=6, ce qui redonne (rapidement cette fois!) que pour n=6, il n'y ait aucune liste L2 qui soit solution!

Remarques/compléments post-1ère S :
1) Un élève de Terminale scientifique (option arithmétique) aurait pu justifier ce dernier aspect ainsi : modulo 4, il n'y a que quatre possibiltés pour n : 0, 1, 2, 3, et seules les deux premières donnent n(n-1)/2 égal à 0 modulo 4.

2) La liste L2 est ce qu'on appelle une permutation de l'ensemble E={1 ;2 ; ...; n} : c'est en fait le résultat d'une application s (appelé aussi permutation) de E dans E :

par exemple, pour n=4, et L2=(4,3,1,2), s est l'application de E dans E définie par :
En fait s(i) est le xi de l'énoncé.

L'ensemble Sn de toutes les n! applications s de E dans E est un ensemble bien connu ; chacune de ces application est une bijection de E dans E, et muni de la loi de composition habituelle des applications, Sn a une structure particulière : c'est un groupe.
On connaît des "tas" de propriétés de ce groupe, et en connaissant quelques unes (pas toutes bien sûr), j'ai essayé de voir si cela pouvait être utile pour la dernière question, mais en fait il n'en n'est rien : ca m'a plutôt fait perdre du temps!

Dire qu'une liste L2 (correspondant à la permutation s) est solution signifie alors que les n distances d(s(i),i)=|s(i)-i| sont distinctes deux à deux : on dira que s est solution.

On peut alors préciser ce que j'ai appelé plus haut, solution inverse : si s est solution, l'application réciproque s-1 est aussi solution :

on sait que les d(s(i),i) sont distincts deux à deux lorsque i décrit E, et il faut montrer qu'il en est de même pour les d(s-1(i),i) ; or lorsque les i décrivent E, il en est de même pour les s-1(i), donc les d(s(s-1(i)),s-1(i)) sont distincts deux à deux et comme d(s(s-1(i)),s-1(i))=d(i,s-1(i))=d(s-1(i),i), les d(s-1(i),i) sont bien distincts deux à deux.

Mais si s et s' sont solutions, sos' ou s'os ne sont pas forcément solution.
Un premier exemple : si s est solution, on vient de voir que s-1 est aussi solution, mais sos-1 est la permutation identique ( tout i est transformé en i), donc toutes les distances sont égales à 0, et donc sos-1 n'est pas solution.
Autres exemples (n=4) :

i1234
s(i)4132
Distances3102

i1234
s'(i)4213
Distances3021

i1234
sos'(i)2143
Distances1111

i1234
s'os(i)3412
Distances2222

J'ai aussi remarqué que les solutions trouvées pour n=4 ou n=5, sont des p-cycles :
pour n=4

le s ci-dessus est (1 4 2)o(3) et le s' ci-dessus est (1 4 3)o(2), donc ce sont des 3-cycles. pour n=5 les deux s trouvés (voir question 1) sont (1 5 2 3)o(4) et son inverse ou (réciproque) (1 3 2 5)o(4), donc ce sont des 4-cycles Bien sûr, de là dire que toute permutation solution est un p-cycle est un pas que je ne franchirai pas.
Cependant la décomposition en p-cycles d'une permutation solution ne peut contenir un 2-cycle, car un 2-cycle conduit à deux distances égales ; ce qui prouve que toute solution pour n=4 est forcément un 3-cycle, et pour n=5 c'est forcément un 4-cycle (puisque par ailleurs une solution a un seul point fixe).

-retour énoncé-


Solution Versailles 2

Pour faciliter la lecture des schémas, tout domino horizontal sera coloré en gris, tout domino vertical sera coloré en noir, et toute case non recouverte par un domino sera colorée en jaune.
Et pour me faciliter la tâche, j'utiliserai l'abréviation cr pour une case recouverte, cnr pour une case non recouverte.

1 a) Supposons, pour fixer les idées qu'il existe une cnr sur le bord du damier, par exemple le bord haut :

Il n'y a donc pas de cnr sur les bords du damier.

1 b) Dans un sous-damier 2×2 il ne peut y avoir 3 ou 4 cnr, car on pourrait rajouter un domino ;
mais il ne peut y avoir non plus uniquement 2 cnr, car

Donc dans un sous-damier 2×2 posséde au plus une cnr. En fait si n=2, le damier 2×2 ne contient aucune cnr (cf le a).

Une conséquence est que deux cnr ne peuvent avoir un sommet commun (puisqu'elles sont alors obligatoirement dans un sous-damier 2×2).

Note : l'impression de la qestion 1 c) commencera au début de la page suivante.

1 c) Il me semble capital, maintenant, de remarquer que toute case non recouverte est obligatoirement dans un sous-damier 3×3 du type suivant :

Type 1

               
                
             

ou
Type 2

               
                
             

( on passe du Type 1 au Type 2 par une symétrie axiale)

En effet,

On retrouve le fait que deux cnr ne peuvent avoir un sommet en commun (puisque "autour" d'une cnr il n'y a que des cr).

On en déduit que sur une même ligne ou une même colonne, deux cnr ne peuvent être séparées par une seule cr.

En effet, supposons que sur une même ligne (par exemple) on ait deux cnr séparées par une seule cr.
Alors, cette cr appartient forcément à un domino vertical qui recouvre une autre case cr' qui est soit, au dessus, soit au dessous de cette cr. Pour fixer les idées supposons que cr' soit au dessus de cr (voir figure ci-dessous) : la cnr de gauche est donc au centre d'un damier 3×3 de Type 1 et la cnr de droite est au centre d'un damier 3×3 de Type 2 et donc la case située sous la cr entre les deux cnr est recouverte par deux dominos, ce qui est interdit.

                          
                             
                          

Venons-en maintenant à la question 1c) proprement dite.
Tout d'abord, remarquons, que dans un damier 5×2 (pour fixer les idées on supposera qu'il est constitué de 5 colonnes, toutes avec deux cases) il y a au plus 3 cnr (car on peut le décomposer en 2 sous-damier 2×2, qui contiennent chacun au plus 1 cnr, et la colonne restante contient elle aussi, au plus 1 cnr (sinon on peut rajouter un domino)).
Et bien sûr, 2 de ces cnr ne peuvent être sur une même colonne (sinon, on peut rajouter un domino).
Supposons que ce damier 5×2 ait effectivement 3 cnr : elles sont sur 3 colonnes distinctes et non contigües (sinon un carré 2×2 aurait deux cnr).
Il y a alors trois configurations possibles (à des symétries près), les cases recouvertes étant en vert (puisqu'on ne sait pas à priori par quel type de domino, horizontal ou vertical, elles sont recouvertes) :

cas 1

                          
                            

cas 2

                          
                            

cas 3

                          
                            
Donc dans un sous-damier 5×2, il ne peut y avoir 3 cnr, donc il y a au plus 2 cnr.

2)

Voici un exemple de carré 7*7 muni d'un recouvrement rigide avec 5 cnr (je suis parti du sous-damier 3×3 de Type 2 défini au début de la solution de 3c) et j'ai essayé d'en mettre 5 :

                                         
                                         
                                         
                                         
                                         
                                         
                                         

3) Pour arriver au résultat, on va décomposer le damier n×n en sous-damiers 5×2 :

On peut donc mettre KK' sous-damiers 5×2 dans le damier n×n : A droite des KK' sous-damiers 5×2 il y a r colonnes (aucune si r=0, notées C1, ...,Cr sinon) avec n-r' cases, et dessous "le tout", il y a rien si r'=0, et si r'=1, il y a une ligne (notée L1) de n cases.
Je conseille au lecteur de faire la figure correspondante, pour pouvoir suivre facilement le petit calcul suivant majorant le nombre de cnr du damier n×n.

Les KK' sous-damiers 5×2 apportent toujours au plus 2KK' cnr (cf la question 1c).

Donc on a toujours au plus n(n+5)/5 cnr dans un damier n×n muni d'un recouvrement rigide.

4) En anticipant le résultat de la question suivante, à savoir que f(n)/n2 tend vers 1/5 (puisque les questions 3 et 4 donnent un encadrement de f(n)), c'est que, pour n grand, f(n) doit étre voisin de n2/5, c'est-à-dire dans un damier n×n muni d'un recouvrement rigide, pour n grand, on a environ 20% de cases qui sont des cnr!
C'est loin d'être le cas du damier 7×7 de la question 2 où il n'y a que 5 cnr soit environ 10% de cnr, mais 7 n'est pas "grand".
Avoir 20% de cnr, signifie "qu'en moyenne" pour 5 cases on a 1 cnr : on va voir qu'il est possible de mettre sur un "grand damier" , sur chaque ligne (et même sur chaque colonne) 1 cnr, puis 4 cr, puis 1cnr, puis 4cr, etc!
La difficulté, c'est que pour prouver cela, les questions précédentes ne sont pas d'une grande utilité!

La figure ci-dessous est un damier 15×15 qui n'est pas...muni d'un recouvrement rigide, puisque sur les bords il y a des cnr et des moitiés de dominos verticaux!

En fait il s'agit du "début" d'un pavage du plan (il y a toute une théorie sur le pavage du plan).

                                                                                
                                                                                  
                                                                   
                                                                    
                                                                          
                                                                          
                                                                          
                                                                          
                                                                          
                                                                          
                                                                          
                                                                          
                                                                          
                                                                          
                                                                          

Ce pavage du plan est obtenu par translation selon deux directions différentes du motif suivant constitué en fait de 5 cases :

                 
                 

Remarque : je laisse le lecteur trouver les deux translations évoquées ci-dessus.

On constate que sur chaque ligne et chaque colonne de ce pavage du plan, on a 1 cnr puis 4 cr puis 1 cnr puis 4cr ...

Mais si on "plaque" sur ce pavage infini du plan un damier n×n, on obtient certes un recouvrement du damier n×n, mais ce n'est pas un recouvrement rigide du dit damier, cela pour 3 raisons :

Montrons comment ce recouvrement non rigide (et noté RNR) peut être transformé en un recouvrement rigide.

Réglons d'abord les deux premiers problèmes :

Reste le 3ième problème.
En procédant ainsi, on obtient un recouvrement rigide du damier n×n (on a "perdu" uniquement les cnr du RNR qui étaient sur les bords et éventuellement 4 cnr intérieures).
Essayons de comptabiliser son nombre de cnr, ou plus exactement de le minorer, lorsque n³7.
Pour chacune des n-6 lignes différentes des bords bas et haut, des 2ième, 3ième, n-2ième, n-1ième lignes (il y en a au moins une, puisque n³7), notons k le nombre de ses cnr : à gauche de la 1ière cnr on a x cases remplies (la case du bord gauche étant exclue), et à droite de la dernière cnr on y cases remplies (la case du bord droit étant exclue) : x+y+5(k-1)+1=n-2.
Mais, compte-tenu de la propriété des lignes du pavage du plan, on a x et y£4, d'où n-2£9+5(k-1), soit k³(n-6)/5, et ainsi le nombre de cnr de ce damier n×n est supérieur ou égal à (n-6)(n-6)/5.
Remarque : on pourrait augmenter ce minorant en comptabilisant les cnr de chacune des 2ième, 3ième, n-2ième, n-1ième lignes, chacune d'entre elles ayant au moins (n-6)/5-1 cnr ; mais cela n'a pas d'incidence sur le résultat de la question suivante.

Donc on peut trouver un recouvrement rigide d'un damier n×n avec au moins (n-6)2/5 cnr.
Cette minoration n'a d'intérêt que si n est "grand" : pour n=7 on obtient 1/5 comme minorant du nombre de cnr, alors qu'en fait dans ce cas il existe un recouvrement rigide avec 5 cnr (question 2).

5) Et arrive la question la plus facile...
En effet, les questions 3 et 4 permettent d'écrire tout de suite :
pour n³7, (n-6)2/5£f(n)£n(n+5)/5, donc (1-6/n)2/5£f(n)/n2£(1+5/n)/5.
Lorsque n tend vers +¥, les membres de gauche et de droite de cette double inégalité tendent vers 1/5, et le théorème des sandwichs (ou des gendarmes ou de l'encadrement...) permet de dire que la limite de f(n)/n2 lorsque n tend vers +¥ est 1/5.

-retour énoncé-


Fin des solutions

présentation olympiades