Les iles perdu !! HELP

Bonsoir,

J'ai besoin d'aide sur cette exercice, j'ai mis la 1ere question les autres (plus difficile) vont venir aprés !

Un océan a une infinité d'îles. Chaque île est marqué par l'un des nombres entiers {..., -3, -2, -1,0,1,2,3, ...,} sans deux îles ayant le meme nombre et tout entier étant le nombre d'une certaine île. Deux îles sont reliées par un pont, si leurs nombre diffèrent par une puissance de deux. Par exemple, il ya un pont reliant l'île 7 et l'île -25.

On définit la distance entre deux îles k1 et k2 étant le nombre minimal de ponts nécessaires pour partir de k1 à k2. Par exemple, la distance entre les îles 0 et 7 est de 2. (Vous pouvez vous déplacer d'île 0 à 8, puis à l'île 7; c'est le minimum, puisque vous ne pouvez pas aller de 0 à 7 en utilisant un seul pont.)

Montrer que pour tout entier r ≥ 1, vous pouvez trouver deux îles dans l'océan à une distance r l'une de l'autre.


Amusez vous bien et merci !

SOS
SOS
SOS
SOS

Aucune idee les mecs ?

Bonsoir :
Il s'agit de montrer que pour tout r il existe un entier naturel a qui s'écrit comme somme d'au moins r puissances de 2 ( ainsi on pourra allez de l'île 0 à l'île a ) :
Par récurrence pour r = 1 , a = 3 marche :
Supposons qu'il existe a_(r) >=3 tel que le résultat soit vrai au rang r :
On vas prouver que a_(r)+2^(a_(r)-1) marche .
il est évident que a_(r)+2^(a_(r)) s'écrit comme somme de r+1 puissances de 2 , montrons qu'on ne peut pas faire mieux :
supposons qu'on a a_(r)+2^(a_(r))=sum ( k=1..r-1) epsilon_(k)* 2^(alpha_k)
avec epsilon_(k)=1 ou - 1 et (alpha_k)k des entiers .
Supposons que tout les alpha_(k) sont différents de a_(r) , si tout les epsilon_(k) sont positifs , alors le terme de droite est inférieur ou égal à 2^(a_(r)) -2 contradiction .
Donc il y a au moins un terme négatif mais alors le terme de droite est supérieur ou égal à 2^(a_(r)+1)-2^(a_(r))+2, un rapide calcul montre que ce n'est pas possible pour a_(r)>=

3 . D’où un des alpha_(k) est égal à a_(r) et on a une contradiction avec l' H.P .
Le second point nécessite une petit explication : Si il y a des epsilon_k qui sont négatifs alors
il y a forcément un alpha_(k)>=a_(r) , mais alors le minimum qu'on puisse faire c'est 2^(a_(r)+1)- sum (k=1..a_(r)-1) 2^(k) qui donne le résultat voulu .
Sauf erreur .