FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
2 participants
Page 1 sur 1
Re: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
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`.
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
- Messages : 56
Date d'inscription : 11/04/2012
Re: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
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.
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
- Messages : 56
Date d'inscription : 11/04/2012
Re: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
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.
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
- Messages : 56
Date d'inscription : 11/04/2012
Re: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
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.
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
- Messages : 56
Date d'inscription : 11/04/2012
Re: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
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 !
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 !
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Re: FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
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.
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.
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Toutes mes félicitations !
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 ...
J'espère que tu parviendras encore à résoudre le problème 4. Comme toujours ces problèmes n°4 sont les plus durs ...
Cordialement, G. Lorang
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 ...
J'espère que tu parviendras encore à résoudre le problème 4. Comme toujours ces problèmes n°4 sont les plus durs ...
Cordialement, G. Lorang
Sujets similaires
» THIRD BENELUX MATHEMATICAL OLYMPIAD : BxMO 2011
» SECOND BENELUX MATHEMATICAL OLYMPIAD : BxMO 2010
» European Girls' Mathematical Olympiad (EGMO) 2012 :
» BxMO 2012
» BxMO avril 2013
» SECOND BENELUX MATHEMATICAL OLYMPIAD : BxMO 2010
» European Girls' Mathematical Olympiad (EGMO) 2012 :
» BxMO 2012
» BxMO avril 2013
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|