11
$\begingroup$

Imagine a 2d snake formed by drawing a horizontal line of length $n$. At integer points along its body, this snake can rotate its body by $90$ degrees either clockwise or counter clockwise. If we define the front of the snake to be on the far left to start with, the rotation will move the back part of the snake and the front part will stay put. By doing repeated rotations it can make a lot of different snake body shapes.

Now let us define a valid shape. A shape is valid if it can be formed from a straight line snake by applying at most one $90$ degree bend at each one of the integer points along its body and no two parts of the resulting shape intersect. The shape T for example is not valid as there is no way to make it from a single snake nor would any shape be with two parts intersecting.

We now apply some further rules to say a shape is reachable. A shape is reachable if it is valid and it is possible to reach the orientation without any parts of the snake's body intersecting in between. This includes during the rotations needed to bend a part at right angles.

Is every valid shape reachable?

Example of a rotation of part of the snake's body. Imagine $n=10$ and the snake is in its start orientation of a straight line. Now rotate at point $4$ counter-clockwise $90$ degrees. We get the snake from $4$ to $10$ (the tail of the snake) lying vertically and the snake from $0$ to $4$ lying horizontally. The snake now has one right angle in its body.

When a rotation happens it will move one half of the snake with it. We do have to worry about whether any of this part which is rotated might overlap a part of the snake during the rotation. For simplicity we can assume the snake has width zero. You can only ever rotate at a particular point in the snake up to $90$ degrees clockwise of counter clockwise. For example, you can never fully fold the snake in two onto itself as that would have involved two rotations at the same point in the same direction.

$\endgroup$
  • $\begingroup$ I don' t think so, you obviously can't make a curve even if you can rotate any part of its body. It would have been possible to make straight lines inclined at $45^{\circ}$ if you would have been able to rotate any part. But with only integer rotatable parts, probably not. $\endgroup$ – AvZ Jan 27 '15 at 13:36
  • $\begingroup$ @AvZ A curve isn't a valid shape. ". A shape is valid if it can be formed from a snake with an arbitrary number of right angle bends in its body without any of its parts intersecting." Or did I misunderstand you? $\endgroup$ – user66307 Jan 27 '15 at 13:37
  • $\begingroup$ Your question was that if every valid shape is reachable. But you defined valid shape as a shape which can be formed by the snake. Your question gets somewhat circular. You can form rectangles in some cases for a closed polygons. But you have to clarify valid shapes $\endgroup$ – AvZ Jan 27 '15 at 13:40
  • $\begingroup$ @AvZ Ah. Is it clearer now? $\endgroup$ – user66307 Jan 27 '15 at 13:41
  • $\begingroup$ Yes, much clearer now. $\endgroup$ – AvZ Jan 27 '15 at 13:45
9
$\begingroup$

If you will forgive a bit of Unicode box art, I think this is a counterexample:

┌──────────────────┐
│ ┌─────────────── │
│ │ ───────────────┘
│ └────────────────┐
└──────────────────┘

The horizontal lines are supposed to be 1 apart. It has to be sufficiently wide for the example to work.

Edit: A bit of explanation may be in order. The recipe for snake folding is reversible, so if this snake is reachable, it can be unfolded into a straight line. But there is no legal move from this configuration.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ there are some small legal moves by folding just a tiny part at the tail/head of the snake. Though there shouldn't be enough room to squeeze everything away. (and just now i understand the "horizontall ines are 1 unit apart line) $\endgroup$ – mercio Jan 27 '15 at 14:17
  • $\begingroup$ Within the limits of ASCII art, I think Harald has packed the horizontal lines as close together as possible (vertical resolution is coarser than horizontal resolution). So here if the snake were to turn its "head" right or left, a self-intersection would occur. $\endgroup$ – hardmath Jan 27 '15 at 14:21
  • $\begingroup$ @hardmath Indeed. If I had deleted the four seemingly redundant text lines, I would end up with an ambiguous looking stack of three pluses on the right margin. I could probably have done better if I looked up the line art characters that exist somewhere in unicode land, though. $\endgroup$ – Harald Hanche-Olsen Jan 27 '15 at 14:25
  • $\begingroup$ Hah, now I see why Unicode is superior to ASCII! $\endgroup$ – hardmath Jan 27 '15 at 14:33
  • $\begingroup$ @hardmath Ah well, I fixed it with some unicode box art. Unfortunately, there is a small gap between the text lines which makes breaks in the vertical lines, but it can't be helped. $\endgroup$ – Harald Hanche-Olsen Jan 27 '15 at 14:33
0
$\begingroup$

This should be a comment to the answer by @HaraldHanche-Olsen (https://math.stackexchange.com/a/1121816/152299) but I don't know how to put a pre-formatted ASCII-art in a comment. :(

How about this snake?

┌──────────────────┐
│                  │
│   ───────────────┘
│
*
│ ┌────┐
│ │    │
│ │    │
│ │    │
│ │    │
│ │
└─┘

When bent at the asterisk, wouldn't it become what you show?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The problem is the intersections you get during the course of the rotation. $\endgroup$ – user66307 Feb 7 '15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy