21
$\begingroup$

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.

enter image description here

Now we rotate from position 4.

enter image description here

We end up after the rotation in this orientation.

enter image description here

Now let us consider this orientation of a different snake.

enter image description here

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

example of collision

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

enter image description here

(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?

$\endgroup$
2
  • 1
    $\begingroup$ I don't see any mathematical method to this. Probably, the only practical way is to write a computer program $\endgroup$ – AvZ Feb 7 '15 at 18:06
  • $\begingroup$ One class of examples is to double over the snake, and then spiral it around until the ends can't be unbent. i.imgur.com/5vYPn7p.jpg I think you can at least beat Harald Hanche-Olsen's example with this approach, you might even be able to get down to 29 but I have to check more carefully. $\endgroup$ – Marcel Besixdouze Feb 7 '15 at 22:11
7
+50
$\begingroup$

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:

enter image description here

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$:

enter image description here

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.

$\endgroup$
8
  • 2
    $\begingroup$ I think yours fails here: i.imgur.com/nJVV2dP.png $\endgroup$ – Axoren Feb 7 '15 at 21:13
  • $\begingroup$ I think @Axoren must be correct; all that this answer changed was an irrelevant measurement, since if we rotate as Axoren's image suggests, all the bits that are important are moving exactly the same as in Axoren's answer. $\endgroup$ – Milo Brandt Feb 7 '15 at 22:17
  • $\begingroup$ Whether this shape is reachable depends on what you consider to be valid moves. Without realizing it, I considered only moves that bend the snake (creating right angles), not moves that straighten the snake (removing right angles). I think this shape is still unreachable if only bending is allowed, whereas the shorter shape initially proposed by @Axoren can be reached by bending alone. $\endgroup$ – David K Feb 7 '15 at 22:25
  • $\begingroup$ @DavidK Bending at any internal point has been confirmed by Lembik here: math.stackexchange.com/questions/1134808/… $\endgroup$ – Axoren Feb 8 '15 at 2:40
  • 1
    $\begingroup$ You can bend as many times as you like at each integer location. For example you can bend and later unbend and then bend the other way. You just can't ever bend more than 90 degrees from straight. $\endgroup$ – user66307 Feb 8 '15 at 6:57
2
$\begingroup$

22 Units - (Flawed)

enter image description here

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:

enter image description 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$

enter image description here

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$.

$\endgroup$
9
  • $\begingroup$ I think that is reachable. The last move is to rotate by the top right junction in your picture. $\endgroup$ – user66307 Feb 7 '15 at 11:22
  • $\begingroup$ From your examples it seemed like we could only move the last straight segment. If we can move entire subcomponents, that's different. $\endgroup$ – Axoren Feb 7 '15 at 11:27
  • $\begingroup$ You can indeed rotate at any integer point and this will move everything after that point with it. $\endgroup$ – user66307 Feb 7 '15 at 11:28
  • $\begingroup$ @Lembik My answer is corrected. $\endgroup$ – Axoren Feb 7 '15 at 11:36
  • 2
    $\begingroup$ The distance from the top right junction to the snake end is only $\sqrt{2^2+2^2}=2.82,$ and the distance from the top right junction to the top right of the lower part (where it might look like an intersection could occur) is $\sqrt{1^2+3^2}=3.16,$ so it looks now like the last two links could be rotated around the top right junction without giving a crossing. $\endgroup$ – coffeemath Feb 7 '15 at 12:43

Your Answer

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