Un peu de combinatoire

Page 2 sur 2 Précédent  1, 2

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

Re: Un peu de combinatoire

Message par Phi le Mer 11 Juin - 21:03

Je n'exclus pas m'être mal souvenu de l'énoncé du 6.

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par baptiste collet le Mer 11 Juin - 21:10

le seul truc étrange est que le 2) est plus facile et que le 1) pour le 2) il suffit de sortir l'exemple où toutes les distances changent

baptiste collet
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 49
Date d'inscription : 27/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Sam 14 Juin - 19:02

Bon je pense avoir trouvé le 4, mais ce n'est pas bien joli du tout  pale 
Pour ceux qui tiennent à leurs yeux, je peux déjà les informer que la preuve commence par l'expression du terme général de \(a_n\)  affraid 
Du coup je serais curieux de connaître la preuve de Phi, car celle-ci est plutôt bestiaaaaale  What a Face ...

Ex 4:


Pour commencer  Embarassed ,
$$ a_n=\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2 \sqrt{2}} $$
Dès lors, avec \(n=i2^k\) (\(i\) impair), il nous suffit de montrer que
$$A=\frac{(1+\sqrt{2})^{i2^k}-(1-\sqrt{2})^{i2^k}}{2^{k+1} \sqrt{2}} $$
est entier  Twisted Evil 
Sauf qu'en factorisant on obtient que \(A\) vaut
$$\frac{[(1+\sqrt{2})^{i2^{k-1}}+(1-\sqrt{2})^{i2^{k-1}}][(1+\sqrt{2})^{i2^{k-2}}+(1-\sqrt{2})^{i2^{k-2}}]...}{2^k}\frac{(1+\sqrt{2})^i-(1-\sqrt{2})^i}{2 \sqrt{2}}$$
On voit alors que le dernier terme est \(a_i\), et donc entier, ensuite il ne nous reste que des termes de la forme
$$\frac{1}{2}\left(\sum_{m=0}^{\alpha}\binom{m}{\alpha}2^{\frac{m}{2}}+\sum_{m=0}^{\alpha}\binom{m}{\alpha}2^{\frac{m}{2}}(-1)^m\right)$$
Les termes avec \(m\) impair non nécessairement entiers s'annulent, et les autres sont bien divisibles par 2, donc c'est bon   drunken 


avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Sam 14 Juin - 20:08

Ex4—version un peu moins bestiale:

D'abord on a clairement $$a_2=2$$
On va montrer par récurrence sur k que pour tout n et pour tout k entiers positifs, on a:
$$ a_n=a_k*a_{n+1-k}+a_{k-1}*a_{n-k} $$ (*)
Clairement, c'est vrai pour k=1 et k=2.
Soit k entier strictement positif supérieur ou égal à 2 tel que (*) soit vrai pour tout n.
Alors pour tout n, on a
$$ a_n=(2a_k+a_{k-1})*a_{n-k}+a_k*a_{n-k-1} $$ avec la relation de récurrence.
$$ a_n=a_{k+1}*a_{n+1-(k+1)}+a_{k+1-1}*a_{n-(k+1} $$ ce qui clôt la récurrence.

On remarque ensuite que $$a_n$$ est de même parité que n.
De plus (*) nous donne $$ a_{2n}=a_n*a_{n+1}+a_n*a_{n-1} $$
Ceci se réécrit $$ a_{2n}=2a_n*(a_n+a_{n-1}) $$
Comme $$ a_n+a_{n-1} $$ est impair, on a alors:
$$ v_2(a_{2n})=v_2(a_n) +1 $$
Il s'ensuit par une récurrence immédiate que, pour $$ n=2^i*(2p+1) $$
$$ v_2(a_n)=i+v_2(a_{2p+1})=i=v_2(n) $$, CQFD.


PS: si vous savez comment je pourrais mieux utiliser le LaTex (si c'est bien ça), je suis tout à fait intéressé.

Touveutoubé: je me trompe peut-être (ou alors j'ai mal formulé le problème) mais je crois que tu ne montres pas que k est l'exposant maximal de 2 pour a(n).

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Sam 14 Juin - 20:50

Oui, merci, je vois ce que tu veux dire : il faut préciser que ce que j'appelais les autres termes divisibles par 2 ne sont pas divisibles par 4.

Pour le LaTeX, si ta question est d'apprendre à l'utiliser, il y a bcp de tutoriels très bons en ligne, par exemple

http://fr.openclassrooms.com/informatique/cours/redigez-des-documents-de-qualite-avec-latex

http://www.tuteurs.ens.fr/logiciels/latex/

http://www.grappa.univ-lille3.fr/FAQ-LaTeX/

Mais peut-être que tu sais déjà tout ça et que j'ai mal compris...Sinon, les * ne sont pas nécessaires, et tu peux mettre des formules dans le corps du texte (plutôt que toujours centré) en les entourant de \( et de \42 (avec à la place du 42 une parenthèse fermée, sauf que si je la fais il y aura simplement marqué "et" en police Computer Modern...)

En tout cas bravo pour ta preuve qui est bien plus élégante que la mienne (enfin ça c'était pas très difficile, mais c'est joli dans l'absolu) !!
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Dim 15 Juin - 7:44

Merci pour les tutoriels de LaTex mais (même si je ne connais que très peu) ce n'était pas ça que je cherchais mais plutôt comment ne pas avoir besoin de centrer mes formules. Donc merci pour ça.

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Dim 15 Juin - 8:32

OK, je n'étais pas sûr d'avoir bien compris la question du coup j'ai répondu aux deux interprétations possibles...

Sinon en repensant à l'exercice 2 cela m'a fait penser à un exo de taupin croisé récemment : montrer que S(n) vaut asymptotiquement n!
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Dim 15 Juin - 14:48

Spoiler:

Soit \(T_n=\frac{S_n}{n!}\).
Alors \(T_{n+1}=1+\frac{T_n}{n+1} \). (*)
Clairement en remplaçant par l'expression exacte \(T_n \geq 1+\frac{1}{n}\geq 1 \).
D'autre part \(T_{n} \geq T_{n+1} \) ssi \( \frac{nT_n}{n+1} \geq 1\) d'après (*)
C'est à dire ssi \( T_n \geq \frac{n+1}{n} \), ce qui est clairement vrai.
La suite \((T_n)\) est donc décroissante et minorée, donc elle converge vers \(l\).
Or (*) nous donne que \(lim_{n -> \infty}1+\frac{l}{n+1}=l\) soit \(l=1\), CQFD.
(J'espère juste ne pas m'être trompé sur le sens de "asymptotiquement égal)

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Dim 15 Juin - 15:23

Nan nan cela me paraît bon, mais je me demande si les taupins feraient comme ça...
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Page 2 sur 2 Précédent  1, 2

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