FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

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

FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

Message  G. Lorang le Sam 14 Avr - 17:57

J'ai seulement les questions en anglais Rolling Eyes


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: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

Message  le_magicien le Sam 14 Avr - 20:07

Problème 1

En posant `n=1` dans la seconde condition de l'énoncé, on trouve `f(m+1)=f(m)+f(1)+2m` quel que soit l'entier strictement positif `m`. En travaillant de proche en proche, on trouve donc `f(m+1)=f(m)+f(1)+2m=f(m-1)+2f(1)+2m+2(m-1)=f(m-2)+3f(1)+2m+2(m-1)+2(m-2)`
`=\cdots=f(1)+mf(1)+2m+2(m-1)+2(m-2)+\cdots 2=(m+1)f(1)+2\frac{m(m+1)}{2}=(m+1)(f(1)+m)`.

Si `f(1)=1`, alors la fonction `f(m)=m^2` est une solution du problème (on vérifie très facilement qu'elle vérifie toutes les conditions de l'énoncé). De plus, c'est la seule solution du problème. En effet, si `f(1)>1`, alors le nombre `f(m+1)=(m+1)(f(1)+m)` vaut `f(m+1)=((f(1))^2-f(1)+1)(f(1))^2` lorsqu'on choisit `m=(f(1))^2-f(1)`. Ce nombre n'est visiblement pas un carré parfait car il est le produit d'un carré parfait par le nombre `(f(1))^2-f(1)+1` qui est strictement compris entre les carrés des deux entiers successifs `f(1)-1` et `f(1)`, si `f(1)>1`.

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: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

Message  le_magicien le Sam 14 Avr - 20:41

Problème 2

Dans le cas où `a=b` ou `b=c` ou `c=a`, on trouve directement, à partir de l'équation de l'énoncé, que les trois nombres `a`, `b` et `c` sont tous égaux entre eux. On peut donc considérer uniquement le cas où les trois nombres `a`, `b` et `c` sont deux à deux distincts. Mais alors, on peut déduire les relations suivantes : `k=\frac{a^n-b^n}{c-b}=\frac{b^n-c^n}{a-c}=\frac{c^n-a^n}{b-a}`.

Par le principe des tiroirs, il y a deux des trois nombres `a`, `b` et `c` qui sont de même parité. Admettons que ce soient `a` et `b` car les autres cas sont analogues. On déduit alors de l'égalité `k=\frac{a^n-b^n}{c-b}` que `c` doit aussi être de même parité que `a` et `b`, sinon le second membre est une fraction dont le numérateur est pair et dont le dénominateur est impair, et il ne peut donc pas être égal au nombre impair `k`.

Comme les trois nombres `a`, `b` et `c` sont tous de même parité, on déduit du principe du tiroir qu'il y en a deux qui sont de même congruence modulo `4`. Admettons que ce soient `a` et `b` car les autres cas sont analogues. On déduit alors de l'égalité `k=\frac{a^n-b^n}{c-b}` que `c` doit aussi être de même congruence modulo `4` que `a` et `b`, sinon le second membre est une fraction dont le numérateur est un multiple de `4` et dont le dénominateur est congru à `2` modulo `4`, et il ne peut donc pas être égal au nombre impair `k`.

Comme les trois nombres `a`, `b` et `c` sont tous de même congruence modulo 4, on déduit du principe du tiroir qu'il y en a deux qui sont de même congruence modulo `8`. Admettons que ce soient `a` et `b` car les autres cas sont analogues. On déduit alors de l'égalité `k=\frac{a^n-b^n}{c-b}` que `c` doit aussi être de même congruence modulo `8` que `a` et `b`, sinon le second membre est une fraction dont le numérateur est un multiple de `8` et dont le dénominateur est congru à `4` modulo `8`, et il ne peut donc pas être égal au nombre impair `k`.

On continue de la sorte jusqu'au moment où on a déduit que les trois nombres `a`, `b` et `c` sont de même congruence modulo une puissance de `2` plus grande que eux. On déduit alors qu'ils sont égaux.

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: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

Message  le_magicien le Sam 14 Avr - 21:11

Problème 3

Dans la première tour, il y a `C_n^r` possibilités pour choisir `r` filles et `C_n^r` possibilités pour choisir `r` garçons. Une fois les garçons et les filles choisies, il ne reste plus qu'à ordonner les garçons (ordonner les filles en plus serait redondant car on formerait plusieurs fois les mêmes couples), ce qui se fait de `r!` façons différentes. On peut donc dire que `X(r)=(C_{n}^r)^2\cdot r!`.

Dans la second tour, si on choisit les `r` filles `g(i_1), g(i_2), \ldots, g(i_r)` avec `1\leqi_1<i_2<\ldots<i_r\leq n`, il y a `2i_1-1` cavaliers possibles pour la fille `g(i_1)`, puis il reste `2i_2-2` cavaliers possibles pour la fille `g(i_2)` (il y en avait `2i_2-1` mais l'un d'eux vient d'être casé avec la fille `g(i_1)`), `\ldots`, puis finalement puis il reste `2i_r-r` cavaliers possibles pour la fille `g(i_r)` (il y en avait `2i_r-1` mais `r-1` d'entre eux viennent d'être casés avec les `r-1` première filles). On peut donc dire que `Y(r)=\sum_{I_r} (2i_1-1)(2i_2-2)\cdots(2i_r-r)` où la somme porte sur toutes les choix possibles de `r`-uplet `(i_1,i_2,\ldots,i_r)` de nombres entiers vérifiant `1\leqi_1<i_2<\ldots<i_r\leq n`.

Pour conclure, il suffit de prouver que `\sum_{I_r} (2i_1-1)(2i_2-2)\cdots(2i_r-r)=(C_{n}^r)^2\cdot r!` par récurrence sur `r`. Pour éviter tout problème, on pose `C_n^r=0` si `r>n`.

Je vais continuer dans le poste suivant.

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: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

Message  le_magicien le Sam 14 Avr - 21:42

Problème 3 : suite

Amorçons notre récurrence en démontrant que l'égalité `\sum_{I_r}(2i_1-1)(2i_2-2)\cdots(2i_r-r)=(C_n^r)^2\cdot r!` est vraie pour `r=1`, quel que soit l'entier strictement positif `n`. Pour `r=1`, le premier membre s'écrit `\sum_{I_1}(2i_1-1)=1+3+5+\cdots+2n-1=\frac{(2n-1+1)\cdot n}{2}=n^2` et le second membre s'écrit `(C_n^1)^2\cdot 1! =n^2\cdot 1=n^2`. Les deux membres sont donc égaux.

Continuons notre récurrence en supposant que l'égalité est vraie pour `r` quel que soit l'entier `n>r` et en la démontrant pour `r+1` quel que soit l'entier `n>r`. Je vais écrire `\sum_{I_r;n}` en précisent le `n` car c'est important. De plus, il ne faut pas perdre de vue qu'une somme est nulle si elle n'a aucun terme (cela s'applique au symbole sommatoire aussi). En utilisant l'hypothèse de récurrence, le premier membre s'écrit `\sum_{I_{r+1;n}}(2i_1-1)(2i_2-2)\cdots(2i_r-r)(2i_{r+1}-(r+1))=\sum_{i_{r+1}=1}^n (2i_{r+1}-(r+1))\sum_{I_r;i_{r+1}-1}(2i_1-1)(2i_2-2)\cdots(2i_r-r)=\sum_{i_{r+1}=1}^n (2i_{r+1}-(r+1))(C_{i_{r+1}-1}^r)^2\cdot r!`. Le second membre s'écrit `(C_n^{r+1})^2\cdot (r+1)!`. On va utiliser une récurrence sur `n` --- à l'intérieur de notre récurrence sur `r`,--- pour conclure que `\sum_{i_{r+1}=1}^n (2i_{r+1}-(r+1))(C_{i_{r+1}-1}^r)^2\cdot r! =(C_n^{r+1})^2\cdot (r+1)!`.

Je vais continuer et finir dans le poste suivant.


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: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

Message  le_magicien le Sam 14 Avr - 22:27

Problème 3 : suite et fin.

Vu qu'on est en train de passer de `r` à `r+1` dans la récurrence principal, cela n'a pas de sens de travailler ici pour `n\leq r`. Avec la convention d'annuler les facteurs binomiaux non conventionnels, si `n=r+1`, le premier membre vaut `(2(r+1)-(r+1))\cdot (C_{r+1-1}^r)^2\cdot r! =(r+1)\cdot 1^2\cdot r! =(r+1)!` et le second membre vaut `(C_{r+1}^{r+1})^2\cdot (r+1)! =1^2\cdot (r+1)! =(r+1)!`. Les deux membres sont bien égaux.

Il ne reste qu'à montrer que si la formule est vraie pour `n`, alors elle l'est aussi pour `n+1`. Le premier membre vaut `\sum_{i_{r+1}}^{n+1}(2i_{r+1}-(r+1))\cdot (C_{i_{r+1}-1}^{r})^2\cdot r! =(2(n+1)-(r+1))\cdot (C_{n+1-1}^{r})^2\cdot r! +\sum_{i_{r+1}}^{n}(2i_{r+1}-(r+1))\cdot (C_{i_{r+1}-1}^{r})^2\cdot r! =(2n+1-r)\cdot (C_{n}^{r})^2\cdot r! +(C_n^{r+1})^2\cdot (r+1)!`
`=\frac{(2n+1-r)\cdot n! \cdot n! \cdot r!}{(n-r)!\cdot(n-r)!\cdot r!\cdot r!}+\frac{n!\cdot n!\cdot(r+1)!}{(r+1)!\cdot (r+1)!\cdot (n-r-1)!\cdot (n-r-1)!}=((2n+1-r)(r+1)^2+(r+1)(n-r)^2)\cdot\frac{n!\cdot n!\cdot r!}{(r+1)!\cdot (r+1)!\cdot (n-r)!\cdot (n-r)!}`
`=((2n+1-r)(r+1)+(n-r)^2)\cdot\frac{n!\cdot n!}{(r+1)!\cdot (r+1)!\cdot (n-r)!\cdot (n-r)!}\cdot (r+1)! =(2nr+2n+r+1-r^2-r+n^2-2rn+r^2)\cdot\frac{n!\cdot n!}{(r+1)!\cdot (r+1)!\cdot (n-r)!\cdot (n-r)!}\cdot (r+1)!`
`=(n^2+2n+1)\cdot\frac{n!\cdot n!}{(r+1)!\cdot (r+1)!\cdot (n-r)!\cdot (n-r)!}\cdot (r+1)! =\frac{(n+1)!\cdot (n+1)!}{(r+1)!\cdot (r+1)!\cdot (n-r)!\cdot (n-r)!}\cdot (r+1)!` et le second membre vaut `(C_{n+1}^{r+1})^2\cdot (r+1)!` donc la même chose.

OUF ! Very Happy Very Happy Very Happy Very Happy Very Happy

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: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

Message  le_magicien le Dim 15 Avr - 10:21

Solution plus rapide du problème 3.

En fait, la récurrence sur `r` me semble correcte mais est totalement inutile et complique le problème car on peut faire directement une récurrence sur `n`. Je vais écrire cette preuve plus élégante dont le début ressemble à celui de la preuve précédente.

Dans la première tour, il y a `C_n^r` possibilités pour choisir `r` filles et `C_n^r` possibilités pour choisir `r` garçons. Une fois les garçons et les filles choisies, il ne reste plus qu'à ordonner les garçons (ordonner les filles en plus serait redondant car on formerait plusieurs fois les mêmes couples), ce qui se fait de `r!` façons différentes. On peut donc dire que `X(r)=(C_{n}^r)^2\cdot r!`.

Dans la second tour, si on choisit les `r` filles `g(i_1), g(i_2), \ldots, g(i_r)` avec `1\leqi_1<i_2<\ldots<i_r\leq n`, il y a `2i_1-1` cavaliers possibles pour la fille `g(i_1)`, puis il reste `2i_2-2` cavaliers possibles pour la fille `g(i_2)` (il y en avait `2i_2-1` mais l'un d'eux vient d'être casé avec la fille `g(i_1)`), `\ldots`, puis finalement puis il reste `2i_r-r` cavaliers possibles pour la fille `g(i_r)` (il y en avait `2i_r-1` mais `r-1` d'entre eux viennent d'être casés avec les `r-1` première filles). On peut donc dire que `Y(r)=\sum_{I_{r;n}} (2i_1-1)(2i_2-2)\cdots(2i_r-r)` où la somme sur `I_{r;n}` porte sur tous les choix possibles de `r`-uplet `(i_1,i_2,\ldots,i_r)` de nombres entiers vérifiant `1\leqi_1<i_2<\ldots<i_r\leq n`.

Pour conclure, il suffit de prouver que `\sum_{I_r;n} (2i_1-1)(2i_2-2)\cdots(2i_r-r)=(C_{n}^r)^2\cdot r!` par récurrence sur `n` pour `n\geq r`.

Amorçons notre récurrence en démontrant que l'égalité est vrai pour `n=r`. Le premier membre vaut `(2-1)(4-2)\cdots(2r-r) =r!` (car il n'y a que le `r`-uplet `(1,2,\ldots,r)` qui convient) et le second membre vaut `(C_{r}^{r})^2\cdot r! =1^2\cdot r! =r!`. Les deux membres sont bien égaux.

Il faut aussi montrer que l'égalité est vraie pour `n=r+1`, sinon l'amorçage de cette récurrence ne sera pas complet (vu la suite). Dans ce cas, le premier membre vaut `\sum_{k=1}^{r+1}\frac{(r+2)!}{k(k+1)}`. En effet, le terme en `k` de cette somme est le produit `(2-1)(4-2)(6-3)\cdots(2(k-1)-(k-1))\cdot(2(k+1)-k)\cdots(2(r+1)-r)` correspondant au `r`-uplet `(1,2,3,\ldots,k-1,k+1,\ldots,r+1)` dans lequel le nombre `k` est absent. Mais ce premier membre vaut donc `(r+2)!\cdot\sum_{k=1}^(r+1)\frac{(k+1)-k}{k(k+1)}=(r+2)!\cdot\sum_{k=1}^{r+1}(\frac{1}{k}-\frac{1}{k+1})=(r+2)!\cdot(1-\frac{1}{r+2})=(r+1)!(r+1)=(r+1)^2r! =(C_{r+1}^r)^2\cdot r!`, c'est-à-dire le second membre.

Terminons notre récurrence en supposant que l'égalité est vraie pour `n` et en la démontrant pour `n+1`, quel que soit l'entier `r` tel que `1\leq r\leq n`. Le premier membre vaut `\sum_{I_r;n+1} (2i_1-1)(2i_2-2)\cdots(2i_r-r)=[\sum_{I_r;n} (2i_1-1)(2i_2-2)\cdots(2i_r-r)]+[(2(n+1)-r)\sum_{I_{r-1;n}} (2i_1-1)(2i_2-2)\cdots(2i_{r-1}-(r-1))]` où les termes entre crochets représentent respectivement toutes les sommes pour lesquelles `i_r\leq n` et toutes les sommes pour lesquelles `i_r=n+1`. Si une somme n'a aucun terme (ce qui se produit si `r-1=0`), elle est bien sûr nulle. En utilisant deux fois l'hypothèse de récurrence, on trouve que ce premier membre vaut `(C_{n}^r)^2\cdot r!+(2(n+1)-r)\cdot(C_{n}^{r-1})^2\cdot (r-1)! =\frac{n! n! r!}{r! r! (n-r)! (n-r)!}+\frac{(2n+2-r) n! n! (r-1)!}{(r-1)! (r-1)! (n-r+1)! (n-r+1)!}=\frac{n!n!(r-1)!(r(n-r+1)^2+(2n+2-r)r^2)}{r!r!(n-r+1)!(n-r+1)!}`
`=\frac{n!n!r!((n-r+1)^2+(2n+2-r)r)}{r!r!(n-r+1)!(n-r+1)!}=\frac{n!n!r!(n^2+r^2+1-2nr+2n-2r+2nr+2r-r^2)}{r!r!(n-r+1)!(n-r+1)!}=\frac{n!n!r!(n^2+2n+1)}{r!r!(n-r+1)!(n-r+1)!}=frac{(n+1)!(n+1)!r!}{r!r!(n-r+1)!(n-r+1)!}=(C_{n+1}^r)^2\cdot r!`. Le premier membre vaut donc le second membre, ce qui conclut la récurrence et la preuve.

Very Happy Very Happy Very Happy

le_magicien
Pro
Pro

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

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Toutes mes félicitations !

Message  G. Lorang le Lun 7 Mai - 11:00

Cher magicien,
Cela m'a procuré à nouveau un très grand plaisir de lire tes réponses, rédigées avec une clarté absolue et bien sûr sans la moindre faille !
Je t'accorde 30+30+60=120 points cadeaux, car pour résoudre le 3e problème, il a certainement fallu une double portion de patience, et d'ailleurs,
deux solutions c'est encore mieux qu'une ... Very Happy
J'espère que tu parviendras encore à résoudre le problème 4. Comme toujours ces problèmes n°4 sont les plus durs ... Very Happy
Cordialement, G. Lorang
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: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009

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