aes méegcamatuH 142 exercices pe Haut vol préface De JoHaN yeBBou exercices » collection « galaxies p vurnentmégamatuH 142 exercices pe Haut vol PIeRRe BORNSzteIN agnége pe matuémaugues, professeun au Lycée jules vere, ceRgy preface be jonian yenvoucuez Le méme épiteur : Jean Plere Mauss Ue hire del physique sons les éuotions, ‘lure par Marianne Maury. aurann240 pages Jean-Marc LoveLsaono, La physique en questions. Mécanique, dessins @Yven Gutzou, M44 pager André Burou & Jean-Marc LeveLstenn. Lo physique en questions Eectrcié et megntie, dessins Yves Guézou, 144 pages ene Brey La symérie dns tous sess, préfice &'Alin Connes, 4B pages René Desconees Ler cores miqus. Histo, Udo et tecique du evr moi, de Tuite ux ecerchesactles, 96 pages ‘Albert Ducroce & André Waruset, Mathimatgques pla & nest, 416 pages Giles Pacts 8 Claude Bout, avec Fabrice CaMance & Frédérque PFI, En pessnt par hard Jean-Pierre Bounnt La géomézie del chambre & dessins "Yves Gulaou, 192 pages Homo mathemati Ls madidmatgues et nous. 208 pages Isean Bens La pique de tous es jours, dessins Yves Guézou 452 pages alec sour la direction de H-D Francis, les nombres eur histor, er place eer rl de Aetiquité cur recherches ctl, 464 pages tract et adagt ce fllemand par Frangots Gutrara ‘Alexandre Denes, Gries lqus, niger mathématique.. ors es mats, 128 pages Here Bem, Copuarismes,pophes et autres énigmes mathimotiues, 144 pages folndiames;monoyes autres bere nunanques, 144 pager Jee rameiqus & moggues dors lo wostme densi, 76 pages ‘André Sanee-Lactr Avec des nantes et des es. Réréotors mahimocaques, 384 pages. Reampression de 'éduon de 1937 sugmentée dune Gude indie André Deledicg fede Claude Berge Eile Fours, Cuts gomviques, 48 pages. impression de edon de 1907 agmentée dune étude inéte @Evelme Barkin —Recréatiorsonthretiges, 268 pages. Réimpression de ediuon de 1899 ugmentée dune étude née de Jean-Louis Nicolas Ithatration de couverture: nébuleuse du crabe ‘© ESO (European Souther Observatory) ‘Compostion et mise en page: Antoine Vélu sous TEX tsen 27117 s3005 ks 1 oars 1957 wernt ccm 2 3 Farina pr, a capes repre ‘car ser ree isoge pn d coe e eras 6 wate aes ees ar gu es “ropes rk ore tars rut ft ese et anon = ot retrace ren ele, fer fo ne cnr go gts er ce cn a dee ‘ltr au rpc po une Poe gure crs doe ue cefeen srcnee far igewieneenies <—— {es psocpege et ope ef col dela pancape sons att ds ers esr Legere are brent eretrmet es pcos reece overdo carl een Sng Spee agen eso eae ete Betphoccoe opr peer Se als ove ard de tar, ‘Seaano Cot Fant desta du tcp 20 reds Crd opie, F7S006 Pa T0144 07 47 70 © Libro bert itt 2001-20 re Berber Mets, 75647 Pris cedex 13, [Link]sommarre avant pRopos 1v préface v Notations et Rappels vit quel gues Bases eN tHEORIE Des GRAPHES VI RalsONNemeNnt énoncés 1 conrigés 35 algépre énoncés 16 connigés 143 analyse énoncés 29 connigés 228avaNt-PROPpOS Ce livre se veut étre un recueil de beaux exercices d'algebre, d'analyse et de raisonnement (vaste domaine, qui recouvre combinatoire, probabilités, théorie des graphes...). Un second tome regroupera des exercices d'arithmétique et de géométrie. Pour la plupart, ils sont issus de diverses compétitions qui ont lieu de par le monde et les énonoés sont ceux qui ont été proposés aux candidats ou au jury (le formidable journal canadien Crux Mathematicorum en est une source intariss- able) ‘Toutefois, certains ont &é modifiés afin d'étudier le probleme dans sa généralité (par exemple, l'exercice RS ne proposait que le a., tout comme le AI19 ou le Al45). Mais qu’est-ce qu'un bel exercice ? Pour moi, c'est rout d'abord tun énoncé qui donne envie de chercher, par son élégance ou pour le résultat surprenant qu'il annonce. De ce point de vue, les énoncés d'olympiades et compétitions sont redoutables, mais. gar qu'une solution relativement abordable existe. tissent Ensuite, c'est une solution qui ne dégoit pas. La maitrise des outils utilisés, méme si elle est nécessaire, ne doit pas étre une fin en soi. Crest ce qui différencie les exercices de ce livre de la plupart des exercices plus scolaires. Ici, il faut avoir également de l'astuce et de 'intuition. Bref ! faire preuve de créativité. Ce livre s'adresse donc a ceux qui savent «ue sécher sur un probleme, parfois longtemps, ne fait qu'augmenter le plaisir de trouver enfin une solution. Enfin, c'est un exercice qui donne envie d'aller plus loin. Certains énoncés sont des portes ouvertes vers des domaines mathématiques plus généraux (la géométrie combinatoire, par exemple), d'autres peuvent se généraliser ou sont des cas particuliers de théorémes. Lorsque cela ne dépassait pas le niveau prérequis et dans la mesure de mes connaissances, les solutions présentées donnent directement des généralisations possibles et/ou indiquent l'état des recherches sur Ie sujet. Envie, plaisir... un bean programme, non ? Pierre BORNSZTEINpréface Voici un livre qui plaira A tous les amoureux des mathématiques, tous ceux, sans doute plus nombreux qu'on ne le croit, désireux de stattaquer a des exercices difficiles, attrayants par leur élégance et leur implicité, mais dont les solutions nécessitent créativité et rénacité. Picrre Bornsztein a fait un beau travail en rassemblant de nombreux énoncés classés par théme et en rédigeant des solutions approfondies. Les problémes, dont lauteur indique la provenance, sont tirés de ‘compétitions mathématiques diverses, dans l'esprit des Olympiades in- ternationales. Ces exercices sont subtils: il fandra prendre le temps de tatonner, dexpérimenter; voir pourquoi telle situation est impossible et pourquoi telle autre est nécessaire; conjecturer un résultat plausible, en chercher la démonstration ou en trouver un contre-exemple ; voir les idées judicieuses, les organiser en une ébauche de solution avant de passer a une rédaction précise. Bref, il faudra prendre des initiatives, faire preuve d'imagination et ne pas ménager sa peine. “Malgré ses efforts, le lecteur devra, sans démériter, se reporter parf a la solution. Dans certains cas, il se contentera de prendre une idée lui permettant de poursuivre sa recherche personnelle dans d'autres cas, il étudiera la solution détaillée que Ini propose Pierre Bornsztein ; parfois peut-étre, il sera capable de trouver un autre chemin, une autre solution. Quoi qu'il en soit, il éprouvera le plaisir de la recherche et de la découverte sil verra les mathématiques & Macuvre sur des ques- tions stimulantes, subitement éclairées par un argument délicat ou une demonstration limpide. Les candidats au Concours général ou aux Olympiades internationales trouveront bien sir ici d'excellents exercices d'entrainement. Cepen- dant, le public auquel s'adresse cet ouvrage est beaucoup plus large. Les élaves des lyeées et les étudiants qui aiment les mathématiques découvriront avec intérét et peur-étre avec surprise ces exercices si différents de ccux auxquels ils sont habitués : soyons sis qu'il ne le regretteront pas. Mais ce livre s'adresse aussi a leurs professeu ceux-ci pourront élaborer de beaux énoneés en choisissant un exer ice et en y ajoutant des questions intermédiaires de fagon 4 obtenir probleme plus accessible. Visant & démontrer un résultat non évident,de tels énoneés éveilleront certainement la curiosité des éléves et leur donneront matiére 4 réflexion. Il faut d'autre part remercier Pierre Bornsztein de ne pas s'étre arrété & donner la solution des exercices quiil propose ; au contraire, il indique des prolongements possibles et fournit des références utiles & ceux qui voudraient aller plus loin, I mentionne également des problémes restés ouverts et montre ainsi que les mathématiques, méme si on se limite aux notions élémentaires enseignées au lycée, sont une si en mouvement, bien loin de "image figée que certains peuvent parfois vivante, Je souhaite que ce livre rencontre Ie large public qu'il mérite et qu'il ‘contribue diffuser lidée que, & quelque niveau que ce soit, Vactivité de recherche mathématique récompense amplement les efforts qu'on Ini consacre. Johan Yennou* * Johan Vebbon est professeur en classe préparatoire MP au lycée Charlemagne (Paris) et préparateur de Uéquipe de France aux Olympiades internationales de mathématiques.Notations UtILIsées Dans Les soLUtIONS ‘© Un produit indexé sur ¢ est égal & 1. Une somme indexée sur pest Gale 4 0. # Les mots positif, inférieur, intérieur, convexe sont 4 prendre au sens strict. # Liaire d'une figure F est notée [F]. Le pged des entiers a et b est noté a/b. La partic entiére d'un réel x est notée [x] RappeLs géNéRraux «La suite (H,) définie par Hy =) fest stictement croissante et diverge vers +00. * Le principe des tiroirs : Soit mk des entiers positifs. Si mk + 1 objets sont rangés dans » tiroirs alors il existe un tiroir qui contient au moins k+1 objets. « L'inggalité arithmeético-géométrique (IAG): Soient € N* et 1,82, .-+%q des réels positifs ou nuls. Alors: xp tet Ry i L'ggalité ayant lieu si et seulement six) = 22 =... = n+ alité de Cauchy-Schwarz: Soient 1m € N° et 44,25 --.5dny 1s Bas .-++by des réels, Alors : (ayby + ayba+..+ aby)? < (dh +a +...02)(b; bh +... +62) avec égalité si ex seulement si les vecteurs (a), 42, +.+d,) et (bs, Ba, --- by) sont colinéaires. Rappels importants en algépre et analyse inorée) admet une + Toute partie de R non vide et majorée (resp. borne supérieure (resp. inférieure) # Soient a, b des réels. Sif : [a, b] — Rest monotone alors elle admet tune limite a droite et une limite gauche en tout point de Ja, bf. # Liensemble @ des nombres rationnels est dense dans R. + Sip est un nombre premier, l'ensemble Z/pZ est un corps. # Le théoréme de Rolle: Soit f : [a,b] —> I continue sur [a, b] et dérivable sur Ja, bl. Si fla) = f(b) alors il existe ¢ € Ja, b{ tel que f'(c) = 0.gueLgues Bases eN tHéorIe Des GRaPHES Ce qui suit a surtout pour objet de donner quelques définitions naives de la théorie des graphes et de dégager quelques résultats fondamentaux. On ne se formalisera done pas de la rigueur sans doute insuffisante de exposé. Un graphe est, d'une part un ensemble (fini, pour nous) d'objets ap pelés sommets, et d'autre part un ensemble d'arétes dont chacune relic une paire de sommets. I arrive souvent que l'on représente les sommets par des points et les arétes par des ares de courbes, emplacement des points les uns par rapport aux autres et le fait que les courbes s'intersectent ou non est a priori sans importance. En par- ticulies, les points d’intersections des courbes ne sont pas des sommets supplémentai Dans tout le livre, les graphes n‘auront jamais d'arétes multiples (on relie plusieurs fois une méme paire de sommets), ni de boucles (une aréte dont les extrémités sont confondues). Le degré d'un sommet est le nombre d'arétes dont il est une extrémité. Si chaque paire de points est reliée par une aréte, on dit que le graphe cst complet Les arétes forment parfois des chemins qui permettent de «passer» de certains sommets & d'autres. Les sommets peuvent se répartir selon des groupes appelés com- posantes connexes, deux sommets appartenant 2 une méme com- posante si ct sculement s'il existe un chemin pour passer de l'un & autre (un point est toujours considéré comme relié a Tui-méme). Tl est alors assez facile de prouver que deux composantes connexes dis- tinctes sont disjointes. Sie graphe n'a qu'une seule composante, on dit quil est connexe. Enfin, un cycle d’ordre mn est un ensemble de > 3 sommets distinets Py,..-yPy tels que PiPjq1 soit une aréte pour tout i (avec Pysa = Pi)-RaISONNemeNt €NONCES ‘Vingt enfants attendent leurs grands-péres dans la cour de la mater nelle. Deux enfants quelconques ont un grand-pere commun, Prouver {qu'un des grands-péres a au moins 14 petits-enfants dans cette mater nelle (Moldavie 1996) Soient ¢, € deux entiers supéricurs ou égaux A 2. On considére un ‘quadrillage rectangulaire de c colonnes et€ lignes. La figure ci-dessous représente le cas ¢= 4 et € Déterminer le nombre minimum R(c,£) de rectangles nécessaires pour que on puisse recouvrir chaque aréte et chaque sommet du quadrillage. La figure ci-dessous montre que R(4, 3) < 3. (On a écrit 100 nombres autour d'un cercle. Leur somme est 100. La somme de 6 nombres consécutifs quelconques ne dépasse pas 6. Si'un de ces nombres est 6, quels sont Jes autres ? (Lituanie 1995) rawonnement (évocis) , RI R2 R3R4 RS éyonse pa) R6 R7 R8 On trace un polygone convexe 4 1996 cétés de fagon que trois diago- nales quelconques ne soient jamais concourantes a lintérieur du poly- gone. ‘Déterminer le nombre de triangles contenus (sauf éventuelle- ‘ment les sommets) dans le polygone et dont les cétés sont sur les diag onales du polygone. (Saint-Petersbourg 1996) De l'ensemble de toutes les permutations /de {1, 2,.... 7} qui vérifient la condition : Ni) >i-1 pour §=1,2,....m, con en choisit une (on suppose que ce choix se fait sous hypothise d'quiprobabilé). Soit p,, la probabilité que la permutation choisie vérifie la condition : Ai) 1 éléments de {1 + 00] . Déterminer le nombre maximal de réels de la form 00 ¢; € {0, 1} pour tout é, qui appartiennent & I'intervalle I, lorsque 1 décrit l'ensemble de tous les intervalles ouverts de longueur 1 et § décrit l'ensemble des parties & m éléments de [1 +ool (iran 1996) 2 smégamaciExiste-til un entier > 2 satisfaisant la condition suivante ? (Proposé OIM 95) On colorie k sommets d'un 1-gone régulier convexe P. Un coloriage est di presque uniforme lorsque, pout tout entier m tel que 1 <<, la condition suivante est satisfaite: si My et Mz sont deux ensembles de m sommets consécutifs de P alors le nombre de sommets coloriés appartenant My et le nombre de sommets coloriés appartenant Mz different d’au plus 1. Prouver que, pour tous k,1 entiers tels que 0 < k et chiffres «2>. Soit N le nombre d'entiers strictement positfs dont I'écriture décimale posséde exacte- ment 2r chiffres choisis parmi 1, 2, 3, 4 uniquement et ayant le méme nombre de «1> que de «2>. Prouver que M=N. (Ukraine 1996) Un rectangle de c x € carrés unités (c colonnes, £ lignes) est recouvert par des dominos 2.x 1 ou 1 x 2, sans chevauchement et sans sortir du rectangle. a. Si moins une droite paralléle & Mun des cétés du rectangle, et qui traverse Vintérieur du rectangle sans traverser (intérieurement) de domino ? 6. Montrer que, quel que soit le recouvrement, il existe au. b. Ce résultat estil conservé pour les autres valeurs possibles de cee? (Diaprés Mexique 1996) Lors d'un bal, sept hommes A, B, C.D, E, F, G, dans cet ordre, sont assis en ligne et réguliérement espacés, en face de sept femmes a,b, 6, dee, f.g elles-aussi assises sur une méme ligne, paralléle & la précédente, mais dans un ordre arbitraire. Chaque homme X traverse Ia salle et invite x pour une danse. Montrer que deux des hommes parcourent la méme distance, (Danemark 1996) ‘Trois peintres A,B, C sont disposés un & chaque sommet d'un tri- angle équilatéral de coté n. Le triangle est divisé en petits triangles Ini équilatéraux de c6tés 1 par des droites paralléles a ses 6 tialement, tous les cétés des sous-triangles sont bleus. Les peintres se déplacent alors le long de ces segments, et colorient en rouge leurs trajectoires en respectant les deux régles suivantes ‘ mégamate(i) Le premier & se déplacer est A, puis B, puis C, puis 4 nouveau A, et ainsi de suite. A chaque tour, chacun d'entre eux ne parcourt qu'un seul c6té d'un seul petit triangle. (ii) Aucun des peintres ne peut parcourir un segment déja colorié en rouge, mais il peut rout de méme attendre son tour, seul ounon, & l'une des extrémités d'un tel segment. Prouver que, pour tout » € N’, il est possible de peindre en rouge tous les eétés de tous les petits triangles. (Olympiade ibéroaméricaine 1996) On considére un ensemble de » > 3 points du plan, pas tous alignés. R17 A chacun de ces points on affecte un nombre de telle fagon que, pour "éronse re” ‘toute droite passant par au moins deux des points, la somme des nom- bres de cette droite soit égale & 0. Prouver que tous les nombres sont egaux 8 0. (URSS 1977) On dispose 650 points dans un cercle C de rayon 16 cm. Lacouronne RB ‘A a ses rayons intérieurs et extérieurs respectivement Ggaux & [Link] et wérome rir [Link]. Démontrer qu'ill existe une position de A telle que A recouvre au moins 10 des 650 points. Le plan est partitionné en carrés unités (comme un échiquier infini), RU dont K sont noits et les autres blancs. On fixe une orientation. A sétemer st tun moment donné, tous les carrés changent simultanément de couleur selon Mopération suivante : chaque carré regoit la couleur dominante dans l'ensemble des trois carrés qui lui sont voisins au sud, a louest et au sud-ouest. On note 7, le nombre de carrés noirs apres t opérations. Prouver que: a. Hest possible d'avoir no <7. b, Iexiste £tel que m= 0. ce. Ona ng =0. (D'aprés entrainement olympique USA) rascniement (none) 5R20 R21 R22 Soit > 2 un entier. Un point M d'un cercle de centre O est mobile, de sorte que le rayon OM pivote avec une vitesse constante de 36° degrés par seconde. A l'instant t = 0, le point Mest en Mo. At = 1 seconde, on a M = My. Aprés deux secondes supplémentaires (donc t= 3s), on a M = Mz. Aprés encore trois sscondes supplémentaires (done a t= 6s), ona M = Ms, Et ainsi de suite, jusqu’a ajouter encore n—1 secondes pour avoir M = M, 1. On cherche les valenrs de 1 pour lesquelles, & lordre prés, les points Mp, My, ...,My_1 divisent le cercle en m arcs égaux. ‘a, Est-il vrai que les puissances de 2 sont de telles valeurs ? b. Peut-on trouver une valeur de 1 convenable et qui ne soit pas une puissance de 2? (Tournoi des villes 1985) Un cube est formé de 27 petits cubes unités blancs. On peint en noir les faces du gros cube, puis on le désassemble. Une personne ayant les yeux bandés reforme un cube. Quelle est la probabilité qu'il ait toutes ses faces extérieures entigrement noires ? Donner un ordre de grandeur de cette probabilité. (Proposé OIM 1981) Un nombre fini de jetons identiques sont placés dans des cases «lune rangée infinie. On procéde alors 4 l'opération suivante : on commence par choisir une case contenant plus d'un jeton et, de cette case, on extrait deux jetons. On replace ensuite ces jetons, un dans chacune des ceases voisines de la case initiale, a droite et a gauche. On répéte cette opération tant que c'est possible. Prouver que, pour une configuration initiale donnée, la procédure va s‘arréter, et que ni le nombre d’étapes ni Ia configuration finale ne dépendent des choix des cases effectués lors de ces étapes. (Proposé OIM 1996) « mégamaceQuels sont les entiers 7, k > 2 pour lesquels il est possible de trouver tun ensemble de 1 points du plan, pas tous alignés, et un ensemble de k couleurs vérifiant (i) chacun des » points est colorié a l'aide d'une (seule) des k couleurs ; (ii) chacune des k couleurs est utilisée au moins une fois ; (ii) pour toute droite A passant par au moins deux des m points, pour toutes couleurs cet ¢’distinetes, les nombres de points de A coloriés avec c n'est pas égal au nombre de points de A coloriés avec ¢ ? Soit f : Z — Ztelle que, pour tout n € Z + flr) < {05 1}, flrs 1996) = flr) et f(1) + fl2) +... + f11996) = 45. Prouver qu'il existe ¢ € Z tel que: pour tout 1, si flr) = 1 alors fn+t)=0. (Australie 1996) Deux sauterelles se trouvent une a chaque extrémité du segment (0, 1]. Un certain nombre (au moins un) de points de ce segment ont été marqués, divisant ainsi [0, 1] en un nombre fini dV'intervalles. Une sauterelle peut choisir n‘importe lequel des points marqués et sauter depuis V'endroit oit elle se trouve jusqu'au symétrique par rapport au point marqué choisi, du moment que cela ne Ia fasse pas sortir de 0, 1]. Lors d'un mouvement, soit les deux sauterelles sautent simul- tanément, soit l'une saute et l'autre reste immobile. Les sauterelles ne veulent plus avoir de point marqué les séparant, Existe till un entier M tel que: le moyen dV'atteindre leur but ? Si oui, quelle est la plus petite valeur 1 au plus M mouvements, les sauterelles auront roujours possible d'un tel M ? (URSS 1990) raxonniement (605) 5 R23 éronse p76 R24 R25 reponse 279R26 R27 réponse P84 R28 R29 Dans toute paire de poulets, il y a exactement un dominant et un dominé. Un poulet R est appelé un roi si, pour tout autre poulet X, le poulet R domine le poulet X ou bien R domine un poulet ¥ qui ui-méme domine X (Un poulet ne se domine pas lui-méme). a. Prouver que dans tout poulailler qui contient un nombre fini (non nul) de poulets, il y a toujours un roi. A quelle condition nécessaire et suffisante celui-ci est-il unique ? b. Estil possible d'avoir exactement deux rois ? c. Pour 1 > 1 fixé, quels sont les entiers & pour lesquels il existe un oulailler de 1 poulets ayant exactement k rois ? (D'aprés Michigan math. competition 1981) On a placé une banane en haut de cing échelles. Au pied de chacune dle ces échelles se trouve un singe. Un nombre fini de cordes relient les échelles: chaque corde relie exactement deux échelles, et deux cordes ne sont jamais attachées & un méme barreau d'une échelle. Les singes se mettent & grimper, mais aussit6t arrivés 8 une corde, ils la suivent jusqu'au bout et continuent & grimper sur l'autre échelle. Montrer que chaque singe obtiendra une banane. (Canada 1989) Chaque c6té d'un triangle équilatéral est divisé en m > 2 segments de méme longueut. Des droites paralléles aux cétés relient les points ainsi construits pour partager le triangle en 1 sous-triangles équilatéraux. Une suite de ces sous-triangles est appelée une chaine lorsqu'elle ne contient pas deux fois le méme triangle et qu’ partir du second, tout triangle de la suite & un c6té commun avec son prédécesseur. Quel est le nombre maximal de termes que peut contenir une chaine ? (Colorado math. Olympiad 1987) Trouver le plus petit entier positif k pour lequel il existe une fonction fs Z—> (1,2,...,k} celle que: fix) £Mly) chaque fois que [x9 € {5,712} (Olympiade du Pacifique asiatique 1995) * ndgumacsDéterminer le plus petit entier m ayant la propriété suivante: pour tout 1 > m, et pour tout ensemble {x1,22,..-»%4} dentiers stricte- ‘ment positifs, il existe des nombres €, £2, -.-»£,, non tous nuls et dans {-15 05 1} tels que > 1; soit divisible par 7°. (Roumanie 1996) Soit m > [Link] entiet, Dans le plan, on a relié r points (trois jamais alignés) par m segments. 1a. Prouver que, si pour deux points distincts quelconques il existe un unique chemin reliant ces deux points, alors m= 7— 1 '. Pour 1 fixé, quels sont les entiers m < 1 pour lesquels il est pos- sible de choisit m segments parmi ceux reliant les 1 points, de fagon qu'entre deux points distincts quelconques ily ait toujours au moins un chemin ? (D'aprés URSS 1961) ‘a. Un rectangle est formé par des briques 1 x 6 disposées horizontale- rment ou verticalement et sans point intérieur commun. Prouver que Mun des edtés du rectangle est un multiple de 6. 'b. Pour quelles valeurs de 1 € N* est-il possible de recouvrir exacte- ment un carré de 11 x n cases unités par des tuiles du type: (chaque petit carré est un carré unité ; deux tuiles ne doivent pas avoir de point intérieur en commun) ? (Suede 1996 et Italie 1995) Soit Ay, Az,-.-+Am des parties d'un ensemble $ contenant » éléments {avec n > 2). On suppose que, pour tous x, € § distinets, il existe i€ {1,...,m} tel que x © A,ety ¢ Ai, ou bien x ¢ A; ety © A; Prouver que m > log,(n). (Balkans 1997) ratsonniement (60) . R30 R31 R32 néponser90 R33R34 néponse £95 R35 reponse F95 R36 R37 réponse r97 R38 Dans l'espace sont disposés 1 > 3 points, trois jamais alignés. Quel nombre maximum de segments reliant deux de ces points peut-on tracer sans qu'apparaisse de triangle dont les sommets sont parmi les points ? (D'aprés Putnam 1956) Comment découper un rectangle de 7 x 8 carrés unités en polygones, ‘aucun ne contenant plus de cing carrés, de telle fagon que la longueur totale de la coupure soit minimale ? (les coupures doivent suivre les bordures des carrés). : 4a 1 on a écrit les nombres 48,24, 16...., 55 ycesta-dire tous les nombres rationnels de la forme $ pote ke Sur un table: 2,....97. Une ‘opération consiste & choisir deux quelconques des nombres écrits, a et bs, ales effacer, et & écrire le nombre 2ab —a— b+ 1 au tableau. Apres 96 étapes, il ne reste donc plus qu'un seul nombre sur le tableau. 4a, Déterminer ensemble de tous les nombres qui sont des issues pos- sibles par cette procédure. b. Reprendre le probleme, mais en remplagant cette fois les nombres aetb par 2ab+a+b. (D'aprés Autriche/Pologne 1997) Lrensemble {1,2,...,49} est divisé en trois sous-ensembles, Prouver qu’au moins un de ces ensembles contient trois nombres distiners a, b, ¢ tels quea+b=c. (Proposé OIM 1983) ‘On considére 1 > 2 points sur un cercle de rayon 1. Soit q le nombre de segments dont les extrémités sont parmi ces 1 points et dont les Jongueurs dépassent ¥/2. Prouver que 3q <7? (Pologne 1997) 6 gaanSoit > 2. Partant des nombres a1, d2,..-+dy écrits dans cet ordre, (on ajoute (a droite) la somme des deux premiers, puis la somme des troisiéme et quatritme, et ainsi de suite par paires. ‘a. Prouver que ce procédé va se terminer, et déterminer la longueur totale de la liste finale. 'b. Exprimer, en fonction des a, le dernier nombre marqué et la somme de tous les nombres de la liste finale. (D'aprés championnat de France 1988) Soient », k,m > [Link] entiers. Lors d'un concours, on répartit m ex- ‘aminateurs en m jurys de k personnes. Afin d'assurer la coordination, il peut arriver qu'un examinateur appartienne & plusieurs jurys mais, dans tous les cas, deux jurys différents n’ont jamais plus d'une per- sonne en commun. Prower quem < [# [FF] Soient n,m € N°. 1 enfants désirent se partager équitablement m bar- res chocolatées identiques, aucune de ces barres ne devant étre coupée plus d'une fois. a. Pour quels 1 cela est-il possible si m = 9 ? b. Pour quels et 7 cela estil possible ? (Tournoi des villes 1991) Soit A un ensemble d'entiers strictement positifs tels que, pour tous Oh pa x on ait fx —y| > 22. Déterminer le nombre maximal 29 € A, on ait fey] > F5- De le nombre maximal éléments que peut contenie A. (Proposé OIM 1985) Dans le plan R2, on considére ensemble G des points dont les deux coordonnées sont rationnelles. 1a. La réunion des segments dont les extrémités sont des points de Q ccouvre-telle le plan ? b, L'enveloppe convexe de (c’est-A-dire la plus petite partie convexe de R? contenant Q”) couvre-telle le plan ? (Proposé OTM 1983) antonnement (2voNrs) u R39 seporse p04 R40 négonse p05 R41 R42 R43R44 éponse pa R45 R46 R47 La figure suivante contient 16 segments et 12 sommets. Prouver que Von ne peut pas tracer de courbe continue simple (c'est-adire sans repasser par un méme point) qui traverse chaque segment exactement tune fois, mais ne passe par aucun des sommets. (URSS 1961) Lors d'une soirée, on a invité 12k personnes qui ne se connaissent pas. CChacun échange des salutations avec exactement 3k +6 des invités. De plus, pour chaque paire d'invités, on trouve exactement le méme nom- bre d'hotes échangeantdes salutations avec chacun des deux. Combien dlinvités trouve-t-on a cette réception ? (Proposé OIM 1995) Dans une forét plane infinie, les arbres sont centrés aux points de co- ordonnées entiéres, sauf a lorigine O, et ont chacun un trone eylin- drique de diamétre d € JO, 1[ fixé. Un observateur placé en © peut-il se dégager la vue dans une direction donnée en sciant un nombre fini d'arbres bien choisis ? (On supposera que l'éloignement n'affecte pas Ja vision de lobservateur, et que ceui-ci regarde dans une direction paralléle au plan.) een nt sous-triangles équilatéraux identiques par des droites paralléles & ses cétés. Une araignée et une mouche se trouvent chacune. mets de ces triangles. Alternativement, elles se déplacent d'un sommet un sommet voisin. Prouver que, si elle le souhaite, l'araignée peut Une toile d’araignée a la forme d'un triangle équilatéral, divi Mun des som sraper la mouche. (Baltic way 1993) 8 égamateOn écrit en ligne m nombres réels distinets, dans l'ordre croissant de gauche a droite. On réecrit en-dessous les mémes nombres mais dans tun certain ordre, éventuellement différent. Sur une troisiéme ligne, on écrit alors les sommes par colonnes. Les nombres inscrits sur cette troisiéme ligne sont aussi distincts et rangés dans lordre croissant (de gauche & droite). Peut-on en déduire que les deux premigres lignes sont identiques ? (URSS 1984) 119 locataires vivent dans un immeuble de 120 appartements. Un de ces appartements est surpeuplé lorsqu'au moins 15 personnes y habitent. Chaque jour, tous les locataires d'un des appartements surpe- uplés s'en vont habiter dans des appartements différents quelconques. Arrivera-t-il un jour od il n'y aura plus d'appartement surpeuplé ? (Leningrad 1988) On a disposé 50 montres sur une table circulaire. Prouver qu'il existe un instant oi la somme des distances depuis le centre de la ta- ble aux extrémités des aiguilles des minutes est strictement supérieure 4 la somme des distances depuis le centre de la table aux centres des montres. (URSS 1976) ‘On donne 1989 points dans le plan, trois jamais alignés. Comment doit-on les répartir en trente groupes de tailles distinetes de fagon 8 maximiser le nombre des triangles ayant leurs sommets dans des groupes distinets ? (Chine 1988/1989) Un tournoi regroupe 1 > 2 participants. Un match est organisé pour toute paire (A. B} de joueurs distincts. Il n'y a jamais de partie nulle. A Tissue du tournoi, on note s1,....,5, les nombres de victoires re- spectives des joueurs. Prouver qu'il existe trois joueurs A, B, C pour lesquels A a battu B, B a battu C, Ca battu A siet seulement si: 2 Ma = Wn 1) (Putnam 1958) rarsonnement (wows) 3 R48 R49 érorse pint R50 évonse pis B51 R52 esrR53 ons nas RI4 RSF R56 Soit 64 points du plan qui, deux a deux, déterminent exactement 2001 droites distinctes. Prouver qu'au moins quatre de ces points sont alignés. (Wohascum county math competition) Soit n,k © N*. La suite a1,42,....ap est dite n-universelle si toute permutation de {1,2,....7} en est une sous-suite. Par exemple: 1,2, 3, 1,2, 3, 1,2, 3 est 3-universelle, mais 1, 2,3,2,1,3,1 ne l'est pas puisque l'on ne peut obtenir 3, 1, 2. On veut estimer la longueur rminimale €(7) d'une suite universelle pour un m donné. a. Donner un exemple de suite universelle de? —»1+ 1 termes. n(n) 5 termes. b. Prouver qu'une suite universelle contient au moins . Prouver que €(4) = 12. 4. Prouver qu'une suite universelle de longueur minimale ne contient pas plus de 1? — 21+ 4 termes. (URSS 1976) Le plan est considéré comme un échiquier infini dont les cases unités sont naturellement blanches et noires. On suppose que S est un en- semble de 1976 cases tel que deux cases queleonques de S puissent xe relies par un chemin formé de cases voisines (cest-2-dire qui ont tun c&té en commun, Et une case est relige a elle-méme.) Montrer que S contient au moins 494 cases blanches. Peut-on améliorer cette estimation ? (Autriche-Pologne 1976) Sur une table se trouvent 2000 jetons. Deux joueurs enlévent des jetons A tour de réles selon les deux régles suivants: (iA chaque tous, un joueur peut enlever 1,2, 3,4 ou 5 jerons (i) Un joueur ne peut pas enlever le méme nombre de jetons que son adversaire lors de son tour précédent. Le premier joucur qui ne peut pas respecter ces régles perd. Déterminer sil'un des joueurs a une stratégie gagnante, (Olympiad ibéroaméricaine 2000) “ rgamatePierre a choisi mentalement un nombre a dans {1,2,.... 14}. Isabelle, qui cherche a découvrir a, peut choisir un sous-ensemble F de {1,2,.... 144} et demander si a appartient & E ou non. Sila réponse est , Isabelle doi payer deux euros. Si la réponse est «non», elle doit payer un euro. Quelle est la somme minimale nécessaire qu'Tsabelle doit posséder au départ pour étre assurée de trouver a ? (Russie 1998) Les délégués de 1 > 2 pays s'assoient autour d'une table ronde. Afin de faciliter les échanges, deux délégués distincts d'un méme pays ont toujours leurs voisins de droite respectifs qui viennent de deux pays différents. De cette fagon, combien peut-on asseoir de délégués au (Olympiade ibéroaméricaine 1998) Prouver que, de tout ensemble donné de m > 3 points du plan, on peut en exclure un de telle fagon que l'ensemble restant puisse étre partage en deux sous-ensembles, chacun de diamétre inférieur & celui de lensemble initial (le diamétre d'un ensemble fini de points est la distance maximale entre deux points de l'ensemble). (Russie 1998) sasonnerent (éuoncis) » R57 éronse B95 R58 R59 séponse pasali négonse ps al2 al3 neyo ns al4 algepre éNONCES Estil possible que P(x) soit un polynéme a coefficients entiers dont l'un au moins est strictement négatif, mais que, pour tout entier > 1, le polyniime (P(x))" ait tous ses coefficients strictement positifs ? (Tournoi des villes 1994) Soient x,y, 2 dans IR" tels que xyz = 1, Prouver que: ayadensy eed Uxyt eter). (Proposé Moscou 2000) Soient a}, . 11161, --+,b, des réels tels que 0 < by < 1 pour tout Ryetay > dy >, > ayy =O. Prowver qu [exa]n Saas ot at ‘ai mi (Saint-Petersbourg 1996) Déterminer tous les quadruplets de polynémes Py, P2, Ps Pay a coeffi- cients réels vérifant : pour tous entiers x, y,z, ftels que xy—zt = 1, on 2 pulx)paly) — pslzhpale) = 1. (Saint-Petersbourg 1996) “ megamant,o 4 88. OF <4. 1 Prouver que pour tout m € NT : 22-4’ (lrlande 1996) Soit 1 > 5 un enties, et b ER". Le polyndme: fx) est A coefficients réels, et toutes ses racines x, sont céelles, avec "—10bx" > + asx 84. ty Bin Sig Sos SA. Six que vaut a3? (Selection Roumanie 1999) a. Prouver que, pour tout € Nil existe un ensemble M,, contenant ‘exactement 1 entiers strictement positifs et qui vérifie: les moyennes arithmétiques et géomeétriques des éléments de toute partie non vide de M,, sont des entiers. b. Existe-til un ensemble infini d'entiers naturels M pour lequel la moyenne arithmétique des éléments de toute partie non vide de M est sun entier ? (Bosnie 1997) Soit 1 > 1 un entier impair. On suppose que les entiers naturels 2X4, %2,--., %y Vérifient le systéme : G—aP + Qertom) + 1 = (xy 92P + Axyem) + 1 = at (xy — ay + Zepto) + Loe a Prouver que x1 = %» ou qu'il existe j, avec 1 ays yz+ax. Déterminer les cas dégalité. b. Soient a,b,c, d quatre réels positifs ou nuls vérifiant ab vac ad+bexbd + ed) abe-+ abd + acd + bed = 16. Prouver quesa+bsced > Fab +act ads be+ bd +a. Déterminer les cas dégalié. (Vietnam 1996) Soient a,b,c des entiers non nuls. Sachant que |'équation ax? + by! + cz? = 0 admet une solution (x,y, 2) en entiers non tous nls, prouver que l'équation ax? + by? » cz 1 admet une solution en rationnels. (Proposé OIM 1984) Déterminer tous les triplets (x,y, z) de rationnels strictement positifs pepe tels que x 3 un entier, tay, ..., dy des réels strictement positifs. Prou- ALI 4 verque: 4 a on trove nto ONE aay * ay +a nea 4 (URSS 1969) Soient » > 3 un entier, et x € R*. alis Prouver que les nombres x, 2? et 2” ont la méme partie décimale si et "Fors 162 seulement si x est un entier. (Roumanie 1997) Soient n > 2 un entier, et 21,22,---,2, des complexes de module 1. ALI6 Prouver que: once pits [Hepteptat em ten —2ntetegl oot er te2 Zl S max(2r, 12), (Selection Roumanie 1999) a. Prouver que pour tout enter > 3, il existe deux ensembles ALL A= {1.00% 9} Ct B= (91, ---3o} vérifiane les trois conditions suiv- xéronse esce antes : (@ AnB=¢. ii) xp tone ty eo eee iit) xPoxpe..tx2aypeype..ty) b. Soit » © IN'. Prouver qu'il est possible de partager l'ensem- ble {1,2,3,...2"} en deux groupes disjoints tels que, pour tout p€ {0,1,...1— 1} la somme des &? lorsque k décrit un des groupes est égale a celle des k? lorsque k décrit Vautre. (D’aprés Iran 1996 et Suéde 1996) Soit 2 > 3 un entier. Prouver que si toutes les distances entre » points ALIS sur une droite, sauf pour celle entre les points extrémes, paraissent au réponse sty moins deux fois, alors toutes ces distances sont commensurables. (Iran 1998) alginne (evens) »alig réponse 2168 aL20 al21 séponse part aL22 al23 dgonse 277 a. Soit = 24, otk © N. Prouver que parmi 2n~1 entiers quelconques, on peut en trouver dont la somme est divisible par m. b, Cela reste-til vrai si m n'est pas supposé étre une puissance de 2 ? (D'aprés Allemagne 1981) Soient ar, des rées tels que e302 +Sa—17=0 et fP—3p%+ 5p 411-0. Déterminer a + B. (Inlande 1993) Soit (q,) une suite infinie d'entiers vérifiant les deux conditions : (i) Pour tous entiers m > > 0, m —m divise dy ~ dn» (Gi Tl existe un polyndme P tel que, pour tout entier n, gu] < P(r. Prouver qu'il existe un polynéme © tel que, pour tout entier m, Ole) = dn (USA 1995) a, Soient a,b deux réels distincts, pour lesquels les nombres a ~ b, 2 — 62,0 ~ b3, etc. sont tous des entiers. Les nombres a et b sont-ils rationnels ? Sontils entiers ? b. Existe-til des réels a, b distincts pour lesquels a + b est rationnel et af" +b” est irrationnel pour tout entier n> 2? ¢. Existe-til des réels a,b distincts, pour lesquels a+ 6 est irrationnel et a" +B" est rationnel pour tout entier m > 2? (D'aprés Wohascum county math competition et URSS 1989) Soit 2 € N*. On considére les nombres 1,2,2?,...,2" 1. Pour une permutation o = (x1, ....%,) de ces nombres, on définit : So)=a1, Slo) =x1 +32, Slo) =xy 422425, ete. et Q[0) = S,(09S3(0)...S,(0) Calculer > oa , Cette somme portant sur toutes les permutations o possibles, (Canada 1989) 2 gaatDéterminer tous les polyndmes P, non constants et & coefficients ra- tionnels, tels que P-'(Q) CQ. (Iran 1996) Soit P(x) = ax? + bx +c, avec a,b,c € R. Prouver que s'il existe y €[15; 16] tel que P(y) > 1921, alors il existe un nombre rationnel 705 1] tel que P(r) > 1. {Selection Roumanie 1999) Le nombre p désigne le produit des réels x1,.3,...,%,- Prouver que si, pour k = 1,2,...,n, le nombre p ~ x, est un entier impair, alors chacun des nombres x1, X2, .-.,%q €St itrationnel. (Tournoi des villes 1995) Déterminer tous les entiers strictement positifs pour lesquels affirmation suivante est vraie : «Si F(x) est un polyndme a coefficients entiers tel que 0 < Fle) < k pour tout c € (0,1,...,k +1}, alors FO) = Fl) =... = Fk + Be» (Proposé OIM 1997) Soient 1y,...,1, des entiers non muls deux a deux distinets tels que, pour tout k € Z, le nombre maz --.1 divise ny + Yer. +h). (4+h). Prouver que: a. il existe i € {1, ....s} tel que [ni b. si tous les m sont dans N°, alors (111, #2. .--yt} = {Is --.+5}> (Putnam 1982) Prouver qu'il existe un réel strictement positf w tel que, pour tout » © IN, le nombre [1] a la méme parité que x. Donner une valeur explicite den (D'aprés Putnam 1983) alginne (Eons) ” al24 séqorse ra78 al25 al26 ségorse pat aLl27 al28 al29al3o0 aLlji al32 pons p88 al33 réponse rity al34 néponse P90 Soient a, b, c des complexes deux a deux distinets vérifiant: (aby #(b— el #(c— a? =0. Prouver que a,b,c sont les affixes des sommets d'un triangle éqquilatéral. Déterminer les angles 6 tels que: sin @ + cos6 + tan + cotan@ + —— z 6.4. sin * cos ~ Soient 2 > 1 un entier. Déterminer le minimum de: 2 shia rcigpen Be tHE) +) o.x1,22, +55 Sont dans R™ tels que x17 (D'aprés Roumanie 1997) Soit a un nombre rationnel, avec 0 < a < 1, et tel que: cos(311a) + 2 cos(2zca) = 0. Prouver que a (Proposé OIM 1991) Un bloc @ gauche pour l'entier strictement positif N est un bloc formé par des chiffres consécutifs de "écriture décimale de N & partir de celui ui est le plus & gauche. Par exemple 137 est un bloc a gauche pour 13729 mais pas pour 5137. Une suite d'entiers 0 < my < my <...est dite spéciale lorsquaucun des n, n'est un bloc a gauche pour un des 1 avec i 7. Prouver que pour toute suite spéciale on a: (Iran 1998)Soient k > 2 un entier, ct @1,@2,..-,0 des récls distinets dont la @L35 somme n’est pas nulle, Prouver quil existe des entiers my, g..+-0 ie négonse 1198 qui vérifient les deux conditions suivantes 3 Srna > 0 ation ode (1,2, ..., k} autre que identité, on a: t Seca <0. a b. Pour toute (Iran 1997) Soit n € N*. On se donne 2n réels ay, ..., dy, b1,.--by vérifiant: — ALZ6 Ay > ay >... By > Oct by > by >... 2 by > Oeraver: irons 4 ty 2 Bay ay 4.0 > By + Day ony Oy 4g Ho Hy BBL thy Het One Prouver que, pour tout entier k > 2, on a: ak cake. at > bt bf +. 46h Enadier les cas d'galité. (Entrainment olympique France 1981) Déterminer le plus petit entier naturel non nul pour lequel le nombre Q@L57 97 1 réponse 97 Aiea (: " zy mui) a. est un nombre rationnel. b. est un nombre entier. (Selection Roumanie 1998) Soient pi.P2,Ps Pa des nombres premiers distincts. Prouver qu'il ALZS8 n'existe pas de polynéme Q, de degré 3 et & coefficients entiers, tel yugonse p98 que |Q(p1)} = |Q(p2)| = (Autriche/Pologne 1997) aigiane (excncis) Bal39 reponse p99 al4o alg. al42 Résoudre en nombres complexes le syst?me suivant : (x-yP axtex (y-2Payey (z-xPadez (Proposé OIM 1994) a. Prouver que, pour tous réels p et q, on a: p? +g" 41> pig +1). 'b. Déterminer le plus grand réel b tel que p? + q? +1 > bp(q+1) soit vraie pour tous réels p et q. ¢. Déterminer le plus grand récl c tel que p* + q* +1 > ep(q +1) soit vraie pour tous entiers p et q. (Autriche/Pologne 1997) On considére tous les trindmes de la forme ?+¢px+q, oitp, q décrivent {1,2,..-,1997}. Soient By ensemble de ces trinémes qui ont des ont pas de racines entidres, et Ez ensemble de ces trinémes 4 racines réelles. De Ey et Fa, quel est celui qui a le plus d'éléments ? (Russie 1997) a. Soit » > 2 un entie Prouver que quels que soient les réels Hepp ON 1 nl —2 YD costae Asien b. Soit 2 € N°. Déterminer la valeur maximale de )~ sin”, , lorsque * a 6, > 0 pour tout fet S>6;= x. (Proposés OIM 1981 et 1983) Py mégamaceProuver que, pour tout entier 1, il existe un unique polynéme Q a coefficients dans {0, 1, ..., 9} tel que Q(-2) = Q(-—5) =n. (USA 1997) Soient Ay, Az,-..,Any les sommets, dans cet ordre, d'un polygone régulier inscrit dans un cerele de rayon 1 et de centre O. Soit M un point sur la demi-droite [OA;), extérieur au polygone. Prouver que: | n Sa? oh (Croatie 1996) Soit Sun ensemble d’entiers contenant les nombres 0 et 1996. On sup- pose que tout entier racine d'un polynéme non nul a coefficients dans S appartient aussi a S, et qu’a part peut-étre 0 et 1996, tout élément de S est racine d'un tel polynéme. a. Prouver que ~2 € S. b. De (D'aprés Baltic way 1996) ner le plus petit ensemble § possible. Des nombres sont écrits sur une feuille, On peut ajouter & cette liste tout nouveau nombre correspondant a la moyenne arithmétique de certains de ceux qui sont déja dans la liste. Sila liste initiale est formée des nombres 0 et 1, prouver que l'on peut finir par écrixe 1 a. Lenombre 5. b. Tout rationnel r € (03 1]. (URSS 1979) Soient a, b, c,d des récls. On pose A = {x € R | x*+alx| + = Of et B= {x€R| [xf +fx]+d=0}. Prouver que si A et B ont exactement ments en commun, alors a n'est pas un entier. trois: (Roumanie 1997) algéane (Enos) s al43 al44 néponse 7209 al45 al46 al47aLl48 al 49 alyo aly. al52 Pronver que tout nombre rationnel strictement positif peut s'écrire sous la forme (Proposé OIM 1999) Prouver que, pour tous 4, b, c € R* tels que abe = 1, ona: ab be a Oe BS cab * Bach ebe* oe et déterminer les cas d'égalité (Proposé OIM 1996) Soient a.b.c dans R’ tels que Va+ b+ Je “s Peover anil systtime : Vi-b+ Vx—b=1 \iesisvert 1 Venes Vyne=l admet une unique solution en nombres réels. (Proposé OIM 1983) Prouver que tout réelstrictement positif peut s'éerire comme la somme d'au plus 9 réels dont 'écriture décimale n'est composée que de 0 et de7. (Tournoi des villes 1981) Soit f un polynéme & coefficients rationnels, et bx) = x3 — 3x +1. Montrer que, si le réel a vérife ba) = bifla)) = 0, alors bif"(a) = 0 pour tout 1 € N* (oti! = fet f"" = fof"). (Proposé OIM 1992) 6 gamaOn dit que l'on a défini une opération algébrique sur V'intervalle (0, 1] orsqu'il existe une régle qui a tout couple (a,b) de nombres de cet intervalle fait correspondre un nombre ¢ € [0.1] (Ce que l'on note a@b=d. Déterminer tous les réels k > 0 pour lesquels il existe une opération algébrique @ sur [0,1] telle que, pour tous x,y,z € [0,1] les trois conditions suivantes soient vérifiées : () x@1=1ex=35 (i) x0 QO2)=(xoy O25 (iil) (zx) @ (zy) = (x @ 9). Pour ces réels k, préciser les opérations algébriques correspondantes. (Géorgie 1997) a. Soient a1, az, a des réels strictement positifs tels que: (ap +a) +42)? > Ya," +a;' +a) Prouver que a1,d2, as sont les longueurs des cétés d'un triangle. b. Soient > 3 un entier, et ay, ay... dy des récls strictement positifs tels que: 2 > (n— Ia, +a +... #4,). (a2raze...+a, Prouver que, pour tous i,j,k deux & deux distinets, les nombres 44, 4,44, sont les longueurs des céxés d'un triangle. (Chine 1987/1988) 171 > 2 progressions arithmétiques de réels, infinies dans les deux ns (c‘est-3-dire indexées sur 2). a. Prouver que si ces progressions ne sont constituées que d'entiers et que deux quelconques d'entre elles ont un terme en commun, alors elles ont toutes ensemble un terme commun. b. Prouver que le résultat précédent n'est plus vrai si l'on ne suppose ‘pas que les progressions sont & valeurs entiéres. . Prouver que si trois quelconques des progressions ont un terme en commun, alors elles ont toutes ensemble un terme commun. slginae (évoncés) ” al53 dponse nat aly4 als55 neyonse p24al56 al57 sénonse p27 Soient a, b, c,d dans B™ tels que a + b? = (2 +d?)*. Prouver que: sg Cyto (Entrainement Singapour 2000) Soient 1 € IN et 41,3, .-+4 dy, bs, Bas -+++by des réels distinets. Dans un tableau 1 x n, a intersection de la ligne i et de la colonne j, on écrit le nombre a; +b;. Prouver que, si le produit de tous les nombres inscrits sur une des lignes ne dépend pas de la ligne choisie, alors le produit de tous les nombres inscrits sur une des colonnes ne dépend pas de la colonne choisie. (Entrainement Yougoslavie 2000) * mgmtaNaLyse ENONCES Soit n> Lun entier. aN Déterminer les fonctions f : B — R telles que, pour tous x,y réels : fle +9") = lx) + fo". Soit A un réel et (a,) une suite non majorée de réels vérifiant : a 1 aN2 et <4 0. a, Prouver qu'il existe une unique fonction k : N° + N* surjective et croissante telle que: ako 1 0. b, Sila fonction k ne prend chaque valeur qu’au plus mt fois, montrer quill existe une constante C > 1 telle que: C™ < Aa, pour tout 2 > 0. (Turquie 1995) Déterminer tous les couples (a,b) de réels strictement positifs pour. @NF lesquels séronse nase Si(x,) est une suite quelconque de réels vérifiant lim (aan, —baty alors (x,) converge vers 0 (Turquie 1995) atyse (onc) 2»aN4 aNy aNn6é éronse 7236 aN7 an8 Déterminer tous les triplets (f, gb) de fonctions réelles vérifiant, pour tous x,y réels: fox) ~ gly) = (& —y)hix +9. Soient ay, ...,4q dans R*, non tous nuls. a. Prouver que l’équation x" — ax"! — ...— dy 127 —a, = 0 admet tune unique racine strictement positive, notée R. b. On pose: A= Sa; et Baye. a = Prouver que: A* < B®. (Proposé OIM 1996) Déterminer l'ensemble des valeurs prises par la fonction f définie par 342sinx fix) Jiteone fie (Roumanie 1997) lorsque x décrit R. Soit » > 1 un entier. Prouver que le graphe de toute fonction F : [0,1] —> 0, 1} continue erstrictement croissante, peut étre recou- vert parn rectangles, chacun dire 4 et dont les cbtés sont paallles aux axes de coordonnées (les rectangles peuvent se chevaucher, et les bords sont pris en compte). Le résultat estil conservé si la fonction f n'est plus supposée continue ? (Tournoi des villes 1984) Déterminer toutes les fonctions f : B —+ R continues en 0 vérifiant pour tout réel x, on a fix) — 2fltx) + fx) = x2, ob t € J05 TL fixe. (Croatie 1996) xe régamatySoient a, b, ¢ des réels, avec a 40 et (b— 17? > 4{ae +1), Prouver qu'il ANQ n'existe pas de fonction f : R—» R telle que, pourtourx cR: —— Mrowsera4t Flflx)) = ax? + bx +e. (D'aprés tournoi des villes 1996) ee ee aNnio : reac ionic et f(x» 35) +A01=1(x+ 2) +/(x+4) Prouver que fest périodique. (Proposé OIM 1996) SoitA.C Reef: A—+R une fonction elle que: ann ence f+) = Afi — fly) #1 Pour rous x, y dans A. Déterminer toutes les fonctions f lorsque: @AZN WAZQ GAR (D'aprés Bosnie 1997) don onllieanapen tome i eum ani2z fiex+9) > fled(I+yf)) pour tous x,y R™. (Turquie 1996) Soit g : N* —» R croissante ct multiplicative (i.e. pour tous a,b dans. @AN13 [N* premiers entre eux, on a gab) = gla)g(b)). Prouver que, soit g est reronser30 que, pour la fonction nulle, soit il existe une constante u € I tel tout nm EN, g(a) =r", natyse (enoncés) »aNl4 aNly cae ani6 aNni7 ani8 aNnlg9 Soit c(n) le nombre de fagons de recouvrir un carré 2” x 2" par des In(In (con) dominos 1 x 2. Déterminer lim ‘Déterminer les fonctions monotones f : R —+ R telles que, pour tout réel x: A(Afex))) — 3f(fex) + 6ffx) = 4x + 3. (Roumanie 1999) Déterminer tous les réels a), dz, ds pour lesquels: 44, costa) + a2 cos(azx) + a3 coslayx) > 0 pour tout réel x (Roumanie 1996) Existe-til une fonction réelle f dérivable sur et telle que, pour tout réel x : |flx)] < 2 et flxif'(x) > sinx ? (Wohascum county math competition) Prouver qu'il existe un nombre A pour lequel il est possible d'inserire 1978 carrés de tailles différentes sur la courbe d'équation y = Asinx (un carré est inscrit si ses quatre sommets appartiennent a la courbe). (Urss 1978) On constate expérimentalement qu'un phénoméne physique est représenté par un graphique ayant I'allure suivante ro 2 megamanLianalyse des propriétés importantes de ce graphique condui rechercher une fonction continue f : [15 +00| —» R telle que f(1) (2) = 2, fadmet un maximum en t= 2 et lim fit) = En supposant que f est un quotient de deux fonctions polynémes restreintes & l'intervalle considéré, donner un exemple d'une fonction ayant ces propriétés. (Belgique 1979) Pour n > 3 entie, on désigne par (1) le nombre maximum de triangles rectangles que l'on peut construire a 'aide de » points du plan. Prouver fe) aoe: ae aa 7 (Hongrie 1966) La suite de Fibonacci est définie par Fy = Fy = 1 et Fyy2 = Fyat + Fe pour 1 € N*. Soit x, € ]05 1[ fixé. Pour m€ N°, on pose: si x. ¥0 alors X—1 = =~ [2 jes X= 0 alors xy41 = 0. Prouver que, pour Xn tout» € N', ona: Ah Fy Mette pp tet ES (Propose OIM 1992) Soient 1 € N* et a > 1 un réel tel que, pour tout k € N’, le nombre at n'est pas un entier. On pose m= [a"]- Prouver que: Sole + > logy Al = mn. me (Roumanie 1999) Soient n € N', et ay > az > ... > dy des réels tels que, pour tout keEN af 4a; +... +4, > 0. On pose p = max(|ay|, lazh,-.-+ lanl). Prouver que p = a; et que pour tout x > a) + Tl @-4) K qui vérifie les conditions suivantes (i) Pour tout P € P, on a flP) > 0. (ii) Si P est un triangle équilatéral de cOté x, alors f(P) = x2. (iii) Si on partage le polygone P en deux polygones S et Tn'ayant pas de point intérieur en commun, alors f(P) = fiS) + (1). (iv) Silles polygones P et Q sont isométriques alors (P) = flQ). Que vautt \P) si P est un rectangle de obtés x et y ? (Macédoine 1996) se apes Chea aaa -( pour > 1. Prouver que pour tout 2 € N’, on a: {Proposé OIM 96) Une suite est dite fibonaccienne si chacun de ses termes, hormis les deux premiers, est la somme des deux qui le précédent. Prouver que ensemble N° peut étre décomposé en une infinité de suites fibonac ciennes n‘ayant deux a deux aucun terme commun, » dgamanRaISONNemeNt corRigés Notons e1,€25.-+, 20 les enfants. Si g est un grand:-pére, on pose G = {c; | g grand-pére de ¢,}. Comme e nombre d'enfants est fini, on peut considérer un grand-pére gi tel ‘que Card G =m soit maximal. Sim, = 20, c'est fini. Dans le cas contraire, quitte & changer les indices, on peut toujours supposer que ¢, € Gy et ep ¢ Gy. On appelle ge le grand-pére commun & e; et €2 Si tous les petits-enfants de gy étaient aussi des petits-enfants de g , on aurait Gy U {e,} C G25 et done Card Gy > m +1, ce qui contredirait le caractére maximal de m,. Il existe done un enfant, disons ¢3, tel que e € Gy et ey ¢ Gp. Or ep et es ont un grand-pére commun, et celuicci n'est nig) ni ge - Appelons-le gs. Les enfants ¢, ¢ et ey ont done leurs deux grands-péres respects déterminés, selon le schéma suivant: ® Pour i > 4, ¢; doit done «choisir» ses deux grands-péres parmi £15 £2 et gy. Ainsi, gy, g2 et gs sont les seuls grands péres de tous les enfants. Ceux-ci déterminent 2 x 20 = 40 grands-péres. Or, 40 = 3 x 13 + 1. Done, d'aprés le principe des troirs, un des trois grands-péres g1 + £25 ‘gs posséde au moins 14 petits-enfants (en particulier g1, Puisque m est maximal). anonnerment (comes) 8 RIR2 enone pa Remarques: Le nombre 14 ne peut étre amélioré par un nombre plus grand, par exemple, si: = g1 a pour petitsenfants: €1,....¢145 = g2a pour petitsenfants: e1,...4¢7 et €1s.---€205 = g3.4 pour petitsenfants: ep,....¢20 © Pour 1 enfants, on obtient exactement de la méme fagon : 2n+3 3) me ‘* On peut considérer le probléme «dual» suivant: «si deux enfants nnfont jamais les mémes grands-péres, mais en ont toujours un en com- mun, quel est le nombre minimal de grands-péres ?> La réponse est évidemment 21 (pour 20 enfants). Mais c'est aussi un cas particulier d'un théoréme important d'Erdés, Ko et Rado : «Soit E un ensemble 4m éléments (n € NN"). Soit F une famille de sous-ensembles de E qui contiennent chacun exactement k > 0 éléments, avec 2k 2 des entiers. Ric. 0)= [3] oii [x] désigne le plus petit entier supérieur ou égal & x. (On va prouver que Considérons un recouvrement arbitraire, utilisant R rectangles. On désigne par: xe nombre de rectangles qui recouvrent a la fois une partie de la ligne supérieure et une partie de la ligne inférieure du quadrillage s y (resp. 2) le nombre de rectangles qui recouvrent une partie de la ligne supérieure (resp. inféricure) mais pas la ligne inférieure (resp. supérieure) du quadrillage ; tle nombre de rectangles ne rencontrant ni la ligne supérieure, ni la ligne inférieure du quadrillage.[ln jl Rextyecet a Ainsi: Ty a €~ 2 lignes intermédiaires & recouvris, done: yreemese-2 2 De plus, ily a ¢ segments verticaux reliant la ligne supérieure & la ligne située juste en-dessous. Cela entraine 2x+2y > ¢, ou encore x+y > 5 Comme + + est un entier, il vient done: ¢ xey> | HI 6) De la méme fagon, on a: x+e> (| (4) De (2), (3) et (4), on déduit alors : 2x + 2y +22 +21 >2 [5] +€—2,e donc, d'aprés (1): R> [S51 Et puisque R est un enter: x [5]-[3} Ceci étant vrai pour un recouvrement quelconque, on a done RG O> [-{s]> é e],fe Il reste maintenant & trouver un recouvrement en |5)+]5]—1 2|*|2 rectangles. Partons du rectangle principal (celui dont les bords sont les bords du quadrillage). Puis, on eresserre> successivement le rectangle d'une colonne de chaque cété, mais en conservant la hauteur maximale, atonement (comnigis) ”R3 i cet pica ee £ rectangles ‘© Si c est impair, il reste une colonne libre, que l'on recouvre par un rectangle arbitraire de hauteur maximale, Ainsi, on a recouvert toutes les colonnes a l'aide de [$] rectangles. 2 Mais on a également recouvert les lignes supérieures et inférieures du quadrillage. Il ne reste donc plus qu’a recouvrir les — 2 lignes in- termédiaires. Ce que l'on fait en procédant comme ci-dessus; cela t-2)_[e ustise 5] = [$] 1 nouveaux setangles , D’oit un recouvrement du quadrillage en [5 eS] rectangles. Ce aqui achive la demonstration. (On note, .-..2%49 les nombres dans le sens des agulles d'une mon- tte, avee x; = 6. On considére que xiy100 = Soit i € (1,..., 100}. Ona: RAK eee ROO HR tT Hm; HM = OOH, Rio (Or, le membre de gauche posséde 102 = 6 x 17 termes; donc, en les regroupant par paquets de 6 consécutifs, il vient : 100+; + in < 17 x6 Cesta-dire +x; +41 <2. Ainsi: 100 = (x #222) + (a5 +4) +--+ (99 + 100) <2 x 50 doi: Raj ta 22 pour j= 0,1,...,49. De méme: 100 = (on +25) + (4 +85) +--+ CEt00 + 1) < 2x SO dot: Xy+Xyo1=2 pour j= 1,2,...,50. s rmégamatiPuisque x1 = 6 on en déduit facilement que, pour rout i € {1,..., 50}: xy 126 et x= Réciproquement: Pour les valeurs ci-dessus, la somme de deux nom- bres consécutifs est 2, done la somme de 6 consécutifs est 6, et la somme totale est 100. C'est bien une solution. {Etudions directement le cas général en remplagant 1996 par un entier n>6. ‘+ On commence par prouver que le nombre de triangles contenus au sens large dans le polygone et dont les cétés appartiennent aux cordes déterminées par les sommets est Ty) = 2) ug 18172 — 430+ 60). o Cas n°1: Les trois sommets du triangle sont des sommets du polygone. ly a clairement C} triangles de cette sorte. Cas °2 : Exactement deux des sommets du triangle sont des sommets du polygone. Cay) Le troisiéme sommet est done un point intérieur, intersection de deux diagonales. Chaque choix de 4 sommets quelconques engendre 4 tels. triangles, ct tout triangle de cette sorte est engendré une seul fois par la donnée de 4 sommets. D'oii 4Cé triangles dans ce cas. Cas n°3: Un seul des sommets du triangle est un sommet du polygone. passonement (comngés) ry R4 once 2Un tel triangle nécessite la donnée de 5 sommets du polygone. Et ‘chaque choix de 5 sommets génére 5 de ces triangles. ‘Ainsi ily a SCS triangles dans ce cas. Cas n°4: Aucun des sommets du triangle n'est un sommet du poly- gone. Un triangle de cette sorte nécessite la donnée de 6 sommets du poly- gone. Er chaque choix de 6 sommets ne génére qu'un seul triangle de ce type. Done, ily a Cé triangles dans ce cas. Ces quatre cas sont deux 3 deux disjoints et recouvrent routes les pos- sibilités, Done: Ti) = C} + 4C} + SC} + C8, ce qui amene & (1). + On prouve maintenant que les «mauvaisy triangles, c'est-&-dire ceux dont les céxés ne sont pas uniquement sur les diagonales, sont au 3) i En effet, un mauvais triangle est un triangle dont au moins un cété est un cété du polygone. Cas n°1 : Deux cdtés du triangle sont des cétés du polygone. nombre de Crest quil s'agit de deux c6tés consécutifs du polygone (il n'y a que trois sommets dans un triangle. .). I y a 1 choix possibles pour ce groupe de trois sommets consécutifs (Par exemple, on numérote les sommets dans Hordre des aiguilles d'une montre. Le groupe est déterminé par le premier des sommets du groupe lorsque l'on respecte ‘cette orientation.) Le triangle est formé par deux sommets consécutifs et un ne non adjacent aux deux autres. Ily an choix pour le groupe des deux sommets consécutifs. le troisiéme doit alors étre choisi arbitrairement dans les 1 — 4 sommets restant (cous sauf les deux déja choisis et leurs deux voisins). Dioii n(or— 4) triangles dans ce cas. © smégamateCas n°3: Le triangle est formé par deux sommets consécutifs et un point intérieur. ‘On raisonne comme au cas n°2 lors du caleul de Ti). Mais cette fois, Te choix de I'aréte du 1-gone brise la symeétrie et ne génére done qu'un seul des triangles. Il y a m choix pour cette aréte, puis C>_, choix pour les deux autres sommets qui vont permettre de défini le point in D'oti nC2_, triangles dans ce cas. Ce sont les seules possibilités de mauvais triangles. En sommant, il vient que le nombre de mauvais triangles est: rn 3) My=nC2 3 +n 4) n= ‘On en déduit facilement que le nombre de «bons» triangles est Tht) — My ,clest-i-dire: nor 304) 3 5, 720 + 16x? — 67n — 10) En particulier, pour 7 = 1996, on a Buygg = 22 x 3 x 5 x 83 x 499 x 1999 x 17 812.681 = 88 485 472 208 701 380, Les entiers cherchés sont 1, 2,3,4,5, 6. Soit x € N'. On note: ‘Ay le nombre de permutations fde (1, ..,1} telles que: fa) > i—1 pour tout. i) B, le nombre de permutations f de {1, .... #} vérifiant (1) et: fi) 2. Prewe: Soit f une permutation de {1,...,1#1} qui vrifi (1) et (2). Comme ci-dessus, on a fins 1) € (5 0 1}. #Siftnelaned: On raisonne comme a la proposition 1, et le nombre de permutations dans ce cas est B,. # Sif 1) Diapris (2), si’ < m— 1, on a fll) on p, <2(8)" = 0.296..-< 3, Dow n> foon doit avoir n < 8, 2 Réciproquement: py = 1, Po = 8, 2 1a, 2b Ds= 7g = poPo= agoPr= aq < ht done Py > 5 siet seulement sin & {1,2,3,4,5,6). raxonniement (connigés) sR6 nonce 2 vy, (On va prouver que le nombre T de triangles vérifie: 7 < 3S Soit done k € N. On peut supposer que & > 3, sans quoi il n'y a pas de triangle. Un segment de sommets u et v sera noté wv. Si S est un des segments, on note Ts le nombre de triangles ayant § pour cété. On a alors : Y1p=37. 5 De plus, le nombre de couples de triangles distinets ayant § pour c6té ‘commun est T3(Ts — 1) (on rappelle que dans un couple, Fordre est important). Par suite, le nombre de couples de triangles distincts ayant un cBté commun est: rts 0. Lemme : 7 Ona So Ty < 2k(k — 1). 5 Preuve: Choisissons un couple de segments distincts. Il y a k(k — 1) choix possibles Cas n°. On a choisi deux segments sans sommet commun (uv, 2). (On peut alors construire au plus 4 couples de triangles distinets ayant tun été commun, le premier de ces triangles avec le cbté wv, le second avec le cété xy. Is'agit des couples : (ux, xyu), (ux, xy), (uvy, xy), (ury, xy0). Réciproquement: ‘Tout couple de triangles distinets ayant un c6té commun sera généré deux fois par ce procédé. En effet, si (uv, xy) est un tel couple, il est obtenu par le choix (uv, xy) ei-dessus, mais comme xv et wy sont aussi des segments possibles (puisqur'ls servent & former des triangles !) il est aussi obtenu par le choix (xv, uy) (le choix (ux, ux) ne correspond pas & des segments sans sommet commun). Er inalement: 2D TT s - 1) < 4No () 5 oi No est le nombre de couples de segments sans sommet commun.Cas n°2. On a choisi deux segments distincts ayant un sommet com- mun (uv, ww). ‘Avec ces seuls trois points, on peut former au plus un couple de trian- gles ayant un c6té commun: (wow, ww). Réciproquement: ‘Tout triangle ww est généré de cette fagon. Mais le couple (new, zw) est en fait obtenu 6 fois, une pour chacun des couples de segments: (uv, au), (usu, ut), (vt, ete, (vi, v1e), (WH, 10), (wx, wn). Si l'on note Ny Je nombre de couples de segments distincts ayant un sommet commun, il vient alors: 6T 0 pour lesquels il existe une permutation équidistante sont les entiers pairs. Mais on va prouver un résultat plus fort: Pour tout 1 € 18", le nombre de permutations équidistantes d'ordre est (5), le nombre de diviseurs posiifs de 5 (avec bien sir (3) =0 si mest impair). Soit n € N*, pour laquelle il existe une distance midme, notée existe alors au moins une permutation équidistante o associé & c. On va prouver que o est unique. Lemme 1: Pour tout x € {1,...,¢}, ona (x) =x 46 et olx+e)=x. Prewve par récurence: On a(t) > 1, done €= jo(1) ~ 1] = o(1)—1, d’od oft) = 1+ e. Comme o est bijective, il existe un unique a {1,...,1} tel que ofa) = 1. Puisque a > 1, on ac = lola) — al = |1~ al = a~1, doi a=c+Lero(l +c =1 Supposons que le résultat soit vrai pour tout x < k, ott 1 < k < ¢ fixé, ‘Alors les nombres 1, ... A sont les images respectives de +0, .... e+e. On k4 1 < 1+c et o est bijective, done o(k +1) > k+ 1. Ainsi, c= lo(k+1)—(k+ I] =o(k + 1)—(k+ Detdoncolk+)=ke lee‘Comme ci-dessus ilexisteun uniqueb € (1, ...1}tel que a(b) = kel. Les images de 1, ..., k ont été déterminées et aucune n'est égale a k-+1 (cf. hypothése de récurrence). Done b > k +1. Par suite: c= |o{b) ~ bl =|k+1—b]=b—(k+ I) doub=cok+ let ofkslec=kel Cela assure lerésultat au rang k+1, et permet de conclure la récurrence. Lemme 2: Pour tout k € W tel que (2k + 2}e < my si2ke+ 1 2(k + Ie (comme ci-dessus, les nombres 1, ...,2(k + Ie ont déja été utilises ‘comme images). Done, m(x’) € N°. D'autre part, x(x’) < 1 puisque a(x) m. Contradiction. © Si o((2k + Ie) = -c+ 2k + Ie = 2 alors k > Let o((2k + 1}e) = 0((2k — 1)e) (ef. lemme 2). Puisque © est injective, on doit avoir (2k + 1)e = (2k — 1)es ce qui est impossible pour ¢ 4 0. 4 Il ne reste plus que n = 2ke, clest-a-dire un multiple de 2c, Mais alors le lemme 2 impose les valeurs de o{x) pour tout x € {1,....7t}, Cest-A-dire orest unique. Proposition 2: Soit n € N', Lentier ¢ > 1 est une distance miéme si et seulement si 2c divise 1. megamanPrewve : 8 Sic EN est une distance n-iéme, on vient de voir a la proposition 1 (que 2c divisait m. # Si 2c divise 7, la construction du lemme 2 est possible et ¢ est une distance n-itme, Ainsi puisque, d'aprés la proposition 1, il y a pour un n © N’ fixé autant de permutations équidistantes d'ordre 1 que de distances n- itmes, et que, d'aprés la proposition 2, ces distances r-iémes ne sont autres que les diviscurs positifs de > ‘ona le résultat souhaité. Le maximum cherché est C™!, Comme on va le voir, cela découle directement du théoréme suivant di a Sperner (1928). Notons quand méme que, lors d'une compétition du type OIM, ce théoréme p utilisé sans avoir été prouvé, ‘Théoréme: Soit § un ensemble a 7 > 1 éléments ct F une famille de sous- ensembles de S telle que A ¢ B pour tous A, B € F distinets. ‘Alors F ne contient pas plus de C””! éléments. Une jolie preuve de ce théoréme se trouve dans [4]. Pour le lecteur qui o'aurait pas eu la bonne idée de se procurer cette référence et pour {que ce livre soit auto-suffisant, en voici une autre qui suit la démarche de Sperner (et pour les détenteurs de Supermath, cela en fera une de plus...). Prewe Soit F une famille qui vérifie les hypothéses du théoréme (une telle famille sera dite spernienne). Pour tout r= 0,...,%,0n pose: A, = {A €F | Card) = 7} © SiA, = 6, sauf pour r= 65] c'est fini, tel que A, 7 g, on note £ le plus petit de ces entiers r. On pose alors : Bus ={BCS| ilexiste A € A, tol que AC Bet Card B= 141) et F=(F-A)UBra sassonement (Cong) » R8SiA,B © F distincts tels que A C B alors, d'aprés la minimalité de t et les propriérés de F, ona B&F — A, et A © Byy,d'o A= A'U {a} avec A’ € Ay. ‘Mais alors, A’ ¢ B. Contradiction. Done, F* est une famille spernienne et Card F" = Card F + Card Bar — Card A, (puisque F est spernienne, on a F By = #)- Comptons maintenant les couples (X,¥) ot X € Ay, ¥ € But ct Xcy: + Pour chaque X, on peut construire ensembles Y. Tout ¥ peut étre construit au maximum t+ 1 fois. Ainsi, (# — 1) Card(A,) < (t+ 1) Card(B,,4), C'est-&-dire : Card(Bya1) >" —f Cardy) > Cardia), cart < [5], ct alors Card(#") > Card(F). En répétant ce procédé un nombre fini de fois, on peut construire une famille spernienne d'au moins autant de membres que F, et dont au- cun n'a moins de 6] éments, Par une procédure analogue, on peut «éliminer> également toutes les parties contenant plus de Gi] éléments. (On est ramené au début de la preuve, et la conclusion s'en suit. Revenons a l'exercice. Soit $C [15 +00] une partic a m éléments. Pour toute partie A de S, fon note s(A) la somme des éléments de A, avec s(9) = 0. Soit I un intervalle ouvert de longueur 1. Lemme: iA, B sont deux parties distinctes de S telles que A C B, alors s(A) ou s(B) n'est pas dans I. Prewe: Si AC Bavee B A, alors il existe x € B — A. Et donc: (B) = x+5(B\{x}) x+s(A) 1+s(A) c'est-a-dire s(B) — s(A) > 1. Ainsi, (A) et (B) ne peuvent appartenir un méme intervalle ouvert de longueur 1. Et le lemme est prouvé. © migamatnOr, tout nombre de la forme )~ ;x; est la somme s(A) de la partie {A formée par les x, pour lesquels ¢, = 1. Du lemme, on déduit que e nombre de réels de cette forme que contient I ne peut dépasser le nombre de parties Ay, A2,... de S que l'on peut construire de telle facon qu'aucun des A, ne soit contenu dans un autre. Le théoréme de Sperner permet donc d'affirmer que I ne contient pas plus de od) réels du type souhaité. Ceci étant vrai pout des 1 et § arbitrairement choisis dans le cadre de 'énoneé, le maximum cherché ne dépasse done pas col Réciproquement : Soient n € Nt et p N, tels que 6] <2. Pour i= 1,...eron pose xj = 1+ <1. Hest clair qu'alors les x; sont Da deux a deux distinets et appartiennent a [1, +00[ « Soit A.C {2e1.-.+%} une partic a [5] éléments. Alors: G] 1, pour tout i, Parmi les 2" possibles combinaisons linéaires de la forme J €,a, 03 €; € {1,1}, le nombre maximum qui or appartiennent 4 une boucle ouverte de rayon 1 est CI, I n'est pas difficile de voir que Vexercice ci-dessus se raméne au cas - Cocas a été résolu par Erdés, qui n'a pas réussi a conclure pour d= 2. Cest finalement Kleitman qui a atteint le cas général (et méme bien plus), et de fagon « Références: [1] D. Kleitman, «On a lemma of Littlewood and Offord on the distri- bution of linear combinations of vectors», Advances Math., 5 (1970), p. 155-157. [2] P. Erdés, «On a lemma of Littlewood and Offord», Bull. Amer. Math. Soc., 5 (1945), p. 898-902. [3] M. Aigner, G. M. Zeigler, Proofs from The Book, Springer, p. 117-120, [4] P, Bornsztein, Supermath, Vuibert, p. 105-106.Non. RQ Test clair que m = 2 ne convient pas. On impose done » > 3. Par V'absurde: Supposons qu'il existe des sous-ensembles Ay,.... A, de N° vérifiant les conditions de l'énoncé. Propriété 1: Soit k € {1,....1} fixé. Pour tous a, b,¢ de At, avec a 7b, les nombres a-+¢ et b +c appartiennent au méme A. Prewve : Par symétric, il sufft de prouver la propriété pour k Soient a,b,c € Ar, aveca 4b. Soient 23,43, avec 4, € A; pour tour é ¢ Si l'un des nombres a +¢ ou b + est dans A, mais pas l'autre; par exemple a+c€ A; ctb+e€ Ar: Posons m= 4b 4640) +044 -.-+Ay +4 +0 4a Puisque b+ a2 44 +...+ a, € Ay, on en déduit que m= (a40)4 (D4, 444... 4 dy) #04 +--+ dy EAD Mais a+ a2 +454 ...4a, € Ay également. Ft alors: m= (b+ 0)+ (04a, 4044... 4 0g) 6054-04 ay EAL Ce qui contredit que Ay Az = #. 4 Si les nombres a + ¢ et b+ ¢ n'appartiennent pas au méme A; et qu'aucun des deux n'est dans A, ; par exemple, a+c © Az et b+c € Aa: Posons p= a+b4c+04+...+4,- Ona alors Pabslasc)tayt... 40, Az et p=a4(b+e) ay... 4 dy Ar ce qui contredit que Az 1.A3 = #- Ainsi, a +c et b+ sont dans le méme A, . Ft la propriété est prouvée. sassoroiement (corngis) 5Soient 44,42, -.-4y avec a; € A, pour t ti On pose S = a) 442+...44,.. Et par symétrie, on peut toujours supposer queS€ Ay Pour tout i, on note b, = § —a;. On peut noter alors que b; € A, pour tout i. Propriété 2: ‘A, contient tous les entiers pairs. Preuve: Pour tout i¢ {1.....7}: Sia, =b,,alors 2a, = Se Ay. # Sia, 4b, alors, d’aprés la propriété 1, les nombres a, + a; et a, +, sont dans le méme sous-ensemble. Puisque § € Ay , on a done 2a; € Ay - ‘Ainsi, dans tous les cas, 2a; € Ay. Or, ceci est vrai pour tout i et Je choix de a, dans A, est arbitraire. Done, pour tout entier x > 1, on 2x € Ay, comme annoncé. I découle de la propriété 2 que a, est impair pour i > 2. Mais alors, puisque 24 a) +24 +...+a, € Ap, il faut que » soit impair (sans quoi on aurait un nombre pair dans Az). Propriét ‘A, ne contient que des nombres pairs, et les contient rous. Preuve: On sait déja que Ay contient tous les nombres pairs. Puisque ay +43+...+, € Az, que est impairet que a est impair pour i> 3,[Link] a; pait. Et ce, pour un choix arbitraire de a € Ay D’oii la conclusion. Soient a2, ...,dy, avec a; € A; pour tout jet p € N’ ; on a done 2p rays... 4ay Az ct 2P4an+aq4... dy EAs Lorsque p décrit N*, on en déduit que Az contient tous les nombres impairs & partir de 2+a3 +...+a, et que A3 contient tous les nombres npairs & partir de 2+ a2 +4 +...+dq. Mais alors Az et As ne sont pas disjoints ! ‘On a notre contradiction, et la conclusion s'en suit.Soient 1, k des entiers avec 0 < k fli — 1), cest--dire fli) — fi ~ 1) = 1. Puisque 0) = 0 ct fin) = &, on colorie ainsi exactement k points. ‘Montrons que ce coloriage est presque uniforme: On remarque tout d'abord que pour tout entier a, on a fla+n) = fla)+k etdone fla+n)—fla—1+n) = fla)~fla—1) (notons que cela assure que, si 'on parcourt le polygone plusieurs fois, on ne colorie pas d'autre sommet que ceux coloriés au premier tour). Par suite, si M est un ensemble de mt (avec 1 < m < 1) sommets cconsécutifs Past, +--+ Peams & Si S(M) désigne le nombre de sommets coloriés de M, on a donc: sim) = 3 fla) ~ fla —1) = fla +m) — fla). w fat On pose p = [mcr]. On vérifiefacilement qu'alors, pour tout entier a: fla)+p 2 fixé. Supposons que le résultat soit vrai pour tout p-gone, 00 OL. Preuve par Vabsurde: Supposons que L > €+2. Par exemple, € est donne pat les sommets S;, S2...-. Scar et L est donné par les sornmets Sasts+-+Sgutet~ I n'y a done aucun point colorié entre $} et Srs1s ni entre Sya1 et Syatat (Ces quatre points étant coloriés). Soient alors My = {S15 ---» Seer} et Ma = {Ses2s --+1 Sastaz}- ‘My et My sont deux ensembles de £4 1 sommets consécutifs, mais S(M,) = 2 et S(Mp) = 0, ce qui contredit que le coloriage est presque uniforme. Done, L < € + 1, et le lemme est prouvé. On note que si L = é, le coloriage est régulier (points coloriés réguligrement espacés) et qu‘alors le résultat est évident. On supposera done que = € +1 Les points coloriés découpent le polygone en k arcs consécutifs de longueurs € ou € + 1. Soit r le nombre de ces ares de longueur € +1. Ona donc r > 1. De plus, en comptant le nombre total de points, on an = RE +r. Et, puisqu'au moins un arc est de longueur €, onan < (C+ 1); doar 2et 1 2 et que aber Dans ce nouveau coloriage, les nt sommets sont 1 ares consécutifs dans lancien coloriage. A partir de My , on construit ensemble Ey de tous les points contenus dans les mt arcs définis par M, , exceptés les deux points extrémes. Ces deux points extrémes sont des points coloriés dans le coloriage initial du r-gone. Ey est donc un ensemble de m€ +a—1 sommets consécutifs du r-gone dont exactement m ~ 1 sont coloriés. mégamate