Bravo Frenicle, moi qui pensais que tu avais trouvé la reponse sur internet sans parvenir a faire le tracé. Toutes mes félicitations !
Mais elle y etait ! Heureusement, j'avais essaye de deguiser le truc en remplacer les arbres par des choux
Bonjour,
più sacrée énigme celle-là !
Très jolie performance de frenicle et beaucoup de plantages.
Pas d'accord pour détroner le parasite (très facile quand on ne tombe pas dans les pièges ) alors que celle-ci semblait d'un très bon calibre (j'étais complètement dans les choux avec un tout petit 24!).
Pour prouver que 37 est bien le maximum, on peut considérer un graphe dont les sommets représentent les 16 choux, et tel que deux choux soient reliés entre eux par une arête si et seulement s'ils ne font pas partie d'un alignement de trois choux.
Par exemple, le graphe qui correspond à la solution que j'ai donnée est :
Le nombre d'arêtes partant de chaque chou est 15 - 2a, où a est le nombre d'alignements auquel appartient ce chou (puisqu'il y a 15 autres choux et qu'on en retire 2 par alignement) : ce nombre d'arête est donc impair, et il est donc supérieur ou égal à 1. Par exemple, dans le graphe ci dessus, il est égal à 1 ou 3.
Le nombre maximum possible d'arêtes du graphe est égal à "2 parmi 16", c'est-à-dire 16.15/2 = 120. Pour chaque alignement de 3 choux, il faut retirer 3 arêtes (puisque trois choux déterminent 3 paires de choux). Donc si T désigne le nombre total d'arêtes du graphe, et A le nombre total d'alignements de 3 choux, on a T = 120 - 3A. (Ci-dessus, A = 37 et T = 120 - 3.37 = 9.)
On a donc A = 40 - T/3. Comme il y a au moins une arête du graphe partant de chaque chou, T est supérieur ou égal à 16/2 = 8.
Donc A 40 - 8/3 = 37,333...
Comme A est entier, A 37.
Q.E.D.
Cordialement
Frenicle
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :