Aide pour les futurs mathématiciens
 
AccueilAccueil  PortailPortail  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  Connexion  

Partagez | 
 

 Les iles perdu !! HELP

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
momokani
Habitué


Masculin Nombre de messages : 16
Age : 25
Date d'inscription : 14/02/2012

MessageSujet: Les iles perdu !! HELP   Dim 22 Avr 2012, 22:10

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 !
Revenir en haut Aller en bas
momokani
Habitué


Masculin Nombre de messages : 16
Age : 25
Date d'inscription : 14/02/2012

MessageSujet: Re: Les iles perdu !! HELP   Mar 24 Avr 2012, 07:55

SOS
SOS
SOS
SOS
Revenir en haut Aller en bas
momokani
Habitué


Masculin Nombre de messages : 16
Age : 25
Date d'inscription : 14/02/2012

MessageSujet: Re: Les iles perdu !! HELP   Mer 25 Avr 2012, 08:06

Aucune idee les mecs ?
Revenir en haut Aller en bas
darkpseudo
Expert sup


Masculin Nombre de messages : 817
Age : 24
Date d'inscription : 31/10/2009

MessageSujet: Re: Les iles perdu !! HELP   Jeu 26 Avr 2012, 22:59

Bonsoir Smile :
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 .
Revenir en haut Aller en bas
Contenu sponsorisé




MessageSujet: Re: Les iles perdu !! HELP   

Revenir en haut Aller en bas
 
Les iles perdu !! HELP
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Les iles perdu !! HELP
» La météo à temps perdu
» J'ai perdu le gout
» J'ai perdu ma foi et je le vis mal
» je suis totalement perdu

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum des amateurs de maths :: Olympiades :: Arithmétiques-
Sauter vers: