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) = Cn2 = 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 44 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.

 

Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Précédent Suivant Parent