DEFI 158 : Savez-vous planter les choux ?

Posté par minkus minkus

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

Posté par borneo borneo

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

Posté par minkus minkus

Mais elle y etait ! Heureusement, j'avais essaye de deguiser le truc en remplacer les arbres par des choux

Posté par manpower manpower

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

Posté par jamo jamo

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

Posté par frenicle frenicle

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

Posté par minkus minkus

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

Posté par tshit (invité)

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