3
$\begingroup$

There is a line of infinite length (about zero thickness) in a 3D space. It can rotate or move across any plane at any speed. Every point (flagged or not) that has already been visited by the line cannot be touched again.

Your mission is to set flags on specific points in space. As you set each flag, it will move until it touches the flag. Then you set another flag, and so on. You cannot set a flag on a point it has already visited.

Is it possible to make it impossible for the 'line' to reach a flag, after a finite number of flags?

Also,

Answer the same Q for a line of finite length.

Improve this question
$\endgroup$
11
  • $\begingroup$ Does the line necessarily move straight, ie. to reach a flag must it follow a single plane? $\endgroup$
    – Rohcana
    Sep 8, 2015 at 9:52
  • $\begingroup$ Does the line move in a plane or can it move randomly ? $\endgroup$
    – ABcDexter
    Sep 8, 2015 at 9:59
  • $\begingroup$ 'As you set each flag, it will move until it touches the flag.' "It" refer to the line I suppose? "move" can also mean "rotates" until it hits the flag? $\endgroup$
    – BmyGuest
    Sep 8, 2015 at 10:23
  • $\begingroup$ If the line is not allowed to occupy the same point twice, this effectively eliminates rotation, or am I missing something? $\endgroup$
    – Sleafar
    Sep 8, 2015 at 10:25
  • 1
    $\begingroup$ @Sleafar I think he means Once the line is displaced from a point, it cannot return to that point again $\endgroup$
    – Rohcana
    Sep 8, 2015 at 11:45

3 Answers 3

Reset to default
2
$\begingroup$

No, it is impossible to block off the line from any point, whether the line is finite or infinite.

Say you have some maze path M already dragged out by the line. Because no two "walls" may be adjacent (there is always a gap between them), it is always possible to go back arbitrarily close to any point on M by backtracking.

Now, pick any point P in the space not intersecting with M. There must be another point S on the path M that is the shortest distance to P. Since we can always backtrack, we trace M back to any point between P and S, and then we have a straight shot to P.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have much to learn about elegance and simplicity from this proof. $\endgroup$
    – MathET
    Sep 23, 2015 at 5:24
4
$\begingroup$

No.

I don't have a mathematical proof, but merely an explanation:

Assume the line never rotates (it doesn't need to, since you only set new flags after it reaches one). This reduces the problem to a point in 2D space. However, since you can't place a flag on a visited point, you can never "cut off" the point and stop it sneaking between the gaps in the "walls" it's left behind.

A couple of changes would drastically alter the problem:

However, if you could set more than one flag at once and it couldn't, or had to touch them simultaneously, you could force the line to rotate.

Improve this answer
$\endgroup$
6
  • $\begingroup$ You're right. Try answering the 2nd Q also (finite line) $\endgroup$
    – ghosts_in_the_code
    Sep 8, 2015 at 14:29
  • $\begingroup$ @ghosts_in_the_code Doesn't a "No" for the 2nd questions directly follow from the first "No" ? In the explanation above the "dot" would just become a "half-transparent" dot :c) $\endgroup$
    – BmyGuest
    Sep 8, 2015 at 14:32
  • $\begingroup$ The second part is more complicated and I have't figured it out yet. If the line isn't infinite, you can place flags along its "infinite" length and force it to rotate. Thus you have to not only consider possible flag moves but also possible line moves to avoid cutting itself off. You have to create a "cage" of positions and movement that it can't fit into. $\endgroup$
    – Samthere
    Sep 8, 2015 at 14:43
  • $\begingroup$ You can also make the same argument in terms of the line only rotating, anchored to a fixed point. In that case, every point maps to a point in the unit sphere around the origin. $\endgroup$
    – user88
    Sep 8, 2015 at 19:55
  • $\begingroup$ @JoeZ. this does not really work since technically you pass infinitely many times through the anchoring point. $\endgroup$
    – Puzzle Prime
    Sep 8, 2015 at 21:42
1
$\begingroup$

I sketched a playing stategy for the line. It's pretty complicated, but if I didn't miss any point, the line should be able to reach the flags, no matter where they're placed.

In order to evade getting in a locked position, the line needs to restrict its movements in a way such that the projection of the set of all visited points into the horizontal plane has a total area of zero (i.e. It's a curve). This way, it will always be able to escape by going up or down from the neighborhood of any point in the plane.

To show that any flag is reachable in this way, first notice that the ones in unvisited areas are trivially reachable within these constraints: As long as the line is kept vertical, its shadow will not sweep any area on the xy-plane. For areas which have already been passed by, the mechanism is slightly more complex.

During vertical motion, small horizontal displacements would be necessary to avoid self collision. However, it would not be a problem, since for any obstacle at some nonzero horizontal distance, an even smaller horizontal displacement would be possible.

Suppose, now, the flag lies on the curve. It can be shown, upon suitable tameness conditions (piecewise differentiability), that there can be found in its neighborhoood infinitely many line segments of unvisited points. These correspond to vertically unbounded areas which are completely free for maneuver. They can be reached from above or below by using the escape method explained at the start.

Consider one of those areas. In the worst case, every point directly above and below the flag is already visited. But by simultaneously moving forward, up/down, and tilting the top it is possible to make it reach the goal. After that, the vertical orientation can be restablished without self-intersections, by going backwards, tilting back up and moving downwards fast enough to compensate.

This entire process can be done in arbitrarily tight horizontal spaces, by shrinking the tilting angle (tilting less). Since the only rotation involves the plane of movement, it preserves the property that the projection of visited points forms a meagre set.

Here is an illustration of this mechanism: Line

Please, don't comment. I used all my drawing skill to make this one

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ If anyone makes fun of your Rainbow Road drawing, they're going to have to answer to me! $\endgroup$
    – user1717828
    Sep 23, 2015 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.