Voici le 3ème défi de l'année. Pour décorer votre sapin, vous n'utilisez que des étoiles et vous procédez ainsi : vous débutez par une étoile en haut ; ensuite, sous chaque étoile, vous placez une étoile à gauche ou à droite, ou les deux, ou rien du tout... Jusqu'à n'avoir plus aucune étoile sous la main.
Défi : avec 2016 étoiles, quelle est la plus petite hauteur possible pour votre sapin ? Par hauteur, il faut comprendre le nombre d'étages intermédiaires ; par exemple, le sapin dans l'image ci-contre a une hauteur de 2. S'il n'y avait eu qu'une étoile, on aurait attribué une hauteur nulle.
Tentez votre chance en postant une réponse en commentaire !
4 réactions
1 De Jean-Baptiste chagnoleau - 20/12/2015, 18:14
Pour obtenir la plus petite hauteur possible on place le plus d'étoile possible par étages. Autrement dit tant que cela est possible on place sous chaque étoile deux étoiles. On numérote les étages de haut en bas. Le n-iéme étages peut contenir au maximum 2^n étoiles. On utilise ensuite un algorithme dont voici le code:
k=2016
n=0
while k>2**n:
print(n-1,k)
Ce code nous permet de trouver que l'on peut avec 2016 étoiles remplir 9 étages est qu'il y aura 993 étoiles sur le dernier étages (pouvant en accueillir 2^10=1024).
Ainsi la plus petite hauteur possible pour le sapin est 9
2 De Romain Validire - 20/12/2015, 21:20
C'est étonnant, si je reprends votre démarche avec k=6 étoiles, je trouve que j'arrive à une hauteur minimale pour mon sapin égale à 1. Hors dès qu'on a au moins 4 étoiles la hauteur est au moins égale à 2....
3 De Seigneur Foulques - 29/01/2016, 00:25
Pour que le sapin ait une hauteur minimale, il faut que chaque étoile repose sur deux étoiles pour tous les étages jusqu'à la base.
Ainsi le nombre E(n) d'étoiles utilisées pour l'étage n vaut 2*E(n-1), en comptant les étages de haut en bas. On reconnaît là une suite géométrique de raison 2 dont la somme donne le nombre total d'étoiles utilisées. Soit U(n) le nombre total d'étoiles utilisées ; U(n) = somme pour k allant de 1 à n des 2^k. On a bien U(0)=1, U(1)=3 etc... Que vaut cette somme ? L'élève de prépa averti reconnaîtra aisément ce cas bien connu, U(n) = 2^(n+1)-1.
[[[[[Preuve : somme des termes d'une suite géométrique pour k allant de 0 à n de raison q :
(1-q^(n+1))/(1-q)
Ici q=2 :
U(n)=(1-2^(n+1))/(1-2)
U(n)=(1-2^(n+1))/(-1)
U(n)=-(1-2^(n+1))
U(n)=2^(n+1)-1 : fin de la preuve ]]]]]
Donc, U(n)=2^(n+1)-1.
Mais, comme dirait Achille Talon, "bof." : il faut poursuivre ! On veut trouver n tel que U(n)=2016
soit :
2^(n+1)-1=2016
2^(n+1)=2015
e^((n+1)ln(2))=2015
(n+1)ln(2)=ln(2015)
n+1=ln(2015)/ln(2)
n+1=log2(2015)
n=log2(2015)-1
Attention ! Ce résultat et sa méthode de calcul peuvent se révéler très utiles en informatique pour calculer la complexité d'un programme (notamment dans les fonctions récursives au programme de PC).
La gentille calculatrice nous indique 10,97 environ. Nous en déduisons que nous avons dix étages complets, plus un onzième étage composé pour une part d'étoiles se trouvant sous d'autres étoiles, et pour le reste de vides (autorisés par l'énoncé).
En conclusion, un sapin de 2016 étoiles fera au moins onze étages : sa hauteur minimale est de 10.
4 De Romain Validire - 29/01/2016, 17:23
Suite à une erreur technique, des réponses ont disparu dans l'abîme des indésirables...
En conséquence, voici une rafale de points pour ce défi :
Adrien : 1 point, Alex : 1 point, Clément : 1 point,
et naturellement, Foulques : 1 point.
Félicitations à tous et tout particulièrement à Foulques pour la qualité de sa démonstration.