SEED Science

Solution : énigme de mai 2004 : Encore d'autres arbres en rangs d'oignons

Solution : énigme de mai 2004

Encore d'autres arbres en rangs d'oignons

Lawrence Lee a démontré qu'il n'y avait pas de solution, alors qu'Igor Markov en a trouvée une. Tout dépend de la manière dont vous interprétez le problème.

Pour Igor :

Cette solution peut sembler trop banale ou « de la triche » pour beaucoup, mais je la considère quant à moi comme une façon de tirer avantage de la manière dont le problème est énoncé.

A l'origine, le problème est le suivant : Vous disposez de 10 arbres. Vous devez les planter sur 4 rangées, chacune contenant 5 arbres.
Supposons que nous plantions les arbres sur 1 seule rangée de dix arbres :

Vous pouvez identifier un grand nombre de rangées uniques. Voici quatre exemples :

  1. A, B, C, D, E
  2. B, C, D, E, F
  3. C, D, E, F, G
  4. D, E, F, G, H

Notez que le problème ne précise en aucun cas que les rangées doivent être de longueur identique. Vous pouvez donc définir une rangée en sautant des arbres, ce qui augmente le nombre de possibilités. Exemple :

A, C, F, I, J

Enfin, le problème ne précise nulle part que les rangées doivent être uniques. Ceci permet une infinité de solutions. Exemple :

  1. A, B, C, D, E
  2. A, B, C, D, E
    .
    .
    .

     n) A, B, C, D, E

Lawrence exclut les rangées d'arbres qui sont colinéaires. Trois points ou davantage sont colinéaires s'ils sont alignés. Les arbres d'une même rangée sont donc colinéaires. La solution d'Igor est valable à condition que tous les arbres soient alignés, de sorte à être colinéaires. Lawrence ne permet pas cet état des choses. Il interprète le problème de telle sorte que chaque rangée d'arbres se trouve sur une ligne droite différente.

Voici l'explication de Lawrence :

Je vais vous prouver que ce problème n'est pas valide dans l'espace euclidien, car il n'a pas de solution.

Décidons d'abord qu'il est impossible à 2 des 4 rangées d'être colinéaires. (Sinon, le problème n'est pas très compliqué.)

 

 

A) Plantons la première rangée d'arbres. Par définition, nous avons besoin de 5 arbres. Nous appelons cette rangée A. Il nous reste maintenant 5 arbres.

 

B) Plantons maintenant la deuxième rangée d'arbres. Etant donné que cette rangée ne peut pas être colinéaire avec la rangée A, elle ne peut partager qu'1 arbre maximum avec la rangée A. Pour cette rangée, il nous faut au moins 4 arbres supplémentaires. Appelons cette rangée B. Il nous reste maintenant 1 arbre. (Est-ce que vous commencez à comprendre où je veux en venir ?)

C) Plantons maintenant la troisième rangée d'arbres. Pour que celle-ci ne soit pas colinéaire avec les rangées A et B, elle ne doit avoir qu'1 seul arbre maximum en commun avec la rangée A et 1 seul arbre maximum en commun avec la rangée B. Pour cette rangée, il faut au moins 3 autres arbres. Zut, il ne nous reste qu'1 seul arbre !

Ce problème n'a donc pas de solution valide, sauf si l'espace est faussé.