I127. Un joli zig-zag |
I. Trajets optimaux |
Dans un quadrillage de dimensions 5x5, trouver le plus long chemin constitué d'une séquence de segments de droite reliant des points de coordonnées entières de telle sorte que:
SolutionJean Moreau de Saint Martin,Michel Lafond,Jean Nicot et Matthieu Scetbun ont résolu le problème tel que posé. Par ailleurs Jean Nicot a tracé le zig-zag en maximisant non pas la longueur du chemin mais le nombre de segments reliés entre eux. Cette formulation était celle du problème ci-après posé à l'été 2015 par Stan Wagon sur le site de Macalester College Problem 1215 Connect the Dots Consider a 5x5 square lattice of 25 points. Find the longest path (in terms of number of segments) that: * connects lattice points in sequence with straight segments and never intersects itself (even a tangency is not allowed), and * has each segment of strictly greater length than the segment that precedes it. For example, on a 3 x 3 lattice the longest such path has length 4: it is (0,0) -> (0,1) -> (1,2) -> (1,0) -> (2,2). |