10 arbres - solution

On veut planter 5 alignements de 4 arbres. Ce qui fait 10 arbres seulement

Une solution simple est le pentagramme régulier. Mais il y en a d'autres !
Nous allons étudier le cas général de n alignements de n - 1 arbres.

Le 1er cas à considérer est 3 alignements de 2 arbres : une seule possibilité, un triangle.
Avec 4 alignements, il y a aussi une seule possibilité, un "quadrilatère complet"
A partir de cette configuration, en ajoutant une 5ème droite, nous allons déduire toutes les configurations avec 10 points sur 5 droites.

Donnons tout d'abord quelques formules générales.

Avec n alignements, soit n droites, il y a S(n) = C_n² = n(n-1)/2 points d'intersection.
Sur chaque droite il y a n - 2 segments. Soit en tout, A(n) = n(n - 2) segments finis.
[0, 0], 3, 8, 15, 24, 35, 48...

Ceci délimite aussi F(n) régions finies.
La formule d'Euler donne alors le nombre de régions finies : F(n) + S(n) = A(n) + 1, soit :

F(n) = (n - 1)(n - 2)/2

0, 0, 1, 3, 6, 10, 15, 21...
Pour faciliter la comparaison des différentes configurations, nous considérons le "graphe dual". C'est à dire le graphe obtenu en plaçant un sommet dans chaque région, reliés si les deux régions ont une frontière commune. De plus, chaque sommet aura comme valeur le nombre d'arètes de la région.
Ce graphe est alors plus simple que le graphe entier, et si les graphes duals sont différents, à fortiori les graphes entiers le sont. Un recensement systématique de toutes les configurations possibles consiste alors à ajouter une 5ème droite qui coupe les 4 droites du quadrilatère complet de toutes les façons possibles. Pour faciliter le recensement et être sûr de ne pas en oublier, numérotons chaque segment du quadrilatère complet.

Il y a a priori sur chaque droite 4 façons de choisir le segment coupé par la 5ème droite, soit 4⁴ configurations au maximum à envisager. Nombre d'entre elles sont à rejeter immédiatement (car impossible d'aligner les segments).

On finit alors par trouver les seules configurations possibles :
(Les zones en bleu sont des éléments caractéristiques)

Pat1	Pat2	Pat3	Pat4	Pat5	Pat6

Pat6 est différent de Pat1 : cycle 4-3-5-3 au lieu de 3-4-4-4, pour les autres la forme du graphe dual suffit à les distinguer.

la liste complète des positions examinées :

1a 2a 3a 4a	pat5	1a2a implique uniquement 3a/3d, 4a/4d
1a 2a 3a 4d	pat1
1a 2a 3d 4d	pat5
1a 2b 3b 4b	pat5	1a2b implique uniquement 3b/3c, 4b/4c
1a 2b 3c 4c	pat6
1a 2c 3c 4d	pat5	1a2c implique uniquement 3c, 4d
1a 2d 3d 4d	pat5	1a2d implique uniquement 3d, 4d
1b 2a 3b 4b	pat6	symetrique de 1a2b
1b 2a 3c 4c	pat5
1b 2b 3a 4a	pat6	1b2b implique uniquement 3a/3d, 4a/4d
1b 2b 3a 4d	pat2
1b 2b 3d 4d	pat6
1b 2c 3a 4c	pat1	1b2c implique uniquement 3a/3d, 4c
1b 2c 3d 4c	pat5
1b 2d 3b 4b	pat3	1b2d implique uniquement 3b/3c, 4b/4c
1b 2d 3c 4c	pat5
1c 2a 3a 4b	pat5	symetrique de 1a2c
1c 2b 3b 4a	pat5	symetrique de 1b2c
1c 2b 3b 4d	pat1
1c 2c 3b 4c	pat3	1c2c implique uniquement 3b/3c, 4b/4c
1c 2c 3c 4b	pat4
1c 2d 3a 4b	pat1	1c2d implique uniquement 3a/3d, 4b
1c 2d 3d 4b	pat5
1d 2a 3a 4a	pat4	symetrique de 1a2d
1d 2b 3b 4b	pat4	symetrique de 1b2d
1d 2b 3c 4c	pat3
1d 2c 3c 4a	pat5	symetrique de 1c2d
1d 2c 3c 4d	pat1
1d 2d 3a 4a	pat3	1d2d implique uniquement 3a/3d, 4a/4d
1d 2d 3d 4a	pat6
1d 2d 3d 4d	pat3

Examinons maintenant les configurations à 6 droites et 15 points, 10 régions.
Le nombre de possiblilités explose. Pour chacune des 6 configurations de 5 droites, il faut examiner les différentes positions de la 6ème droite. Cela devient un travail de titan...
Donnons juste quelques exemples.

A partir de Pat2	A partir de Pat4	A partir de Pat6

Annexe

Sur un quadrillage... C'est à dire que les arbres sont placés sur les points d'un quadrillage Il s'agit de réaliser les 6 configurations ci-dessus de 5 alignements de 4 arbres, sur la plus petite surface possible.