European Girls' Mathematical Olympiad (EGMO) 2012 :

Voir le sujet précédent Voir le sujet suivant Aller en bas

European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  G. Lorang le Mar 17 Avr - 11:32

JOUR 1 :

Problème 1. Soit `ABC` un triangle dont le centre du cercle circonscrit est `O`. Les points `D`, `E` et `F` sont
respectivement situés à l’intérieur des segments `[BC]`, `[CA]` et `[AB]` tels que `DE` soit perpendiculaire à `CO` et
`DF` soit perpendiculaire à `BO` (Par intérieur, nous voulons dire, par exemple, que le point D se trouve sur la
droite `BC` et que `D` est situé entre `B` et `C`).
Soit `K` le centre du cercle circonscrit du triangle `AFE`. Prouver que les droites `DK` et `BC` sont perpendiculaires.

Problème 2. Soit `n` un entier strictement positif. Trouver le plus grand entier positif `m` satisfaisant la propriété
suivante : un tableau à `m` lignes et `n` colonnes peut être rempli par des nombres réels afin que pour toute paire
de lignes `[a_1, a_2,..., a_n]` et `[b_1, b_2,..., b_n]` on ait que
`max(|a_1 − b_1|, |a_2 − b_2|,...,|a_n − b_n|) = 1`.

Problème 3. Trouver toutes les fonctions `f : RR ->RR` telles que
`f(yf(x + y) + f(x))= 4x + 2yf(x + y)`,
pour tout `x, y in RR`.

Problème 4. Un ensemble `A` d’entiers est dit somme-clos si `A sub A+A`, c-à-d tout élément `a in A` est la somme
de deux éléments `b, c in A` (qui ne sont pas nécessairement distincts). Un ensemble `A` d’entiers est dit somme-nulle-
absente si 0 est le seul entier qui ne peut s’exprimer comme la somme des éléments d’un sous-ensemble
fini non-vide de A.
Existe-t-il un ensemble d’entiers qui soit somme-clos et somme-nulle-absente ?

JOUR 2 :

Problème 5. Les nombres premiers `p` et `q` satisfont
`p/(p + 1)+(q + 1)/q=(2n)/(n + 2)`
pour un certain nombre entier strictement positif `n`. Trouver toutes les valeurs possibles de `q − p`.


Problème 6. Il y a un nombre infini de personnes enregistrées sur le réseau social Facedebouc. Des paires
d’utilisateurs sont enregistrées comme amis, mais chaque personne ne peut avoir qu’un nombre fini d’amis.
Chaque utilisateur possède au moins un ami. (L’amitié est symétrique ; c-à-d que si A est un ami de B, alors
B est aussi un ami de A.)
Toute personne doit désigner un de ses amis comme étant son meilleur ami. Si A désigne B comme étant son
meilleur ami, il ne s’en suit (malheureusement) pas que B choisisse nécessairement A pour meilleur ami. Une
personne désignée meilleur ami est appelée 1-meilleur ami. Plus généralement, si `n > 1` est un entier positif,
alors un utilisateur est appelé `n`-meilleur ami si et seulement si il est désigné meilleur ami par un `(n−1)`-meilleur
ami
. Quelqu’un qui est `k`-meilleur ami pour tout entier strictement positif `k` est appelé populaire.
(a) Prouver que toute personne populaire est le meilleur ami d’une autre personne populaire.
(b) Montrer que si on pouvait avoir un nombre infini d’amis, il serait possible qu’une personne populaire ne
soit le meilleur ami d’aucune autre personne populaire.

Problème 7. Soit `ABC` un triangle acutangle dont le cercle circonscrit est nommé `Gamma` et l’orthocentre `H`. Soit
`K` un point de `Gamma` tel que `A` et `K` soient situés de part et d’autre de `BC`. Soit `L` le symétrique de `K` par rapport
à `AB` et `M` le symétrique de `K` par rapport à `BC`. Soit `E` le second point d’intersection de `Gamma` avec le cercle
circonscrit au triangle `BLM`. Montrer que les droites `KH`, `EM` et `BC` sont concourantes. (L’orthocentre d’un
triangle est l’intersection de ses hauteurs.)

Problème 8. Un mot est une suite finie de lettres d’un certain alphabet. Un mot est répétitif s’il est la
juxtaposition d’au moins deux séquences identiques (par exemple ababab et abcabc sont répétitifs, mais ababa et
aabb ne le sont pas). Prouver que si un mot a la propriété qu’en interchangeant toute paire de lettres adjacentes,
on obtient un mot répétitif, alors toutes ses lettres sont identiques. (On peut interchanger deux lettres adjacentes
identiques laissant ainsi le mot inchangé).
avatar
G. Lorang
Admin

Messages : 325
Date d'inscription : 07/05/2010
Localisation : LMR-L

Voir le profil de l'utilisateur http://lmrl-maths.forumactif.com

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  carole le Mar 17 Avr - 14:09

Je connais quelques résultats, mais les démonstrations c' est autre chose... De plus les problèmes 4 et 8 n' ont pas été résolus entièrement par aucune des participantes...

Pour le problème 4, on peut montrer qu' il existe de tels ensembles.
Supposons que chaque élément est la somme des deux éléments précédents (cf. Suite de Fibonacci).
On a alors `a_0+a_1=a_2`, `a_1+a_2=a_3`...
d' où on a également `a_0=a_2-a_1` etc.
Entre autre on peut considérer les nombres de Fibonnacci et leurs relatifs.
`1, 1, 2, 3, 5, 8, 13...`
Si on choisit maintenant alternativement un nombre positf et négatif de cette suite, on reçoit une suite somme-clos.
p.ex.:
1, -2, 3, -5, 8, -13,...
Or, on peut montrer que cette suite/cet ensemble est également somme-nulle-absente. (Je pense que ceci a valu 1 ou 2 points si c' était bien clair rédigé)

Remarque:
On ne doit pas choisir le même nombre pour un ensemble somme-nulle-absente, ni un nombre et son relatif dans un même ensemble.

Je continuerais plus tard...
avatar
carole
Expert
Expert

Messages : 181
Date d'inscription : 11/05/2010
Age : 24

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Suite problème 4

Message  carole le Mar 17 Avr - 16:34

Je ne sais pas si l' idée suivante sera utile ou non...
Comme on a choisi les éléments tels qu' en valeur absolue la somme de deux éléments consécutifs donne le suivant.
On peut exprimer `a_n=-a_(n-1) a_(n-2)=2*a_(n-2)-a_(n-3)=...
Remarquons que les coefficients des `a_n` appartiennent de nouveau à la suite de Fibonacci! (Je ne suis pas sûre si ceci est relevant pour la démonstration...)
On pourrait donc réduire toute somme des éléments à une expression de la forme `x*1 y*(-2)` où x et y sont des entiers relatifs (car on a choisi le premier terme 1 et le deuxième -2).
Pour obtenir une somme-nulle, il faudrait que `x=2*y`.


Comme on a des éléments positifs et négatifs dans notre ensemble, il faudrait essayer de minimiser la différence entre la somme de x éléments positifs et de y éléments négatifs. (Je travaille en valeurs absolues dans la suite)
Or, on peut exprimer un élément d' indice de parité donnée par la somme des tous les éléments dont l' indice est le l' autre parité plus 1.
Ceci est bien vrai, car `a_n=a_(n-1)+a_(n-2)=a_(n-1)+a_(n-3)+a_(n-4)=a_(n-1)+a_(n-3)+a_(n-5)+...+1` (dans la suite de Fibonacci on utilise le 1 deux fois (`a_n` est le n-ième terme de cette suite), alors qu' ici on ne peut l' utiliser qu' une seule fois)
Par ceci, on sait que la somme minimale qu' on peut obtenir dans cet ensemble est 1 et donc l' ensemble est également somme-nulle-absente!

Je ne sais pas si ceci est bien une démonstration où non. Si quelqu'un trouve un argument manquant, il peut bien sur le commenter Wink
avatar
carole
Expert
Expert

Messages : 181
Date d'inscription : 11/05/2010
Age : 24

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Mar 17 Avr - 21:53

Coucou Carole,

J'ai eu l'occasion de faire les problèmes plus ou moins en direct car j'ai trouvé le site du concours et ils ont publié les problèmes. Je n'avais pas pensé à Fibonacci et je n'avais pas trouvé la réponse de ce problème 4. Je n'ai pas non plus trouvé celle du problème 3 dans lequel je parviens juste à prouver que `f(x)=2x` est la seule solution continue. Je pense que j'ai trouvé les solutions des autres problèmes.

Dur dur ce problème 4. J'étais parti sur une mauvaise voie, sur celle d'essayer de montrer qu'un ensemble d'entiers à la fois somme-clos et somme-nulle-absente n'existe pas. Maintenant que tu parles de Fibonacci, je vois pourquoi cela existe.

Attention quand même à ta preuve. Tu dis que `a_n` est la somme de tous les `a_i` tels que `i` est inférieur à `n` et de parité différente de `n` augmentée d'une unité. Je suis tout à fait d'accord avec cela. Mais ce `a_n` est seul et il se pourrait a priori qu'une somme de plusieurs `a_i` d'indice pair soit égal à une somme de `a_i` d'indice impair. Comment contres-tu cela ?

Voici une piste : montrer que tout nombre entier naturel s'écrit d'une et d'une seule façon comme somme de termes deux à deux distincts et non consécutifs de la suite de Fibonacci (d'origine). On peut alors déduire immédiatement qu'une somme de termes d'indice impair ne peut égaler une somme de termes d'indice pair.

Après, il reste encore à montrer que tous les nombres entiers non nuls sont une somme de termes de la suite de Fibonacci modifiée (avec un signe - tous les deux termes). Je suis par contre convaincu que cette suite est somme-clos par ce que tu as dit.

Veux-tu que j'écrive les solutions des problèmes 1, 2, 5, 6, 7 et 8 ou préfères-tu encore chercher ? As-tu une solution du problème 3 ?

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Mer 18 Avr - 12:38

Solution du problème 5

Comme `\frac{p}{p+1}+\frac{q+1}{q}=\frac{2n}{n+2}`, il vient `1-\frac{1}{p+1}+1+\frac{1}{q}=2-\frac{4}{n+2}`, puis `\frac{1}{p+1}-\frac{1}{q}=\frac{4}{n+2}` et donc `\frac{q-p-1}{q(p+1)}=\frac{4}{n+2}`. On va réduire la fraction `\frac{4}{n+2}` mais cela engendre trois cas possibles.

Cas 1 : le nombre `n` s'écrit sous la forme `4k+2` pour un nombre entier naturel `k`. L'équation devient alors `\frac{q-p-1}{q(p+1)}=\frac{1}{k+1}`. Comme le second membre est une fraction irréductible, il existe un nombre entier `a` tel que `q-p-1=a` et `q(p+1)=a(k+1)`. Il est même nécessaire que `a` soit strictement positif pour que `q(p+1)=a(k+1)` possède une solution. De l'équation `q-p-1=a`, on tire `p+1=q-a` et on le substitue dans l'équation `q(p+1)=a(k+1)`. On obtient `q(q-a)=a(k+1)`. Mais cela implique que le nombre `a` (entier strictement positif) divise le produit `q(q-a)`. Comme le nombre `q` est un nombre premier, si `a` ne divise pas `q`, alors `a` divise `(q-a)` et donc aussi `q=(q-a)+a`. Bref, le nombre `a` doit diviser le nombre `q`. Donc `a=1` ou `a=q`. On vérifie tout de suite que `a=q` est impossible car cela implique que `k` est strictement négatif. Donc `a=1`. Mais alors `q-p-1=1` et donc `q-p=2`. L'équation initiale est satisfaite pour `p=3`, `q=5` `n=78` (par exemple).

Cas 2 : le nombre `n` s'écrit sous la forme `4k` pour un certain entier strictement positif `k`. L'équation devient alors alors `\frac{q-p-1}{q(p+1)}=\frac{2}{2k+1}`. Comme le second membre est une fraction irréductible, il existe un nombre entier `a` tel que `q-p-1=2a` et `q(p+1)=a(2k+1)`. Il est même nécessaire que `a` soit strictement positif pour que `q(p+1)=a(2k+1)` possède une solution. De l'équation `q-p-1=2a`, on tire `p+1=q-2a` et on le substitue dans l'équation `q(p+1)=a(2k+1)`. On obtient `q(q-2a)=a(2k+1)`. Mais cela implique que le nombre `a` (entier strictement positif) divise le produit `q(q-2a)`. Comme le nombre `q` est un nombre premier, si `a` ne divise pas `q`, alors `a` divise `(q-2a)` et donc aussi `q=(q-2a)+2a`. Bref, le nombre `a` doit diviser le nombre `q`. Donc `a=1` ou `a=q`. On vérifie tout de suite que `a=q` est impossible car cela implique que `k` est strictement négatif. Donc `a=1`. Mais alors `q-p-1=2` et donc `q-p=3`. Remarquons alors que `p` et `q` sont de parités différentes avec `q>p`, donc que `p=2`, puis que `q=2+3=5`. Dans ce cas, l'équation initiale est satisfaite pour `n=28`.

Cas 3 : le nombre `n` s'écrit sous la forme `2k+1` pour un certain entier naturel `k`. L'équation devient alors alors `\frac{q-p-1}{q(p+1)}=\frac{4}{2k+3}`. Comme le second membre est une fraction irréductible, il existe un nombre entier `a` tel que `q-p-1=4a` et `q(p+1)=a(2k+3)`. Il est même nécessaire que `a` soit strictement positif pour que `q(p+1)=a(2k+3)` possède une solution. De l'équation `q-p-1=4a`, on tire `p+1=q-4a` et on le substitue dans l'équation `q(p+1)=a(2k+3)`. On obtient `q(q-4a)=a(2k+3)`. Mais cela implique que le nombre `a` (entier strictement positif) divise le produit `q(q-4a)`. Comme le nombre `q` est un nombre premier, si `a` ne divise pas `q`, alors `a` divise `(q-4a)` et donc aussi `q=(q-4a)+4a`. Bref, le nombre `a` doit diviser le nombre `q`. Donc `a=1` ou `a=q`. On vérifie tout de suite que `a=q` est impossible car cela implique que `k` est strictement négatif. Donc `a=1`. Mais alors `q-p-1=4` et donc `q-p=5`. Remarquons alors que `p` et `q` sont de parités différentes avec `q>p`, donc que `p=2`, puis que `q=2+5=7`. Dans ce cas, l'équation initiale est satisfaite pour `n=19`.

Conclusion : `q-p` vaut nécessaire `2`, `3` ou `5`.

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Mer 18 Avr - 13:25

Solution du problème 2

On va montrer que le plus grand entier `m` recherché vaut `2^n`.

Tout d'abord, on va prouver qu'il existe un tableau de `2^n` lignes et `n` colonnes satisfaisant la propriété de l'énoncé. Il suffit de considérer un tableau dont les lignes sont tous les `n`-uplets de `\{0;1\}`. Il y a `2^n` `n`-uplets de cette sorte donc le tableau possède `2^n` lignes. Considérons deux lignes distinctes arbitraires `[a_1,a_2,\ldots,a_n]` et `[b_1,b_2,\ldots,b_n]` de ce tableau. Il existe au moins un nombre `k\in\{1,2,\ldots,n\}` tel que `a_k\ne b_k` puisque les deux lignes sont des `n`-uplets différents. On a donc l'égalité `|a_k-b_k|=1`. De plus, il est clair que `a_i-b_i\in\{-1;0;1\}` pour tout `i\in\{1,2,\ldots,n\}` et donc que `|a_i-b_i|\leq 1=|a_k-b_k|` pour tout `i\in\{1,2,\ldots,n\}`. On a donc bien `\max\{|a_1-b_1|,|a_2-b_2|,\ldots,|a_n-b_n|\}=|a_k-b_k|=1`.

Ensuite, on va considérer un tableau arbitraire de `2^n+1` lignes et `n` colonnes et on va prouver que la condition de l'énoncé n'est pas vérifiée. On peut supposer que, pour tout `i\in\{1,2,\ldots,n\}`, il existe un nombre réel `x_i` tel que tous les nombres de la colonne numéro `i` du tableau sont compris dans un intervalle du type `[x_i;x_i+1]` (en effet, si ce n'est pas le cas pour la colonne `i`, on peut trouver deux lignes `[c_1,c_2,\ldots,c_n]` et `[d_1,d_2,\ldots,d_n]` du tableau pour lesquelles `\max\{|c_1-d_1|,|c_2-d_2|,\ldots,|c_n-d_n|\}\geq|c_i-d_i|>1`, ce qui implique que la condition de l'énoncé n'est pas vérifiée). Considérons alors tous les ensembles de la forme `[y_1;y_1+0,5]\times[y_2;y_2+0,5]\times\cdots\times[y_n;y_n+0,5]` où `y_i\in\{x_i\;x_i+0,5}` quel que soit `i\in\{1,2,\ldots,n\}`. Cela fait `2` choix pour `y_i` pour chaque valeur de `i\in\{1,2,\ldots,n\}`, et donc `2^n` ensembles en tout. De plus, ces `2^n` ensembles recouvrent entièrement l'ensemble `[x_1;x_1+1]\times[x_2;x_2+1]\times\cdots\times[x_n;x_n+1]`. Donc, par le principe des tiroirs, au moins un de ces `2^n` ensembles contient au moins `2` des `2^n+1` `n`-uplet de nombres que forment les lignes du tableau. On peut donc trouver deux lignes distinctes `[e_1,e_2,\ldots,e_n]` et `[f_1,f_2,\ldots,f_n]` du tableau telles que `|e_i-f_i|\leq 0.5` pour tout `i\in\{1,2,\ldots,n\}`. Mais on alors `\max\{|e_1-f_1|,|e_2-f_2|,\ldots,|e_n-f_n|\}\leq 0.5<1`, ce qui contredit la propriété de l'énoncé.

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Mer 18 Avr - 15:12

Solution du problème 1



Par facilité d'écriture, j'utilise la notation `XY` pour désigner le vecteur libre qui possède `X` comme origine et `Y` comme extrémité.

On cherche à démontrer que le produit scalaire `KD*BC` est nul. On va d'abord chercher à chasser le point `K` de cette expression en faisant intervenir le fait qu'il est sur la médiatrice du segment `[AF]` et sur la médiatrice du segment `[AE]`.
On a : `KD*BC`
`=KD*(BA+AC)`
`=KD*BA+KD*AC`
`=(KF+FD)*BA+(KE+ED)*AC`
`=KF*BA+FD*BA+KE*AC+ED*AC`
`=(KF+KA-KA)*BA+FD*BA+(KE+KA-KA)*AC+ED*AC`
`=(KF+KA)*BA-KA*BA+FD*BA+(KE+KA)*AC-KA*AC+ED*AC`
`=0-KA*BA+FD*BA+0-KA*AC+ED*AC`
car `K` est sur la médiatrice du segment `[AF]` inclus dans la droite `AB` et sur la médiatrice du segment `[AE]` inclu dans la droite `[AC]`.
On a donc : `KD*BC`
`=-KA*BA+FD*BA-KA*AC+ED*AC`
`=-KA*(BA+AC)+FD*BA+ED*AC`
`=-KA*BC+FD*BA+ED*AC`
`=-(KD+DA)*BC+FD*BA+ED*AC`
`=-KD*BC-DA*BC+FD*BA+ED*AC.`
On a donc : `2(KD*BC)=-DA*BC+FD*BA+ED*AC` et le point `K` a été définitivement chassé de l'expression qu'on va continuer à manipuler.

On va mainenant faire apparaître le point `O` pour jouer sur la perpendicularité des droites `DF` et `BO`, sur la perpendicularité des droites `DE` et `CO`, mais aussi sur le fait `O` soit sur les médiatrices des côtés du triangle `ABC`.
Il vient : `2(KD*BC)`
`=-DA*BC+FD*BA+ED*AC`
`=-DA*(BO+OC)+FD*(BO+OA)+ED*(AO+OC)`
`=-DA*BO-DA*OC+FD*BO+FD*OA+ED*AO+ED*OC`
`=-DA*BO-DA*OC+0+FD*OA+ED*AO+0`
`=-(DF+FA)*BO-(DE+EA)*OC+FD*OA+ED*AO`
`=-DF*BO-FA*BO-DE*OC-EA*OC+FD*OA+ED*AO`
`=0-FA*BO+0-EA*OC+FD*OA+ED*AO`
`=-FA*(BO+AO-AO)-EA*(OC+OA-OA)+FD*OA+ED*AO`
`=-FA*(BO+AO)+FA*AO-EA*(OC+OA)+EA*OA+FD*OA+ED*AO`
`=0+FA*AO+0+EA*OA+FD*OA+ED*AO`
car `O` est sur la médiatrice du segment `[AB]` inclus dans la droite `AF` et sur la médiatrice du segment `[AC]` inclu dans la droite `[AE]`.

On a donc : `2(KD*BC)`
`=FA*AO+EA*OA+FD*OA+ED*AO`
`=FA*AO+AE*AO+FD*OA+DE*OA`
`=(FA+AE)*AO+(FD+DE)*OA`
`=FE*AO+FE*OA`
`=FE*(AO+OA)`
`=0`.
Donc les droites `KD` et `BC` sont perpendiculaires.

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  carole le Mer 18 Avr - 16:29

Je n' ai pas encore de réponse pour la question 3, je n' aime pas trop les équations fonctionnelles, mais je pense qu' il n' y avait pas d' autres solutions que la solution `f(x)=2x` .

Revenons au problème 4; le_magicien a écrit:
Attention quand même à ta preuve. Tu dis que `a_n` est la somme de tous les `a_i` tels que i est inférieur à n et de parité différente de n augmentée d'une unité. Je suis tout à fait d'accord avec cela. Mais ce `a_n` est seul et il se pourrait a priori qu'une somme de plusieurs `a_i` d'indice pair soit égal à une somme de `a_i` d'indice impair. Comment contres-tu cela ?

Voici une piste : montrer que tout nombre entier naturel s'écrit d'une et d'une seule façon comme somme de termes deux à deux distincts et non consécutifs de la suite de Fibonacci (d'origine). On peut alors déduire immédiatement qu'une somme de termes d'indice impair ne peut égaler une somme de termes d'indice pair.

C' est un peu de tavail...
Notons `ul(n)` la plus grand nombre de la suite de Fibonacci inférieur ou égal à `n`.
Donc on a `n=ul(n)+k` où k est strictement inférieur au premier nombre de Fibonacci inférieur à `ul(n)`.
Or, d' ici on sait que si k peut s' exprimer par des nombres de Fibonacci non-consécutifs, alors forcément n peut s' exprimer également par une telle somme, car k est plus petit que le premier nombre de Fibonacci inférieur à `ul(n)`.
Il suffit donc de montrer que k peut s' exprimer ainsi, et on peut descendre jusqu' au cas où k=1. Or, si on commence la suite par 0,1,1,1,2,3,5,... il est évident qu' on peut exprimer k avec deux autres nombres de Fibonacci non-consécutifs.

C' est un peu confus, mais je ne trouve pas mieux pour le moment...
avatar
carole
Expert
Expert

Messages : 181
Date d'inscription : 11/05/2010
Age : 24

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Mer 18 Avr - 16:44

Solution du problème 6

(b) Considérons la situation suivante. Les personnes sur le réseau Facedebouc sont les éléments de l'ensemble infini `\{(i,j) : i,j\in\mathbb{N}, 0<i\leq j \}\cup\{(0,0);(0,1);(1,0)\}` et tout le monde est ami avec tout le monde (ce qui est possible puisqu'on peut avoir une infinité d'amis). Pour tous entiers `i,j` strictement positifs et tels que `i<j`, `(i,j)` choisit `(i+1,j)` comme meilleur ami. Pour tous entiers `j` strictement positifs, `(j,j)` choisit `(0,0)` comme meilleur ami. Et finalement, `(0,0)` choisit `(1,0)` comme meilleur ami, `(1,0)` choisit `(0,1)` comme meilleur ami et `(0,1)` choisit `(1,0)` comme meilleur ami.

Tout le monde a bien un meilleur ami. Il est clair que `(0,0)` est populaire car il est le meilleur ami de `(1,1)` et que, pour tout entier `j>1`, `(j,j)` est un `(j-1)`-meilleur ami dont `(0,0)` est le meilleur ami. De plus, `(0,0)` n'est le meilleur ami d'aucune personne populaire (seuls `(0,0)`, `(1,0)` et `(0,1)` sont populaires).

(a) Soit `x` une personne populaire. Comme on ne peut avoir qu'un nombre fini d'amis et que pour être populaire il faut être un `n`-meilleur ami pour une infinité de valeurs de `n`, le principe des tiroirs (dans le cas infini) implique qu'il existe un ami `y` de `x` qui a désigné `x` comme meilleur ami et qui est lui-même un `(n-1)`-meilleur ami pour une infinité de valeurs de `n`. Il suffit de prouver que `y` est populaire pour terminer ce problème. En fait, il suffit même de se donner un nombre entier strictement positif `m` arbitraire et de mettre en évidence que `y` est un `m`-meilleur ami pour terminer ce problème. Or, `y` est un `(n-1)`-meilleur ami pour une infinité de valeurs de `n`, alors il existe un nombre `k` tel que `k\geq m` et que `y` est un `k`-meilleur ami. Il existe donc une suite de personnes `z_1`, `z_2`, `ldots`, `z_{k}` telles que `z_i` désigne `z_{i+1}` comme meilleur ami pour tout `i\in\{1,2,\ldots,k-1\}` et que `z_k` désigne `y` comme meilleur ami. Mais alors, comme `1\leq k\leq m`, on peut dire que la sous-suite `z_{k-m+1}`, `z_{k-m+2}`, `\ldots`, `z_k` prouve que `y` est un `m`-meilleur ami, ce qui termine le problème.

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Mer 18 Avr - 17:54

carole a écrit:
Notons `ul(n)` la plus grand nombre de la suite de Fibonacci inférieur ou égal à `n`.
Donc on a `n=ul(n)+k` où k est strictement inférieur au premier nombre de Fibonacci inférieur à `ul(n)`.
Or, d' ici on sait que si k peut s' exprimer par des nombres de Fibonacci non-consécutifs, alors forcément n peut s' exprimer également par une telle somme, car k est plus petit que le premier nombre de Fibonacci inférieur à `ul(n)`.
Il suffit donc de montrer que k peut s' exprimer ainsi, et on peut descendre jusqu' au cas où k=1. Or, si on commence la suite par 0,1,1,1,2,3,5,... il est évident qu' on peut exprimer k avec deux autres nombres de Fibonacci non-consécutifs.

C' est un peu confus, mais je ne trouve pas mieux pour le moment...

C'est bon jusque là. Very Happy Tu montres l'existence de la décomposition par récurrence en quelque sorte. Tu peux commencer ta suite par 1, 2, 3, 5 (pas besoin de trois 1).
1=1
2=2
3=3
4=1+3
5=5
6=1+5
7=2+5
8=8
etc

Maintenant, il reste à montrer que cette décomposition est unique. S'il faut représenter `n`, on est obligé d'utiliser `ul(n)` (sinon, ce qu'on construit n'est pas assez grand pour représenter `n` (ni même `ul(n)`)). Une fois cette obligation faite, il reste à représenter `n-ul(n)` mais encore une fois on devra choisir le plus grand terme de Fibonacci qui soit inférieur ou égal à ce nombre. Et ainsi de suite, on n'a pas de liberté, il y a unicité. Mais il faut absolument commencer par 1,2,3,5 (et pas par 1,1,2,3,5 par exemple) pour cette unicité.

En gros, pour le problème 4, on n'a plus qu'à prouver qu'on peut représenter tout nombre entier non nul avec la suite de Fibonacci modifiée (celle dont on change le signe d'un terme sur deux) et on aura fini. On vient de prouver que 0 ne se représente pas et tu avais déjà prouvé que c'est somme-clos.

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Mer 18 Avr - 18:26

Solution du problème 7



Comme le triangle `ABC` est acutangle, `H` est à l'intérieur du triangle `ABC`. Les points `H` et `K` sont donc de part et d'autre de la droite `BC` et les droits `HK` et `BC` sont donc sécantes en un point `Y`. Le problème revient à démontrer que `Y` est sur la droite `EM`.

On va démontrer que le symétrique orthogonal `X` par la droite `[BC]` de `H` est sur le cercle circonscrit du triangle `ABC`. En fait, l'angle `|BXC|` vaut l'angle `|BHC|` (puisque c'est son symétrique par construction) qui vaut lui-même `180°-|HBC|-|HCB|=(90°-HBC)+(90°-HCB)=|ACB|+|ABC|` (puisque `BH` et `CH` sont perpendiculaires respectivement à `AC` et `AB`). Mais alors `|BAC|+|BXC|=|BAC|+|ACB|+|ABC|=180°`, ce qui prouve que le quadrilatère `ABXC` est inscriptible et donc que `X` se trouve sur le cercle circonscrit du triangle `ABC`.

Cela étant, comme `M` est de plus le symétrique orthogonal de `K` par la droite `BC`, la droite `XM` est le symétrique orthogonal de la droite `HK` par la droite `BC`. Donc `Y` est sur la droite `XM`. Le problème revient donc à démontrer que `X` est sur la droite `EM`.

Il vient (ce sont des angles) : `|CEM|=|CEB|-|MEB|=|CAB|-|MLB|` car les quadrilatères `EBCA` et `ELBM` sont inscriptibles. Or, `B` est le centre du cercle circonscrit au triangle `KML` et on a donc `|MLB|=|MLK|+|KLB|=|MBK|/2+(180°-|KBL|)/2=|KBC|+90°-|KBA|=90°-|CBA|`.
On obtient donc `|CEM|=|CAB|-90°+|CBA|=(180°-|CAB|-|CBA|-|ACB|)+|CAB|-90°+|CBA|=90°-|ACB|`. On vient en fait de prouver que l'arc intercepté par l'angle `CEM` sur le cercle circonscrit au triangle `ABC` ne dépend pas de la position de `K` sur l'arc `(BC)` une fois que le triangle `ABC` est fixé. Cela étant, on peut se restreindre à démontrer que `X` est sur la droite `EM` pour une position particulière de `K` sur le petit arc `(BC)`.

Choisissons `K` comme étant le symétrique orthogonal `X` de `H` par la droite `BC`. Dans cette configuration particulière, le point `M` est alors le point `H` et le point `E` est le point `A` (vu que `|CEM|=90°-|ACB|`) . Donc, `X` est sur la droite `EM`.

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Jeu 19 Avr - 19:37

Solution du problème 8

Voilà, c'est fini. J'espère ne pas avoir laissé de faute de distraction. Pour être franc, j'ai trouvé ce problème très difficile à rédiger (plusieurs heures ; et je n'imagine pas pouvoir aller plus vite sans manquer de clarté). Pourtant, j'ai découvert le squelette de sa solution et j'ai été convaincu que le résultat était vrai en seulement un quart d'heure. Je me demande s'il existe une solution plus fulgurante et plus facile à rédiger. Je pense que oui, mais je ne la voie pas.

Dans ce qui suit, on suppose que tout mot possède un nombre entier strictement positif de lettres numérotées de gauche à droite à partir de `1`. On appelle sous-mot du mot `x`, tout mot obtenu en considérant une suite de lettres successives du mot `x`. Pour tout mot `x` et tout nombre `k` entier strictement positif, notons `|x|` la longueur du mot `x` (c'est-à-dire son nombre de lettres) et `x^k` le mot `x x x \ldots x` obtenu en juxtaposant `k` copies non tronquées du mot `x`.

Considérons un mot `m`. Pour tout nombre `k\in\{1,2,\ldots,|m|-1\}`, notons `m_k` le mot obtenu en permutant les lettres numéro `k` et `k+1` du mot `m`, `f(k)` le plus petit mot pour lequel il existe un nombre `l` tel que `(f(k))^l=m_k` et `g(k)` le plus grand nombre entier strictement positif pour lequel il existe un mot `y` tel que `y^{g(k)}=m_k` (il est clair que `(f(k))^{g(k)}=m_k` et que `m_k` est répétitif si et seulement si `g(k)\geq 2` si et seulement si `f(k)\ne m`). Considérons que le mot `m` est tel que `g(k)\geq 2` pour tout entier `k\in\{1,2,\ldots,|m|-1\}`. Notre but est de prouver que le mot `m` est composé d'une seule sorte de lettre.

Premier cas : `|m|>9`.

Si `r` et `s` sont des entiers strictement compris entre `{2|m|}/3` et `|m|`, alors les mots `m_r=(f(r))^{g(r)}` et `m_s=(f(s))^{g(s)}` possèdent le même début que le mot `m`, ce début identique étant d'une longueur au moins égale à presque deux tiers de la longueur du mot `m`. Si `g(r)=g(s)`, on a même `f(r)=f(s)` (puisque les longueurs de ces mots ne dépassent pas la moitié de la longueur du mot `m` alors que les permutations de lettres rendant les mots `m_r` et `m_s` différents ont été effectuées dans le dernier tiers du mot `m`) et donc `m_r=m_s`. Montrons par l'absurde `g(r)\ne g(s)` est impossible. Supposons que `g(s)<g(r)` (on raisonne de façon analogue dans le cas où `g(s)>g(r)`). Si `g(s)` divise `g(r)`, alors `f(s)=(f(r))^t` pour un certain entier `t\geq 2` et `m_s=(f(s))^{g(s)}=(f(r))^{tg(s)}`. Ceci contredit les définitions de `f(s)` et de `g(s)` car `f(r)` est strictement moins long que `f(s)` et `tg(s)` est strictement supérieur à `g(s)`. Si `g(s)` ne divise pas `g(r)`, `(g(s),g(r))\in\{(2,3);(2,5)\}`, alors `|f(r)|+|f(s)|<={2|x|}/3` (au pire il s'agit de `|x|/2+|x|/7={9|x|}/14<{2|x|}/3` ou de `|x|/3+|x|/4={7|x|}/12<{2|x|}/3`). Les débuts des mots `m_r` et `m_s` sont donc identiques sur une longueur au moins égale à `|f(r)|+|f(s)|`. Ceci suffit pour prouver qu'il existe un mot `n` et un entier `p\geq 2` tels que `|n|` est un diviseur de `|f(r)|` et `f(r)=n^p`. En effet, pour tout `i\in\{1,2,\ldots,|f(r)|\}`, la lettre numéro `i` (commune) des mots `m_r` et `m_s` est la même que la lettre numéro `i+|f(s)|` (commune) de ces mots. Ceci implique que les lettres du mot `f(r)` sont égales à une permutation cyclique non identique (car `|f(s)|` n'est pas un multiple de `|f(r)|`) de elles-mêmes (par exemple `(abcdef)` ---> `(cdefab)`). Mais alors, `f(s)` est une puissance d'un mot plus court que lui-même (dans notre exemple `a=c=e=a` et `b=d=f=b`, donc `(abcdef)=(ababab)`), dont la longueur est un diviseur de `|f(s)|`. On a donc `m_r=(f(r))^{g(r)}=n^{pg(r)}`. Ceci contredit les définitions de `f(r)` et `g(r)`. Si `g(s)=2` et `g(r)=3`, alors les mots `f(r)`, `f(s)` et `m` ont respectivement `2t`, `3t` et `6t` lettres pour un certain entier strictement positif `t`. Soient `a_1`, `a_2`, `\ldots`, `a_t`, `b_1`, `b_2`, `\ldots`, `b_t`, `c_1`, `c_2`, `\ldots`, `c_t`, `d_1`, `d_2`, `\ldots`, `d_t`, les `4t` premières lettres du mot `m`. Vu la forme du mot `m_r`, il faut que `a_1=c_1`, `a_2=c_2`, `\ldots`, `a_t=c_t` et `b_1=d_1`, `b_2=d_2`, `\ldots`, `b_t=d_t`. Vu la forme du mot `m_s`, il faut que `a_1=d_1`, `a_2=d_2`, `\ldots`, `a_t=d_t`. Donc, il existe un mot `n` tel que `|n|` soit le plus grand commun diviseur `t` de `g(r)` et `g(s)` et des entiers `p,q\geq 2` pour lesquels `f(r)=n^p` et `f(s)=n^q`. On arrive à la même contradiction que dans le cas précédent. Si `g(s)=2` et `g(r)=5`, alors les mots `f(r)`, `f(s)` et `m` ont respectivement `2t`, `5t` et `10t` lettres pour un certain entier strictement positif `t`. Soient `a_1`, `a_2`, `\ldots`, `a_t`, `b_1`, `b_2`, `\ldots`, `b_t`, `c_1`, `c_2`, `\ldots`, `c_t`, `d_1`, `d_2`, `\ldots`, `d_t`, `e_1`, `e_2`, `\ldots`, `e_t`, `f_1`, `f_2`, `\ldots`, `f_t` les `6t` premières lettres du mot `m`. Vu la forme du mot `m_r`, il faut que `a_1=c_1=e_1`, `a_2=c_2=e_2`, `\ldots`, `a_t=c_t=e_t` et `b_1=d_1=f_1`, `b_2=d_2=f_2`, `\ldots`, `b_t=d_t=f_t`. Vu la forme du mot `m_s`, il faut que `a_1=f_1`, `a_2=f_2`, `\ldots`, `a_t=f_t`. Donc, il existe un mot `n` tel que `|n|` soit le plus grand commun diviseur `t` de `g(r)` et `g(s)` et des entiers `p,q\geq 2` pour lesquels `f(r)=n^p` et `f(s)=n^q`. On arrive à la même contradiction que dans le cas précédent. Bref, si `r` et `s` sont des entiers strictement compris entre `{2|m|}/3` et `|m|`, alors `f(r)=f(s)` et donc `m_r=m_s`.

Il existe au moins `3` lettres de `m` dont le numéro est strictement compris entre `{2|m|}/3` et `|m|` car `{2|m|}/3<|m|-3` car `9<|m|`. Vu le paragraphe précédent, on a donc l'égalité `m_{|m|-1}=m_{|m|-2}`. Si les trois dernières lettres du mot `m` forment le sous-mot `abc`, alors l'égalité précédente implique que le sous-mot `acb` est le sous-mot `bac`, et donc que `a=b=c`. On a donc aussi `m_{|m|-1}=m`. Comme on a aussi l'égalité `m_k=m_{|m|-1}` pour tout entier `k` strictement compris entre `{2|m|}/3` et `|m|`, on déduit de proche en proche que le dernier tiers (arrondi vers le bas) des lettres du mot `m` est formé de lettres identiques.

On peut faire un raisonnement analogue en lisant les mots à l'envers pour montrer que le le premier tiers (arrondi vers le bas) des lettres du mot `m` est formé de lettres identiques.

Le mot `m` est donc de la forme `a^lxb^l` où `a` et `b` sont des lettres, `l` est un nombre entier au moins égal à `3` et `x` est un mot tel que `|x|\in\{l,l+1,l+2\}`.

Cela ne laisse pas beaucoup de possibilités pour la forme du mot `m`. En effet, si on permute ses deux premières lettres, il reste identique à lui-même et il devient répétitif. Si `a\ne b`, il faut que les sous-mots `a^l` et `b^l` se répètent chacun une fois dans le mot `m`, mais on n'a pas la place. Donc `a=b`. Il n'y a aucune autre façon de s'en sortir que de choisir `x=a^{|x|}`. On a prouvé que `m=a^{|m|}`.

Deuxième cas : `|m|\leq 9`.

Remarquons d'abord que si il existe `k\in\{1,2,\ldots,|m|-1\}` tel que `|f(k)|=1`, alors le problème est résolu.

De plus, s'il existe `k\in\{1,2,\ldots,|m|-1\}` tel que `|f(k)|=2`, alors le mot `m` s'écrit sous l'une des deux formes suivantes, où `a` et `b` sont des lettres et où `i`, `j` sont des entiers positifs ou nuls de somme non nulle : `(ab)^iba(ab)^j`, `a(ba)^iab(ba)^jb`. Dans les deux cas, il existe deux lettres consécutives identiques. Si on les permute, on obtient un mot identique, mais ce mot doit être répétitif. Cela n'est possible que si `a=b`. En effet, pour qu'un mot soit répétitif, il doit contenir au moins deux fois chacun de ses sous-mots de longueur `2`, sauf s'il est de la forme `yy` (où `y` est un mot) et que le sous-mot considéré est formé de la dernière lettre de `y` suivie de la première lettre de `y`. Mais si `a\ne b`, le mot `a(ba)^iab(ba)^jb` contient exactement une fois le sous mot `aa` et exactement une fois le sous mot `b b`. Il serait évidemment impossible que ce mot soit de la forme `yy` avec `y` qui se termine et commence par `a` et `b` à la fois. De plus, si `a\ne b`, on peut faire le même raisonnement pour le mot `(ab)^iba(ab)^j`, sauf si `i=0` ou `j=0` (les deux ne peuvent être nuls en même temps). Si `i=0` (on raisonne de façon analogue si `j=0`), le mot contient exactement une fois le sous-mot `aa` et ce sous-mot n'est pas en son milieu sauf si le mot est `baab` qui n'est pas un mot répétitif. Bref `a=b`, ce qui montre que le problème est résolu s'il existe `k\in\{1,2,\ldots,|m|-1\}` tel que `|f(k)|=2`.

Nous pouvons donc considérer que, pour tout `k\in\{1,2,\ldots,|m|-1\}`, on a `|f(k)|\geq 3`. Comme `|m|\leq 9`, les seuls mots capables de satisfaire cela sont des mots de longueur `3+3=6`,`3+3+3=9` et `4+4=8`. Plus précisément, il ne reste qu'à traiter les trois candidats suivants : `m=abcacb`, `m=abcabcacb` et `m=abcdabdc` sous l'hypothèse `|f(k)|\geq 3`, ce qui est visuel et immédiat.

EDITION : dans le premier cas, j'ai rajouté la possibilité où `g(s)=2` et `g(r)=5`. Je l'avais oubliée en rédigeant. Elle est très semblable à la possibilité où `g(s)=2` et `g(r)=3`.


Dernière édition par le_magicien le Dim 22 Avr - 12:05, édité 2 fois

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  le_magicien le Ven 20 Avr - 9:35

Solution du problème 4

Voilà, suite aux discussions avec Carole, il résulte ceci.

Soit `E` l'ensemble des nombres strictement positifs. On définit la suite de Fibonacci `(f_n)_{n\in E}` par `f_1=1`, `f_2=2` et `f_{n+2}=f_{n+1}+f_{n}` pour tout `n\in E`. Ensuite, on définit la suite `(g_n)_{n\in E}` par `g_n=(-1)^{n+1}f_n` pour tout `n\in E`. On va prouver que l'ensemble `G=\{g_n : n\in E\}` est un ensemble d'entiers somme-clos et somme_nulle_absente, ce qui fournira une réponse affirmative au problème.

Tout d'abord, `G` est bien évidemment un ensemble d'entiers.

De plus, `G` est somme-clos car pour tout `x\in G`, il existe `n\in E` tel que `x=g_n=(-1)^{n+1}f_n=(-1)^{n+1}(f_{n+2}-f_{n+1})=(-1)^{(n+2)+1}f_{n+2}+(-1)^{(n+1)+1}f_{n+1}=g_{n+2}+g_{n+1}` où `g_{n+1}` et `g_{n+2}` sont des éléments de `G`.

Pour prouver que `G` est somme_nulle_absente, il suffit de prouver par récurrence sur `n` que l'ensemble des sommes des sous-ensembles non vides de l'ensemble `\{g_1,g_2,\ldots,g_n\}` est l'ensemble des entiers non nuls strictement compris entre `-g_{n}` et `-g_{n+1}` (l'un de ces deux entiers est positif et l'autre est négatif, selon la parité de `n`). Si `n=1`, on ne possède que la somme `1` et c'est bien le seul entier non nul strictement compris entre `g_1=-1` et `-g_2=2`. Supposons que la propriété est vraie pour `n`, c'est-à-dire qu'on puisse construire tous (et seulement tous) les nombres entiers non nuls strictement compris entre `-g_n` et `-g_{n+1}` en faisant la somme d'une partie non vide de l'ensemble `\{g_1,g_2,\ldots,g_n\}`, et prouvons qu'elle est vrai pour `n+1`. Avec l'ensemble `\{g_1,g_2,\ldots,g_{n+1}\}=\{g_1,g_2,\ldots,g_n\}\cup\{g_{n+1}\}`, on peut construire les entiers non nul strictement compris entre `-g_n` et `-g_{n+1}`, ainsi que les entiers strictement compris entre `-g_n+g_{n+1}=-g_{n+2}` et `-g_{n+1}+g_{n+1}=0` (dont `g_{n+1}`), mais aucun autre entier que ceux-là. On vient en fait de prouver qu'on peut construire tous (et seulement tous) les entiers non nuls strictement compris entre `-g_{n+1}` et `-g_{n+2}`.

le_magicien
Pro
Pro

Messages : 56
Date d'inscription : 11/04/2012

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: European Girls' Mathematical Olympiad (EGMO) 2012 :

Message  Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum