Moi on me l’a posé comme ça ! après V@j et nico si vous avez des (grosses) améliorations,n’hésitez pas!
Si je ne me trompe pas, le problème revient surtout à dénombrer le nombre de dérangements d’un ensemble à n éléments.
C’est ça kkohlc. si tu connais ce nombre c’est gagné.
Bon en fait j’utilisais successivement deux récurrences simples plutôt que cette grosse formule, mais ma méthode a à chaque fois le gros désavantage de parachuter la propriété que l’on veut montrer par récurrence… Donc finalement peut-être que la tienne est mieux. 
kköhlc a écrit:
(même si cela risque de prendre du temps, étant donné l’exercice et le fait que j’ai un bac blanc à réviser
).
Je pense que ça devrait aller en maths.
kköhlc a écrit:
[quote=« krosian »]
[quote=« kköhlc »]
On note f(x)=\phi(x)+\delta(x) où \forall x\in\mathbb{R}, \phi(x)=ax^2+bx+c et \delta est dérivable.
Qu’est-ce qui t’autorise à faire ça ?
[/quote]
J’ai f(x)=\phi(x)+f(x)-\phi(x) et je pose f(x)-\phi(x)=\delta(x). Et comme j’ai supposé f dérivable (c’est là qu’est mon problème), il faut que \delta soit dérivable.
[/quote]
Non mais je veux dire, pour le choix de a,b,c ?
JeanN a écrit:
Un petit exo de l’X qui ne demande pas de connaissances de taupe.
Déterminer les fonctions f et g de \mathbb R dans \mathbb R vérifiant \forall x\neq y, \frac{f(x)-f(y)}{x-y}=g\left(\frac{x+y}{2}\right)
J’aimerais bien une petite indication pour cet exercice, s’il vous plait.
Pour le moment, j’ai tenté de poser g(x)=2x\phi(x)+g(0), ce qui me donnait f(x)=f(0)+xg(0)+x^2\phi\left(\frac{x}{2}\right) (assez proche de ce que je souhaite obtenir). Mais je n’arrive pas à montrer que \phi est constante.
Faut-il procéder autrement que par l’absurde pour aboutir ?
Pour le problème de Brank :
Pour les dérangements, la 1ère relation de récurrence que j’ai trouvé est D_{n+1}=n(D_n+D_{n+1}), c’est bien celle-ci ? (je n’ai pas rédigé la preuve dont je préfère vérifier que ma formule est correcte)
Pas de soucis
Tu peux considérer f(1-x)-f(x), f(-y)-f(y) puis remplacer x par -y et combiner pour montrer que f(y+1)-f(y) est affine…
JeanN a écrit:
Pas de soucis
Tu peux considérer f(1-x)-f(x), f(-y)-f(y) puis remplacer x par -y et combiner pour montrer que f(y+1)-f(y) est affine…
Merci pour cette indication.
Voilà ma proposition :
Pour tout x\neq y, on notera \mathcal{E}_{x,y} l’égalité \displaystyle \frac{f(x)-f(y)}{x-y}=g\left(\frac{x+y}{2}\right).
De \mathcal{E}_{1-x,x}, il vient f(1-x)-f(x)=(1-2x)g\left(\frac{1}{2}\right). De \mathcal{E}_{-y,y}, il vient f(-y)-f(y)=-2yg(0).
En effectuant le changement de variables x=-y dans la première équation, on obtient \displaystyle f(1+y)-f(-y)=(1+2y)g\left(\frac{1}{2}\right).
On ajoute les deux premières équations, ce qui donne finalement \displaystyle f(1+y)-f(y)=(1+2y)g\left(\frac{1}{2}\right)-2yg(0).
D’après \mathcal{E}_{1+y,y}, on a g\left(y+\frac{1}{2}\right)=f(1+y)-f(y). On pose alors \displaystyle t=y+\frac{1}{2}. On obtient donc \displaystyle g(t)=2t\left(g\left(\frac{1}{2}\right)-g(0)\right)+g(0).
De \mathcal{E}_{x,0}, il vient \displaystyle f(x)=f(0)+xg\left(\frac{x}{2}\right), soit \displaystyle f(x)=f(0)+xg(0)+x^2\left(g\left(\frac{1}{2}\right)-g(0)\right).
On en déduit que les couples de fonctions solutions de l’équation \mathcal{E}_{x,y} sont de la forme (f,f') où f est une fonction polynomiale de degré \leq 2.
Ca marche
J’avais en fait trouvé une solution bien plus compliquée mais un collègue m’a proposé cette idée de solution qui repose essentiellement sur le fait qu’une composée de deux symétries de R (ie applications de la forme x\mapsto a-x) est une translation de R…
brank a écrit:
Celui là est difficile, voir très difficile sans indication.Je peux en donner au fur et à mesure.
Dans une grande assemblée, on demande à chaque personne d’écrire son nom sur
un bout de papier et de le mettre dans un chapeau. On agite le chapeau puis chacun tire
un bout de papier. Quelle est la probabilité que personne ne tire le bout de papier portant
son propre nom ?On pourra démontrer (c’est bien de rédiger la récurrence) et se servir de la formule d’inclusion- exclusion suivante: (les A_{i} sont des évènements )
Exercice super sympa !
[spoiler]Soit n\in\mathbb{N^*}. On note \mathcal{S}_n l’ensemble des bijections de [\![1;n]\!]. On dit que s\in\mathcal{S}_n est un dérangement de [\![1;n]\!] si pour tout k\in \,[\![1;n]\!] , s(k)\neq k.
On note \mathcal{D}_n l’ensemble des dérangements de [\![1:n]\!] et D_n=\text{Card}(\mathcal{D}_n).
On pose F_i=\{s\in\mathcal{S}_n: s(i)=i\}. Alors \displaystyle D_n=\text{Card}(\mathcal{P}_n)-\text{Card}\left(\bigcup\limits_{1\leq i\leq n} F_i\right).
On a évidemment \text{Card}(\mathcal{P}_n)=n! .
On montre ensuite par récurrence la formule du crible : \displaystyle \text{Card}\left(\bigcup\limits_{1\leq i\leq n} F_i\right)=\sum_{\emptyset\neq \text{I}\subset[\![1,k]\!]}(-1)^{1+\text{Card}\text{I}}\text{Card}\left(\bigcap\limits_{i\in \text{I}} F_i\right).
Cette égalité est évidemment vérifiée au rang n=1. Supposons qu’elle est vraie au rang k\geq 1.
On a alors : \displaystyle \text{Card}\left(\bigcup\limits_{1\leq i\leq k+1} F_i\right)=\text{Card}\left(\bigcup\limits_{1\leq i\leq k} F_i\right)+\text{Card}(E_{k+1})- \displaystyle \text{Card}\left(\left(\bigcup\limits_{1\leq i\leq k} F_i\right)\bigcap F_{k+1}\right). (d’après le principe d’inclusion-exclusion)
Par distributivité de l’intersection par rapport à l’union, il vient : \displaystyle \text{Card}\left(\left(\bigcup\limits_{1\leq i\leq k} F_i\right)\bigcap F_{k+1}\right)= \text{Card}\left(\bigcup\limits_{1\leq i\leq k}\left( F_i\bigcap F_{k+1}\right)\right).
On utilise alors l’hypothèse de récurrence, ce qui donne \displaystyle \text{Card}\left(\bigcup\limits_{1\leq i\leq k+1} F_i\right)=\sum_{\emptyset\neq \text{I}\subset[\![1,k]\!]}(-1)^{1+\text{Card}\text{I}}\text{Card}\left(\bigcap\limits_{i\in \text{I}} F_i\right) \displaystyle +\text{Card}(F_{k+1})-\sum_{\emptyset\neq \text{I}\subset[\![1,k]\!]}(-1)^{1+\text{Card}\text{I}}\text{Card}\left(\bigcap\limits_{i\in \text{I}}\left(F_i\bigcap F_{k+1}\right)\right).
D’où \displaystyle \text{Card}\left(\bigcup\limits_{1\leq i\leq k+1} F_i\right)= \displaystyle \sum_{\emptyset\neq \text{I}\subset[\![1,k]\!]}(-1)^{1+\text{Card}\text{I}} \displaystyle \left(\text{Card}\left(\bigcap\limits_{i\in \text{I}}F_i\right)+ (-1) \text{Card}\left(\bigcap\limits_{i\in \text{I}}\left(F_i\bigcap F_{k+1}\right)\right)\right) +\text{Card}(F_{k+1}) .
Par associativité et commutativité de l’intersection, il vient \displaystyle \text{Card}\left(\bigcup\limits_{1\leq i\leq k+1} F_i\right)=\sum_{\emptyset\neq \text{I}\subset[\![1,k+1]\!]}(-1)^{1+\text{Card}\text{I}}\text{Card}\left(\bigcap\limits_{i\in \text{I}} F_i\right).
D’après le principe de récurrence, la formule du crible est vraie pour tout n\geq 1. \square
Ensuite, il est évident que \displaystyle \text{Card}\left(\bigcap\limits_{i\in \text{I}} F_i\right)=(n-\text{Card}(\text{I}))! (on a \text{Card}(\text{I}) points fixes, et on dénombre le nombre de permutations des éléments restants). De plus, on peut former \displaystyle {n\choose \text{Card}(\text{I})} ensembles inclus dans [\![1;n]\!] et de taille \text{Card}(\text{I}).
Il vient donc \displaystyle\text{Card}\left(\bigcup\limits_{1\leq i\leq n} F_i\right)= \displaystyle\sum_{\text{Card}(\text{I})=1}^n (-1)^{1+\text{Card}(\text{I})} {n\choose \text{Card}(\text{I})}(n-\text{Card}(\text{I}))! .
On a enfin \displaystyle\text{Card}\left(\bigcup\limits_{1\leq i\leq n} F_i\right)=n! \sum_{k=1}^n\frac{(-1)^{1+k}}{k!} .
En reprenant la formule initiale, il vient \displaystyle D_n= n!\left(1-\sum_{k=1}^n\frac{(-1)^{1+k}}{k!}\right)=n!\sum_{k=0}^n\frac{(-1)^k}{k!} .
La probabilité que personne ne tire le papier portant son propre nom est donc \displaystyle\mathbb{P}_n=\sum_{k=0}^n\frac{(-1)^k}{k!}. \square[/spoiler]
Edit : Ensuite je montre qu’elle converge et je détermine sa limite ?
Quel courage,écrire tout ça en latex!
En fait si tu remarques bien, l’énoncé ne précise pas combien il y a de personnes dans l’assemblé,c’est toi qui a introduit le n (et c’est ce qu’il fallait faire pour aboutir). Normalement tu n’es pas censé savoir que cette proba tends rapidement vers e^{-1} mais c’est le cas (et si ça trouve tu le sais déjà) 
.Puisque l’assemblée est « grande » on peut « raisonnablement » dire que cette proba vaut à peu prés 0,37. (tu y penseras en sup, quand vous vous ferez des cadeau de noël au hasard )
V@J proposait ça:
Alors voici comment je fais (il s’agit de calculer la probabilité qu’une permutation p_n choisie uniformément au hasard n’ait aucun point fixe) :
D’abord je calcule la probabilité q_{k,n} que 1 fasse partie d’un cycle de longueur k, pour 1 \leq k \leq n ; une récurrence immédiate sur n montre que q_{k,n} = \frac{1}{n}. Donc p_n = \sum_{k=2}^n q_{k,n} p_{n-k} = \frac{1}{n} \sum_{k=0}^{n-2}p_k = p_{n-1}+\frac{p_{n-2}-p_{n-1}}{n}, avec p_0 = 1 et p_1 = 0. Alors une seconde récurrence immédiate montre que p_n = \sum_{k=0}^n \frac{(-1)^k}{k!}
Je n’y avais vraiment pas pensé. C’est bien plus efficace et surtout ça économise du \LaTeX (j’ai vu apparaître très souvent [unparseable or potentially dangerous latex formula] )
La seule autre idée que j’avais eue était …
… d’établir une autre relation de récurrence (apparemment ça devrait être D_{n+1}=n(D_n+D_{n-1}) mais j’avais du mal à rédiger proprement une preuve combinatoire. Je réessayerai à l’occasion.
Pour rester dans les proba/combinatoire,un plus facile, histoire que des TS (autres que kkölc) puissent chercher.
Montrer pour n,l entiers positifs l’égalité:
\binom{n+l}{n}= \sum\limits_{k = 0}^l \binom{n+k-1}{n-1}
Pour une solution sans calcul: On peut « classer » les parties à n éléments de {1,2,3,…,n+l} en fonction de leur plus grand élément
J’essaye ! 
[spoiler]Par récurrence. On définit la proposition P : \binom{n+l}{n}= \sum\limits_{k=0}^l \binom{n+k-1}{n-1} avec n, l entiers positifs.
Initialisation, pour l=0 : \binom{n+0}{n}= 1 et \sum\limits_{k=0}^0 \binom{n+k-1}{n-1}= \binom{n-1}{n-1}= 1
On a donc P(0) vraie. On suppose alors qu’il existe un entier positif l tel que P est vraie. A t-on P(l+1) vraie ?
On a alors \sum\limits_{k=0}^{l+1} \binom{n+k-1}{n-1}= \sum\limits_{k=0}^l \binom{n+k-1}{n-1} + \binom{n+l}{n-1}
Grâce à l’HDR, on obtient donc que \sum\limits_{k=0}^{l+1} \binom{n+k-1}{n-1}= \binom{n+l}{n} + \binom{n+l}{n-1} et selon la formule de Pascal, on obtient \sum\limits_{k=0}^{l+1} \binom{n+k-1}{n-1}= \binom{n+l+1}{n} et donc P(l+1) est vraie.
Selon le principe du raisonnement par récurrence, j’en déduis que pour tous n,l entiers positifs, P est vraie : \binom{n+l}{n}= \sum\limits_{k=0}^l \binom{n+k-1}{n-1}
J’espère ne pas avoir écrit d’âneries 
[/spoiler]
Ça marche. 
Et pour la méthode sans calcul ?
Génial
Vais essayer de réfléchir à une méthode non-calculatoire…
Salut Steaks,
Tu as besoin de choses pour la méthode de kkohlc;
-Savoir qu il y k parmis n sous ensembles à k éléments d un ensemble à n éléments.
-de mon indication.
J’ai commencé ma réflexion mais j’ai du mal à décoller…
Je dois partir du fait qu’il y a \binom{n+l}{n} sous-ensembles à n éléments d’un ensemble à n+l éléments, et ensuite classer ces mêmes sous-ensembles en fonction de leur plus grand élément ? (c’est à dire ceux qui ont n, n+1, n+l comme plus grand élément) ? Ca ferait donc l+1 « types » de sous-ensembles, ce qui semble coller au nombre de termes de la somme. Après, je ne sais pas si je commence à avoir le début de quelque chose ou si je pars dans la mauvaise direction ! Merci d’avance pour les indications 
C’est le principe. Il te reste ensuite à dénombrer le nombre d’ensembles à n éléments ayant n+k pour plus grand élément.