Diophante vous invite à un superbe et long voyage dans la Voie Lactée (http://atunivers.free.fr/galaxy.html et http://www.cosmovisions.com/vola.htm). A bord d'un vaisseau spatial vous disposez de deux jeux identiques de n+1 batteries bleues (b) et rouges (r) numérotées par des entiers tous distincts :

b₀=0 < b₁ < b₂ < b₃...< b_n
r=0 < r₁ < r₂ < r₃ ...< r_n

Pour tout i, b_i = r_i
Pour atteindre une constellation de la Voie Lactée située à une distance d de la Terre et exprimée en nombre entier d'années lumière (AL), vous devez parcourir toutes les distances entières k comprises entre 1 et d en associant une batterie bleue b_i à une batterie rouge r_j de telle sorte que b_i + r_j = k. Chaque batterie peut être utilisée en tant que de besoin. Comme l'espace disponible à l'intérieur du vaisseau est réduit, il s'agit d'emporter le nombre minimum N_min de batteries pour effectuer la mission.

- Pour ceux qui ne connaissent que la Grande Ourse et la Petite Ourse : lors d'une première mission vous vous rendez sur Alkaïd qui est à l'extrémité du chariot de la Grande Ourse (http://www.cosmovisions.com/uma.htm) et se trouve à 100 AL de la Terre. Trouver N_min et la séquence correspondante des  b₁,b_2,b₃...,b_n .
- Pour ceux qui ont déjà eu la curiosité de consulter une carte du Ciel : lors d'une deuxième mission qui programme un voyage vers la grande nébuleuse d'Orion visible sous nos cieux pendant les mois d'hiver (http://www.cosmovisions.com/ori.htm), trouver N_min et la séquence correspondante des b₁,b_2,b₃...,b_n afin d'admirer la supergéante rouge Bételgeuse située dans cette constellation à 400 AL de la Terre.

- Pour les plus téméraires : comment rejoindre la constellation de la Lyre (http://www.cosmovisions.com/lyr.htm) pour contempler son fabuleux anneau situé à 2000 AL de la Terre. Les nostalgiques de l'année en cours pourront même faire un petit détour pour parcourir 2006 AL.

- Enfin pour les passionnés de l'espace, est-il possible de trouver une formule générale pour atteindre l'amas d'Hercule (http://www.cosmovisions.com/her.htm) situé à 20 000 AL de la Terre avant de se lancer dans un voyage intergalactique à la conquête de la galaxie d'Andromède (http://www.cosmovisions.com/and.htm) qui est à 2,5 millions AL.

PS : Rappelons que dans tous les cas il s'agit de sauts de puce car les confins de l'univers sont situés à 14 milliards d'AL environ.

Source : Pierre Henri Palmade

 Solution