Arithmétique

[Anonyme]

Bonjour,

voici un petit problème qui me bloque un peu.
On note E_n = {nombres de n chiffres s'écrivant uniquement avec des 1 et
des 2}. Par exemple E_2 = {11, 12, 21, 22}.
Il est clair que pour tout n, card(E_n) = 2^n.

Il faut montrer que pour tout n, il existe un unique a_n dans E_n tel
que 2^n divise a_n.
Au départ j'avais pensé à quelque chose du type principe des tiroirs
mais le fait que E_n ne soit pas stable par soustraction/addition me
psoait problème. J'ai donc regardé quels étaient les premiers termes de
la suite a_n :

1 2 2^1
2 12 2^3 + 2^2
3 112 2^6 + 2^5 + 2^4
4 2112 2^11 + 2^6
5 22112 2^14 + 2^12 + 2^10 + 2^9 + 2^6 + 2^5
6 122112 2^16 + 2^15 + 2^14 + 2^12 + 2^11 + 2^10 + 2^8
7 2122112
8 12122112
9 212122112

Il semblerait donc qu'il y ait une relation entre a_n+1 et a_n.

Ma question est donc : doit on se servir de cette relation pour répondre
à la première question (existence et unicité de a_n). Si non, peut-on
montrer la relation entre a_n+1 et a_n ?

Merci d'avance pour votre aide.

--
albert

[Anonyme]

> voici un petit problème qui me bloque un peu.
> On note E_n = {nombres de n chiffres s'écrivant uniquement avec des 1 et
> des 2}. Par exemple E_2 = {11, 12, 21, 22}.
> Il est clair que pour tout n, card(E_n) = 2^n.
>
> Il faut montrer que pour tout n, il existe un unique a_n dans E_n tel que
> 2^n divise a_n.
> Au départ j'avais pensé à quelque chose du type principe des tiroirs mais
> le fait que E_n ne soit pas stable par soustraction/addition me psoait
> problème. J'ai donc regardé quels étaient les premiers termes de la suite
> a_n :
>
> 1 2 2^1
> 2 12 2^3 + 2^2
> 3 112 2^6 + 2^5 + 2^4
> 4 2112 2^11 + 2^6
> 5 22112 2^14 + 2^12 + 2^10 + 2^9 + 2^6 + 2^5
> 6 122112 2^16 + 2^15 + 2^14 + 2^12 + 2^11 + 2^10 + 2^8
> 7 2122112
> 8 12122112
> 9 212122112


Pour l'existence, on peut simplement dire: si a_n est divisible par 2^n, on
écrit a_n=2^n * b_n. On a alors 10^n+a_n=2^n * (5^n + b_n). Si b_n est pair,
a_(n+1)=10^n+a_n convient. Sinon, 2*10^n+a_n=2^n*(2*5^n+b_n) convient.

--
Mû

[Anonyme]

> Pour l'existence, on peut simplement dire: si a_n est divisible par 2^n,
> on écrit a_n=2^n * b_n. On a alors 10^n+a_n=2^n * (5^n + b_n). Si b_n est
> pair, a_(n+1)=10^n+a_n convient. Sinon, 2*10^n+a_n=2^n*(2*5^n+b_n)
> convient.


Lire "b_n impair".

--
Mû

[Anonyme]

> Pour l'existence, on peut simplement dire: si a_n est divisible par 2^n,
> on écrit a_n=2^n * b_n. On a alors 10^n+a_n=2^n * (5^n + b_n). Si b_n est
> pair, a_(n+1)=10^n+a_n convient. Sinon, 2*10^n+a_n=2^n*(2*5^n+b_n)
> convient.

Pour l'unicité, on fait la même chose en descendant: si 2^n divise a_n pour
un certain n, et qu'on note c_n le nombre a_n privé de son premier chiffre,
on a c_n=a_n-10^(n-1) ou a_n-2*10^(n-1), donc 2^(n-1) divise c_n. En
itérant, on tombe forcément sur 2. Et vu qu'il n'y a qu'une seule manière de
remonter (voir ci-dessus), c'est bon. A écrire proprement, évidemment.

--
Mû

[Anonyme]

µ a écrit:

> Pour l'unicité, on fait la même chose en descendant: si 2^n divise a_n pour
> un certain n, et qu'on note c_n le nombre a_n privé de son premier chiffre,
> on a c_n=a_n-10^(n-1) ou a_n-2*10^(n-1), donc 2^(n-1) divise c_n. En
> itérant, on tombe forcément sur 2. Et vu qu'il n'y a qu'une seule manière de
> remonter (voir ci-dessus), c'est bon. A écrire proprement, évidemment.
>

Merci beaucoup.

--
albert

[Anonyme]

albert junior wrote:
> Bonjour,
>
> voici un petit problème qui me bloque un peu.
> On note E_n = {nombres de n chiffres s'écrivant uniquement avec des 1 et
> des 2}. Par exemple E_2 = {11, 12, 21, 22}.
> Il est clair que pour tout n, card(E_n) = 2^n.
>
> Il faut montrer que pour tout n, il existe un unique a_n dans E_n tel
> que 2^n divise a_n.
> Au départ j'avais pensé à quelque chose du type principe des tiroirs
> mais le fait que E_n ne soit pas stable par soustraction/addition me
> psoait problème. J'ai donc regardé quels étaient les premiers termes de
> la suite a_n :
>
> 1 2 2^1
> 2 12 2^3 + 2^2
> 3 112 2^6 + 2^5 + 2^4
> 4 2112 2^11 + 2^6
> 5 22112 2^14 + 2^12 + 2^10 + 2^9 + 2^6 + 2^5
> 6 122112 2^16 + 2^15 + 2^14 + 2^12 + 2^11 + 2^10 + 2^8
> 7 2122112
> 8 12122112
> 9 212122112
>
> Il semblerait donc qu'il y ait une relation entre a_n+1 et a_n.
>
> Ma question est donc : doit on se servir de cette relation pour répondre
> à la première question (existence et unicité de a_n). Si non, peut-on
> montrer la relation entre a_n+1 et a_n ?
>
> Merci d'avance pour votre aide.

Si tu considère l'ensemble des x - 1111.... où x appartient à E_n, tu
vois que l'écriture en base 10 de ces nombres correspond à l'ensemble
des nombres de 0 à 2^n - 1 écrits en base 2. Tu peux ensuite considérer
la congruence [2^n] des élements de cet ensemble, et en déduire
l'existence et l'unicité de a_n.