Forum des énigmes mathématiques :
DEFI 158 : Savez-vous planter les choux ?

Bravo Frenicle, moi qui pensais que tu avais trouvé la reponse sur internet sans parvenir a faire le tracé. Toutes mes félicitations !

Minkus : quand la réponse est sur le net, il y a moins de poissons  

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!).

Il est vrai que celle du parasite était toute simple à comprendre ...

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

Joli frenicle. Il restait cependant a voir que ce maximum theorique pouvait etre atteint

  bonjour Minkus,il y a 16 choix maximum pour allignés en 3.on compte en diagonale.
  
                                     10        11
                
                                 1        2        3


                                 4        5        6


                                 7        8        9


                                     13        14


                                    16         17            Merci.Il est quand même dure le DEFI...