Is every shape possible with a snake?

516 Views Asked by At

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.

2

There are 2 best solutions below

15
On BEST ANSWER

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.

1
On

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?