17

I was playing around with this demo of Project Euler Problem 208 which allows you to take steps which are "left" or "right" arcs of $1/5$ of a unit circle.

Here's an example walk, which starts at the blue dot pointing vertically up, and which consists of steps

RLLLRLLLRRLLLRLLLRRLRLLLR

example walk

Question

Which points in $\mathbb R^2$ can be reached in a finite number of steps, starting at the origin and pointing in the positive $y$-direction. Is this set of points dense in $\mathbb R^2$? If not, what's the greatest number of points that can land in $[0,1] \times [0,1] \subset \mathbb R^2$?

Peter Kagey
  • 5,052
  • 2
    I would expect the points to be dense but it be a bit of work to prove. One way is to find sequences of moves that end with you facing the same direction but move the point in several directions. If the distances moved are not rational multiples of each other you can combine those movements to get as close as wanted to any point. RL and LR leave you heading in the same direction as at the start. You can compute the displacement they create, but they will be the same vertically and negatives horizontally. Now add RRLL and LLRR to the mix. You need – Ross Millikan Aug 22 '19 at 23:02
  • a combination that moves you downward, but that shouldn't be hard to find. I would think something like RRRLRLRLRLRLLL would work, the first three to make (about a) U turn, the middle RLs to move in that direction, and the last three to reorient upward. – Ross Millikan Aug 22 '19 at 23:05
  • This is a really interesting question. I might end up offering a bounty here – clathratus Aug 23 '19 at 00:37
  • @Peter Kagery I am editing the picture with labels linking turn plan and position reached. Please feel free to undo if required. – Narasimham Aug 23 '19 at 06:42
  • Of course it's dense. That's basically why you can't have a 5-fold axis in classical crystallography. – Ivan Neretin Aug 23 '19 at 07:47
  • @IvanNeretin, can you answer with a quick proof explaining why it must be dense? – Peter Kagey Aug 23 '19 at 21:13
  • I have to think of it for a while. My understanding is based on the concepts which might be well known within crystallography but not elsewhere. – Ivan Neretin Aug 23 '19 at 22:03
  • 1
    I think one could reformulate this question so it is closely linked with the projective definition of the Penrose pattern: Take the standard Z^5 grid in the 5-dimensional vector space. One can put a 2-dimensional subspace E in such a way, that the 5 base vectors project to it pointing to the corners of a regular pentagon. Then your question should be equivalent to the question, If the projection of Z^5 to E is dense, right? I think this has been proven due to E having an irrational angle to the base vectors. – Non Euclidean Dreamer Aug 24 '19 at 15:02
  • 1
    Related:Rolling a random walk on a sphere: "The surface will be filled for every $\delta$ except $\pi/2$ and $\pi$." – Joseph O'Rourke Aug 25 '19 at 01:48

3 Answers3

12

Yes, the set of points attainable by these paths is dense in $\mathbb{R}^2$. Pardon the lack of polish in this answer; I don't have a 'real' math background, so I'm expressing my ideas here using the language most intuitive to me.

We can think of any path as a linear combination of five 'moves,' which w.l.o.g. are given by the vectors $v_n = (\cos\frac{2\pi n}{5}, \sin \frac{2\pi n}{5})$. Paths cannot be arbitrary integer combinations of these vectors, since there are only two moves available after each step. We can, however, devise the following scheme to obtain arbitrary integer combinations of the vectors $2v_n$. Consider the following paths (I've written out the linear combination long form to show the order that the steps must be taken in each path):

\begin{align*} p_1^a &= 2av_1\\ p_2^b &= v_1 + 2bv_2 + v_1\\ p_3^c &= v_1 + v_2 + 2cv_3 + v_2 + v_1\\ p_4^d &= v_1 + v_2 + v_3 + 2dv_4 + v_3 + v_2 + v_1\\ p_5^e &= 2ev_5 \end{align*}

Graphically, these look something like this: $p_1^2$, $p_2^2$, $p_3^2$, $p_4^2$, $p_5^2$.

These paths are composable with each other, so we can take them in arbitrary (positive) integer combinations. Consider a point of the form $x = \sum_{i = 1}^5 p_i^{a_i}$. Writing this out in terms of our original moves $v_i$, we obtain \begin{align*} x &= p_1^a + p_2^b + p_3^c + p_4^d + p_5^e\\ &= (6 + 2a)v_1 + (4 + 2b)v_2 + (2 + 2c)v_3 + 2dv_4 + 2ev_5 \end{align*} We will ignore the constant offset $6v_1 + 4v_2 + 2v_3$. Using the paths $p_i^a$ alone, we can thus reach an arbitrary (nonnegative) integer combination of the vectors $\{2v_i\}$.

Now note that $\sum_{i = 1}^5 2v_i = 0$, so it follows that the vectors $2v_i$ and $\sum_{j \neq i} 2v_j$ are additive inverses. Thus the set of nonnegative integer combinations of the vectors $2v_i$ is actually equal to the set of arbitrary integer combinations of the vectors $2v_i$.

Digging around MathSE, I found this answer that asserts, based on Kronecker's theorem, that if three vectors have components that are all linearly independent over the rationals, then the set of their integer combinations is dense in the unit square (and by extension the plane). $2v_1$, $2v_2$ and $2v_3$ satisfy this hypothesis, so the claim should follow.

Panopticon
  • 298
9

Not an answer, but just an opportunity to mention that the behavior of the "Tangle Toy," which comes in quarter-circles,

         
          Image from FatBrainToys.
has been studied (but not addressing your question):

Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Quanquan Liu, Ron Taylor, and Ryuhei Uehara, “Tangled Tangles”, in The Mathematics of Various Entertaining Subjects (MOVES 2015), volume 2, 2017, pages 141–152, Princeton University Press. Authors' link.

         
          Fig.7: Tangle toy configurations.

To address @Narasimham's question, this paper

Tatu, Aditya. "Tangled Splines." arXiv:1610.03129. 2016-18.

says that the curvature $\kappa(t) =\pm 1$ outside of the knot points, and that torsion $\tau(t)$ is zero, again excluding knot points.

Joseph O'Rourke
  • 30,327
3

Here's a formulation that may help with calculation a bit: define a 'position' as $\langle x, y, \theta\rangle$, where $\theta$ is the angle being made with the $y$ axis; in other words, the starting position is $\langle0, 0, 0\rangle$. Then if you draw the geometry out (which I will try and do once I get onto a machine with better drawing tools) from $\langle x, y, 0\rangle$ the available moves are to $\langle x+(1-\cos(2\pi/5)), y+\sin(2\pi/5), \pi/10\rangle$ and $\langle x-(1-\cos(2\pi/5)), y+\sin(2\pi/5), -\pi/10\rangle$. Since the local frame at angle $\theta$ has its $x$ axis in the direction $\langle \cos\theta, \sin\theta\rangle$ and its $y$ axis in the direction $\langle -\sin\theta, \cos\theta\rangle$ (modulo possible sign errors) then this means that from $\langle x, y, \theta\rangle$ the available moves are to $\langle x+\cos\theta(1-\cos(2\pi/5))-\sin\theta\sin(2\pi/5), y+\cos\theta\sin(2\pi/5)+\sin\theta(1-\cos(2\pi/5)), \theta+\pi/10\rangle$ and to $\langle x-\cos\theta(1-\cos(2\pi/5))-\sin\theta\sin(2\pi/5), y+\cos\theta\sin(2\pi/5)-\sin\theta(1-\cos(2\pi/5)), \theta-\pi/10\rangle$. Since the cosine and sine of $2\pi/5$ and $\pi/10$ have nice clean expressions in terms of $\sqrt{5}$, you should be able to get explicit expressions in terms of $\sqrt{5}$ for the coordinates after making multiple moves as in Ross Millikan's comment, and then use some usual irrationality-of-square-roots arguments to show density. (But of course, note that there's a little subtlety to these arguments, because the same statement with sixth-turns around the circle are false!)

Steven Stadnicki
  • 51,746