Shortest possible unreachable shape

Question

This is a follow up to Is every shape possible with a snake? .

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 or touch each other.

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 or touching in between. This includes during the rotations needed to bend a part at right angles.

Here are some examples thanks to Martin Büttner.

We start with the horizontal snake.

Now we rotate from position 4.

We end up after the rotation in this orientation.

Now let us consider this orientation of a different snake.

We can now see an illegal move where there would be an overlap caused during the rotation.

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 rotate at a particular point in snake up to 90 degrees clockwise of counter clockwise. For, you can never full fold the snake in two as that would have involved two rotations at the same point in the same direction.

Shapes that can't be reached

A shape that can't be reached is

(Thank you to Harald Hanche-Olsen for this example)

In this example all the adjacent horizontal lines are 1 apart as are the vertical ones. There is therefore no legal move from this position and as the problem is reversible there is therefore no way to get there from the starting position.

We say that the length of a valid shape is simply the length of a snake that could form it. For example, the example shape above which can't be reached has length $59$.

What is the shortest possible unreachable valid shape?

Current upper bound

David K gave a shape of length 31 which is unreachable. Is this the shortest possible?

Answer 1

Taking into account that the snake can fold or unfold itself at any one of its integer-coordinate points at any time (provided that it does not touch itself during or after this operation), the snake of length $31$ shown below (based on Harald Hanche-Olsen's example) is unreachable:

If we take a point $P$ at any integer point along the snake from $D$ to $E$ inclusive, $P$ is closer to $B$ than to $F$, that is, $PB < PF$, so either of the moves at $P$ would cause one of the segments above or below $F$ to intersect the segment that ends at $F$. (In particular, $DB = 2 < \sqrt5 = DF$, and all other such points are even farther from the perpendicular bisector of $\overline {BF}$.) If we take a point $Q$ at any integer point along the snake from $C$ to $B$ inclusive, then $QA \geq QE$, with equality only at $CA = \sqrt{13} = CE$; hence a move at any of those points would cause $A$ to pass either through $E$, through some segment ending at $E$, or through some part of the snake between $E$ and $F$.

It is clearly impossible for the snake to fold or unfold at any other point.

Since the same transformation rules that allow the snake's initial shape to be transformed into a reachable shape would also allow the reachable shape to be transformed back to the snake's initial shape, this shape cannot be reachable.

Previous answer

When I first answered this I considered only "straightening" moves when thinking about transforming the snake back to its initial shape. This led me to propose the following shape for a snake of length $24$:

As observed in the comments, there is a legal move at one of the points along the top edge of this shape (in fact there are three such points at which there is a legal move), after which the snake can obviously be unfolded to its initial shape. Hence this shorter snake's shape would be unreachable only under a much more restricted set of rules in which a right angle bend in the snake, once made, could not be unmade. As that restriction was not intended in the original problem statement, this shape is not a solution to the problem.

Answer 2

22 Units - (Flawed)

If entire subcomponents can be moved, there needs to be a hooking structure that prevents rotation on either end in either direction. I believe this is the shortest possible way to create a hook.

Edit:

It seems that my answer fails here:

I'm leaving this answer here for posterity, but it is indeed incorrect.

Analysis of The Problem

Assuming we start with a line of length $L$ and then perform a sequence of bends $b_i$ of $\pm 90$ degrees on any integer point along the line $\in [1, L]$. We call that sequence a pattern $P$. We can extend the set of possible bends to $[-90, 90]$ to give us a sense of continuity. Bends of exactly $90$ degrees will be "whole bends" and other bends will be "partial bends". Patterns consisting of only whole bends will be called "whole patterns".

Definition A pattern is also unreachable if it's invalid. This is only slightly different from the question's definition of unreachable as it also applies to patterns without considering which bend is being made prior.

Definition
$P_1 = P_2$ if they make the same snake shape.

Lemma
Given two whole patterns $P_i$ and $P_f$ such that $P_f$ differs from $P_i$ by a whole bend, there are partial patterns that differ from $P_i$ by a single partial bend and differ from $P_f$ by another single partial bend. $P_f$ is unreachable from $P_i$ if and only if there exists at least one such partial pattern that is unreachable or $P_f$ is unreachable.

Theorem
Given two whole patterns $P_i$ and $P_f$. $P_f$ is reachable from $P_i$ if and only if there exists a sequence of whole patterns $\{P_i = p_1, p_2, ..., p_{n-1}, p_n = P_f\}$ such that for all adjacent pairs $(p_{i+1}, p_i)$, $p_{i+1}$ is reachable from $p_i$.

Corollary
Let $P^L_o$ by the pattern of the straight line of length $L$ without any bends. A pattern $P$ is unreachable if it is unreachable from $P^L_o$.

Theorem
Being "unreachable from" is a reflexive relation on whole patterns. Being "reachable from" is a reflexive relation on whole patterns.

Now, we have some tools to work with.

There are actually two classes of unreachable patterns upon closer inspection.

$$ \mathcal{P}_1 = \{P\ |\ P\text{ is unreachable from }P_o^L\} \\ \mathcal{P}_2 = \{P\ |\ \forall P_ k\not = P, P\text{ is unreachable from }P_k\} \\ \mathcal{P}_2 \subseteq \mathcal{P}_1 $$

For example, two elements of $\mathcal{P}_1$ that are not in $\mathcal{P}_2$

As you can see, these two patterns (length $39$ each) are reachable from each other, but not from a flat snake. Simply checking if a pattern can be bent will not disqualify it from being an unreachable pattern. It could be that the shortest unreachable pattern is a member of $\mathcal{P}_1$ and not $\mathcal{P}_2$.