Bonjour, voici un sujet de l'X d'info, mais mon pb se situe plus dans la partie mathématique de la question 6 et 7, je dois dire que j'ai un peu de mal avec les diférentes suites, ce serai sympa si qqun pouvait m'expliquer notamment la suite (ti) et la suite (Si).
merci d'avance
http://www.polytechnique.fr/concours...t00/InfoMP.pdf
On a T(4)=<0,1,0,2,0,1,0,3,0,1,0,2, 0,1,0>
t0 est le (0+1)-ème terme donc le premier soit 0 qui n'est pas présent dans S0, aucun autre n'est dans S0, donc S1={0}
t1 est le deuxième terme soit 1, 1 n'est pas dans S2 donc S2=S1 U {t1}={0,1}
t2=0 S3=S2\{0} car 0 est dans S2 S3={1}
t3=2 S4={1,2} 2 n'était pas dans S3
t4=0 "non présent donc s'ajoute" S5={0,1,2}
...
D pour désigner delta :
Si D {ti}= (Si\{ti}) U ({ti}\Si)
Deux possibilités : ti est dans Si ou ne l'est pas
si ti y est alors {ti}\Si=vide et S(i+1)=Si\{ti} =Si auquel on retire ti
si ti n'y est pas alors Si\{ti}=Si et {ti}\Si={ti} donc S(i+1)=Si U {ti}=Si auquel on ajoute {ti}
Pour un nombre n donné, on a ceci (après sens large, avant sens strict) :
avant sa 1ère apparition il n'est pas dans Si
après 1ère et avant 2ème il n'y est
après 2ème et avant 3ème il n'y est plus
...
Il est donc dans Si si et seulement si il apparaît un nombre impair de fois entre la 1ère et la i-ème position.
Le reste s'en déduit alors facilement.
merci bcp!!!!!
