Exercices de MPSI

[BijouRe]

Euh.. cette exo est possible avec des outils de Terminale enfaite ?

[Sketshup]

Tu parles de l'exercice de dénombrement?

Si oui, alors oui. La solution est en spoiler.

[BijouRe]

Tu parles de l'exercice de dénombrement?

Si oui, alors oui. La solution est en spoiler.

Tu utilises bcp d'outil/concept qu'on ne voit pas en Terminale ^^ Je comprend la méthode mais les outils que tu utilises ...
C'est pour ça que j'aimerai savoir si il existait une méthode en utilisant les outils de Tle

[Siméon]

Ma solution pour l'exercice de dénombrement:

SPOILER:

On pose pour tout i entre 0 et n, x_i = k_i - 1. Pour toute solution (k_i) dans [1; p-n+2]^{n+1}, on obtient un unique (n+1)-uplet (x_i) dans [0;p-n+1]^{n+1}.

De plus: k_0 + ... + k_n = p+2 équivaut à x_0 + ... + x_n = p-n+1.

Donc, l'ensemble qu'on cherche à dénombrer, et l'ensemble:

{(x_0, x_1, ..., x_n) \in [0; n-p+1]^{n+1} | x_0 + x_1 + ... + x_n = p-n+1}

sont équipotents. Il suffit de dénombrer ce dernier.

On considère la construction suivante:

Dans une ligne, on pose (p+1) briques dont (n) briques sont rouges (R) , et (p-n+1) briques sont bleues (B).

On appelle succession toute configuration possible d'alignement de R et de B. Par exemple, (B; B; B; R; B; B; R; R; B) est une succession pour n=3 et p=8.

Soit r une succession, on la parcourt de sa première entrée jusqu'à sa dernière (p+1)
On pose:
y_1 = Le nombre de briques bleues avant de rencontrer la première brique rouge.
y_2 = Le nombre de briques bleues avant de rencontrer la seconde brique rouge.
Récursivement:
y_{i} = Le nombre de briques bleues avant de rencontrer la i'ème brique rouge.
et: y_{n+1} = le nombre de briques bleues après la n'ème brique rouge.

Clairement: vu qu'il y'a exactement p-n+1 briques bleues. Tout y_i est inférieur à p-n+1, et la somme des y_i est exactement p-n+1.
Donc le (n+1)-uplet (y_i) est une solution.

Réciproquement. Soit x = (x_i) une solution. On construit la succession suivante:

Pour tout i entre 0 et n. x_i briques bleues sont directement suivies d'une brique rouge. Ainsi, on a n briques rouges, et x_0 + x_1 + x_2 + ... + x_n = p-n+1 briques bleues.
La suite de briques construite est donc une succession.


L'ensemble de successions, et l'ensemble qu'on cherche à dénombrer sont équipotents.

Il est facile de dénombrer l'ensemble de successions. On choisit n briques rouges parmis p+1 briques. Il s'agit de nC(p+1). (Ou bien p-n+1 bleues parmis p+1 briques, qui est le même nombre).


Le cardinal de l'ensemble est nC(p+1).

Saut erreur.

Si je ne m'abuse, la soustraction de 1 que tu fais au début de la preuve n'apporte rien.

[zboum]

Cet exercice on le faisait avec "les bâtons", je n'ai jamais compris. En tout cas avec les séries entières, ça se fait en trois lignes.

[BijouRe]

Cet exercice on le faisait avec "les bâtons", je n'ai jamais compris. En tout cas avec les séries entières, ça se fait en trois lignes.

Donc faisable avec des outils de term ?

[czarmath]

Si je ne m'abuse, la soustraction de 1 que tu fais au début de la preuve n'apporte rien.

Si si, pour rendre le problème plus classique il s'agit en fait de
de trouver le nombre de solutions entière à une équation à n indéterminée...

[czarmath]

Ma solution pour l'exercice de dénombrement:

SPOILER:

On pose pour tout i entre 0 et n, x_i = k_i - 1. Pour toute solution (k_i) dans [1; p-n+2]^{n+1}, on obtient un unique (n+1)-uplet (x_i) dans [0;p-n+1]^{n+1}.

De plus: k_0 + ... + k_n = p+2 équivaut à x_0 + ... + x_n = p-n+1.

Donc, l'ensemble qu'on cherche à dénombrer, et l'ensemble:

{(x_0, x_1, ..., x_n) \in [0; n-p+1]^{n+1} | x_0 + x_1 + ... + x_n = p-n+1}

sont équipotents. Il suffit de dénombrer ce dernier.

On considère la construction suivante:

Dans une ligne, on pose (p+1) briques dont (n) briques sont rouges (R) , et (p-n+1) briques sont bleues (B).

On appelle succession toute configuration possible d'alignement de R et de B. Par exemple, (B; B; B; R; B; B; R; R; B) est une succession pour n=3 et p=8.

Soit r une succession, on la parcourt de sa première entrée jusqu'à sa dernière (p+1)
On pose:
y_1 = Le nombre de briques bleues avant de rencontrer la première brique rouge.
y_2 = Le nombre de briques bleues avant de rencontrer la seconde brique rouge.
Récursivement:
y_{i} = Le nombre de briques bleues avant de rencontrer la i'ème brique rouge.
et: y_{n+1} = le nombre de briques bleues après la n'ème brique rouge.

Clairement: vu qu'il y'a exactement p-n+1 briques bleues. Tout y_i est inférieur à p-n+1, et la somme des y_i est exactement p-n+1.
Donc le (n+1)-uplet (y_i) est une solution.

Réciproquement. Soit x = (x_i) une solution. On construit la succession suivante:

Pour tout i entre 0 et n. x_i briques bleues sont directement suivies d'une brique rouge. Ainsi, on a n briques rouges, et x_0 + x_1 + x_2 + ... + x_n = p-n+1 briques bleues.
La suite de briques construite est donc une succession.


L'ensemble de successions, et l'ensemble qu'on cherche à dénombrer sont équipotents.

Il est facile de dénombrer l'ensemble de successions. On choisit n briques rouges parmis p+1 briques. Il s'agit de nC(p+1). (Ou bien p-n+1 bleues parmis p+1 briques, qui est le même nombre).


Le cardinal de l'ensemble est nC(p+1).

Saut erreur.

J'espère que tu as trouvé du plaisir en faisant cet exercice.

[Sketshup]

Salut,

@JustSayin': Ensembles équipotents, fais pas trop attention, ça veut simplement dire qu'ils ont le même cardinal, ou bien qu'il existe une bijection entre les deux.

En décortiquant la solution, on trouvera que l'approche générale est:
-Bijection
-Construction d'une situation où le dénombrement (le fait de compter) est plus simple.
-Prouver que la construction donne un ensemble bijective au nôtre.

J'ai utilisé 2 outils "techniques":
-Etablir les bijections (Pour la première, c'est évident. Pour la deuxième, on considère un élément d'un ensemble, et on prouve qu'il est lié à un élément de l'autre ensemble. On fait la même chose réciproquement)
-Dénombrer le dernier ensemble (une k-combinaison directe)

On a définit ce que c'est qu'une bijection en première, et pareil pour les k-combinaisons. Je pense que le programme français a fait pareil, si ce n'est en première, alors au plus en terminale?

@Siménon: En fait, j'ai essayé de le faire sans, mais je n'ai pas trouvé de situation équivalente (ET facile à dénombrer). En utilisant le même principe des briques, on s'impose, si on ne retranche pas 1, de commencer une succession par une brique bleue, et que toute brique rouge est obligatoirement suivie d'une brique bleue (i.e Pas de 2 briques rouges consécutives).

@zboum: Une autre approche que j'ai essayé est de construire une suite récursive sur p. Je poste dès que j'ai une solution!


@Czarmath: La résolution est toujours amusante, c'est la reproduire en message qui ne l'est pas trop (Encore, on n'est pas strict ici pour LaTeX)

[czarmath]

@Siménon: En fait, j'ai essayé de le faire sans, mais je n'ai pas trouvé de situation équivalente (ET facile à dénombrer). En utilisant le même principe des briques, on s'impose, si on ne retranche pas 1, de commencer une succession par une brique bleue, et que toute brique rouge est obligatoirement suivie d'une brique bleue (i.e Pas de 2 briques rouges consécutives).

Et si on écrit B#B#.....B# , et en suite remplacer n des p+1 "#" par n "R" ?