# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
DrJones
Daedalian Member

 Posted: Sun Nov 20, 2005 4:50 pm    Post subject: 1 Many days ago, I had a dream in which I had to pass a chain through a certain number of rings, placed in different places of a room. The chain's lenght was limited, so there was only one way to reach all rings, starting and ending on the same spot. I had to perform this same task on many other rooms. When I awoke, I found that I dreamed with the 'traveling salesman problem'. In my dream, I realized two things about the problem, which since then I have been trying to prove/disprove, without success. 1. Let's say that there are 8 points located in different coordinates of a 10 x 10 grid. I want to join all the dots with straight lines, starting and ending on the same point, and without visiting the same spot twice. Let's call H the group of resultant polygons which comply with that. Then I think that the polygon on H with the minimum perimeter length doesn't have any crossed line. 2. Let's say that a polygon has a "sharp end" when there are three consecutive points in it (let's call them A, B, C, where A is connected to B, and B is connected to C) that comply that if we trace a straight line from A to C, that line would "cut" (pass through) the inner side of the polygon (tangencies don't count). Then I think that, being P the polygon on H with the minimum perimeter length, and being N the number of "sharp ends" on it, there is no other polygon on H with M "sharp ends", where M
DrJones
Daedalian Member

 Posted: Sun Nov 20, 2005 5:53 pm    Post subject: 2 Well, just want to inform that I have discovered that the first part is true. Good to know.
Bicho the Inhaler
Daedalian Member

 Posted: Thu Nov 24, 2005 12:12 am    Post subject: 3 If I've understood correctly, I don't think (2) is correct. Let the points be A = (0,1), B = (1,1), C = (1,0), D = (0,0), E = (0,4), F = (4,1), G = (1,-3), H = (-3,0). Then the cycle AEBFCGDH has 4 "sharp ends" and length 12 + 4sqrt(10) > 24 (since sqrt(10) > 3). I *think* the shortest cycle, though, has length 24 (AEFGHDCB), which has 5 sharp ends, and I can't see anything as good with 4 or fewer sharp ends (currently without proof). Edit: Oops, never mind. there are paths of length 24 with only 4 sharp ends, like ABFGCDHE. Edit 2: I labeled the vertices wrong! I agree about the first part, though.
Bicho the Inhaler
Daedalian Member

 Posted: Thu Nov 24, 2005 2:13 am    Post subject: 4 Aha. So that didn't work, but I think it can be fixed. Let c be some positive number. Let's revise the set: A = (0,1), B = (1,1), C = (1,0), D = (0,0), E = (0,c+1), F = (c+1,1), G = (1,-c), H = (-c,0). (My previous attempt was the case c = 3.) I claim that for large enough c, all shortest circuits have 5 sharp ends, while there are paths with 4 sharp ends. Some 4 sharp end paths are AEBFCGDH and ABFGCDHE, as before. The path AEFGHDCB has 5 sharp ends, and I claim that's the best path, and the only one up to rotational symmetry. This is because if c is very large, the shortest path always visits the vertices A,B,C,D consecutively in some order, since the distance between any pair of those vertices is negligible (of order 1) compared to the distance between any other pair of vertices (of order c), so it is never to the path's advantage to visit {A,B,C,D} twice. Indeed, unnecessary visits can be eliminated: if it goes from X to {A,B,C,D} to Y (X, Y not in {A,B,C,D}), then just going from X to Y is faster by the triangle inequality (in the limit as c -> infinity), and whichever of {A,B,C,D} we skip we just absorb into another visit to {A,B,C,D} (there must be one, by assumption) at negligible cost. So it suffices to consider {A,B,C,D} as a single vertex (say, "V"), and find the shortest tour of {E,F,G,H,V}. It's not hard to see that this must be VEFGH (or a rotation by 90 or 180 degrees). Going back to the original set, it's not hard to see that the actual edges traversed must be DCBAEFGH, which is what we claimed. I think it actually suffices to take c = 4 (or any c > 3?); 3 was just a bad choice.
DrJones
Daedalian Member

 Posted: Thu Nov 24, 2005 10:28 pm    Post subject: 5 Thank you. I had so far discovered that some polygons with more "sharp ends" had less length than others with fewer, but couldn't find any example with fewer than the best path.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersBicho the InhalerDrJones Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum