arithmétique et permutation
dans Arithmétique
Bonjour,
j'ai retrouvé un exercice de niveau L1, mais je n'ai pas retrouvé la correction.
On note E l'ensemble des $\N^p$ pour $p\geq 1$ : $E=\{ \N^{p}, p\in\N^* \}$
Les fonctions $d$,$\sigma$,$g$ et $f$ sont définies sur E de la façon suivante :
si $u\in E$, il existe un unique $p\geq 1$ tel que $u\in \N^p$
on note $d(u)=p$
on définit :
$\sigma(u)=(u_2,u_3,....,u_p,u_1) \in \N^p$
$g(u)=\sigma(u)-u=(u_2-u_1,u_3-u_2,....,u_p-u_{p-1},u_1-u_p) \in \N^p$
et $f(u)=(|u_2-u_1|,|u_3-u_2|,....,|u_p-u_{p-1}|,|u_1-u_p|) \in \N^p$
La question est la suivante :
soient $d\in\N^*$ et $u\in E$ tels que $d(u)=2^d$,
montrer qu'il existe $N\in\N$ tel que $f^N(u)=(0,....,0)$ (la composée nième)
En est t'il toujours de même pour g ?
J'ai montré ce résultat pour d=1,2 et 3, je suis sûr que je pourrai le faire pour d=4, mais pour le cas général, je n'ai pas encore cherché, je n'ai pas eu le temps.
Peut être que c'est évident, mais vu que je me suis borné avec une méthode...
j'ai retrouvé un exercice de niveau L1, mais je n'ai pas retrouvé la correction.
On note E l'ensemble des $\N^p$ pour $p\geq 1$ : $E=\{ \N^{p}, p\in\N^* \}$
Les fonctions $d$,$\sigma$,$g$ et $f$ sont définies sur E de la façon suivante :
si $u\in E$, il existe un unique $p\geq 1$ tel que $u\in \N^p$
on note $d(u)=p$
on définit :
$\sigma(u)=(u_2,u_3,....,u_p,u_1) \in \N^p$
$g(u)=\sigma(u)-u=(u_2-u_1,u_3-u_2,....,u_p-u_{p-1},u_1-u_p) \in \N^p$
et $f(u)=(|u_2-u_1|,|u_3-u_2|,....,|u_p-u_{p-1}|,|u_1-u_p|) \in \N^p$
La question est la suivante :
soient $d\in\N^*$ et $u\in E$ tels que $d(u)=2^d$,
montrer qu'il existe $N\in\N$ tel que $f^N(u)=(0,....,0)$ (la composée nième)
En est t'il toujours de même pour g ?
J'ai montré ce résultat pour d=1,2 et 3, je suis sûr que je pourrai le faire pour d=4, mais pour le cas général, je n'ai pas encore cherché, je n'ai pas eu le temps.
Peut être que c'est évident, mais vu que je me suis borné avec une méthode...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
(si le modérateur le veut bien, sinon à lire ici)
Ce n'est pas $\N^p$ mais $\Z^p$ qu'il faut lire, partout où il y a $\N^p$
Je réécris ici pour que le modérateur n'ait pas à tout modifier
Bonjour,
j'ai retrouvé un exercice de niveau L1, mais je n'ai pas retrouvé la correction.
On note E l'ensemble des $\Z^p$ pour $p\geq 1$ : $E=\{ \Z^{p}, p\in\N^* \}$
Les fonctions $d$,$\sigma$,$g$ et $f$ sont définies sur E de la façon suivante :
si $u\in E$, il existe un unique $p\geq 1$ tel que $u\in \Z^p$
on note $d(u)=p$
on définit :
$\sigma(u)=(u_2,u_3,....,u_p,u_1) \in \Z^p$
$g(u)=\sigma(u)-u=(u_2-u_1,u_3-u_2,....,u_p-u_{p-1},u_1-u_p) \in \Z^p$
et $f(u)=(|u_2-u_1|,|u_3-u_2|,....,|u_p-u_{p-1}|,|u_1-u_p|) \in \Z^p$
La question est la suivante :
soient $d\in\N^*$ et $u\in E$ tels que $d(u)=2^d$,
montrer qu'il existe $N\in\N$ tel que $f^N(u)=(0,....,0)$ (la composée nième)
En est t'il toujours de même pour g ?
J'ai montré ce résultat pour d=1,2 et 3, je suis sûr que je pourrai le faire pour d=4, mais pour le cas général, je n'ai pas encore cherché, je n'ai pas eu le temps.
Peut être que c'est évident, mais vu que je me suis borné avec une méthode...
oui en effet $E=\cup \Z^p$, c'est une erreur de ma part.
f est définie sur E et non pas sur un $\Z^p$. Si ça pose un problème, on peut la définir sur $\Z^p$, ça ne change rien.
Mais si elle a été définie comme ça, c'est parce que l'exercice a des questions avant,
il y a des calculs de $f(f(u),f(v))$ et après elle est prolongée sur des classes d'équivalence $E/\sigma$.
mais ça ne m'intéresse pas donc ici on peut la définir sur $\Z^p$
Soit f définie sur $\Z^p$ avec $p=2^d$ par
et $ f(u)=(\vert u_2-u_1\vert,\vert u_3-u_2\vert,....,\vert u_p-u_{p-1}\vert,\vert u_1-u_p\vert) \in \mathbb{Z}^p$
montrer qu'il existe $ N\in\mathbb{N}$ tel que $ f^N(u)=(0,....,0)$ (la composée nième)
C'est plus compréhensible comme ça.
On en déduirait que les p suites composantes convergent donc stationnent... et par voie de conséquence stationnent en 0 en utilisant le fait que p est une puissance de 2.
Tout cela est purement intuitif. J'espère que ça pourra t'aider.
merci
Le seul point qui coince est le fait que les suites stationnent en 0 car ce n'est pas vrai : on peut seulement prouver que l'une d'entre elles tend vers 0 et les 2 autres vers le même limite nulle ou non.
$$(0,1,1) \mapsto (1,0,1) \mapsto (1,1,0) \mapsto (0,1,1)$$
f(x,x)=(f(x),f(x))
mais pour prouver qu'on peut se ramener à ce cas, c'est pas plus simple que de montrer qu'on arrive à 0.
j'ai remarqué, après sueur, qu'il suffit de prendre des p-uplets d'entiers entiers compris entre 0 et 1, car si on regarde les entiers modulo 2, tomber sur 0 après un certain nombre de coup signifie qu'on peut tout factoriser par 2, et f(2u)=2f(u), au bout d'un certain moment on aura $f^n(u)=2^kf(v)$, or on voit bien que
$||f^n(u)||\leq ||f(u)||$ si je prends pour norme le max des valeurs absolues du p-uplet, donc si k devient grand, f(v)=0
selon moi, il suffit de montrer le résultat pour des p-uplets avec des 0 et des 1
je vous expliquerai ce soir, là je n'ai pas le temps
Les éléments de $g(u)$ sont de somme nulle.
Les éléments de $f(u)$ sont des distances entre éléments de $u$, lesquels sont positifs (sauf éventuellement le premier terme de la suite). Donc le max de ces éléments des décroissants.
Les éléments de $u$ et $f(u)$ ont même pgcd...
dans $\Z/2\Z$, je note $\bar{x}$ la classe de x, si x est dans $\Z$
et aussi dans $\Z/2\Z^p$ , $\bar{u}=(\bar{u_1},...,\bar{u_p})$
j'ai remarqué que pour tout $u\in\Z^p$, $f(\bar{u})=\bar{f(u)}$, donc pour tout $n\in\N$, $f^n(\bar{u})=\bar{f^n(u)}$
Aussi $f(2u)=2f(u)$
De plus si on note pour $u\in\Z^p$ $\|u\|=\max(|u_i|)$, on a pour tout $n\in\N^*$ , $\|f^n(u)\| \leq \|f(u)\|$.
Donc si on montre qu'il existe N tel que pour tout $v\in\{0,1\}^p$ $f^N(v)=0$, alors pour tout $u\in\Z^p$, $\bar{f^N(u)}=f^N(\bar{u})=0$
ainsi, si on fixe u, $f^N(u)$ est un multiple de 2, il existe $a\in\Z^p$ tel que $f^N(u)=2a$, et ainsi $f^{2N}(u)=2f^N(a)$ ....
par récurrence, il existe $a_k\in\Z^p$ tel que $f^{kN}(u)=2^ka_k$
Mais comme $\|f^{kN}(u)\| \leq \|f(u)\|$ on a $2^k \|a_k\| \leq \|f(u)\|$ pour tout k, ce qui nécéssite que à partir d'un certain k, $a_k=0$, le résultat serait prouvé.
Le problème se ramène à montrer que pour tout $ v\in\{0,1\}^p$ il existe N tel que $ f^N(v)=0$,
(comme $\{0,1\}^p$ est de cardinal fini $2^p$, on prend le max des N, et ça revient à montrer qu'il existe N tel que pour tout $ v\in\{0,1\}^p$ $ f^N(v)=0$)
d'abord, on voit que $f(u)$ et $g(u)$ ont la même parité, car la valeur absolue ne change pas la parité d'un nombre.
or $g=id-\sigma$
$\sigma$ est "linéaire" , $g^2=id-2\sigma+\sigma^2$
et $\displaystyle g^p=\sum_{k=0}^{p} \text{C}_p^k (-1)^k \sigma^k$
Or comme p est une puissance de 2, pour $0