4
$\begingroup$

This question is an extension of the question: how-to-determine-the-convergence-the-start-and-the-finish-points.

One can apply the next algoritm and obtaine the 1-2-3 grid pattern.

  1. On square grid paper start in the middle.

  2. Draw a line 1-unit long.

  3. Turn a right angle clockwise.

  4. Draw a line 2-unit long.
  5. Turn a right angle clockwise.
  6. Draw a line 3-unit long.
  7. Repeat steps 1-6 four times.

Аfter the step 6 you return to the start point (the red square #1). This rule is correct for any a-b-c grid pattern, where $a, b, c \in \mathbb{N}$. On the figure you can see the five crossing points (four green and one blue) for the '1-2-3' pattern. The red line marks the movement by steps 1-6 from the origin. The order of $a$, $b$, and $c$ in the triplet is irrelevant and a desired closed-path motion can be obtained by combining translation and rotation for the original closed-path motion through matrix multiplications.

enter image description here

Question. Is there a rule by which it can be determined the number of self-crossing points (nodes), k, for the a-b-c grid pattern? I am looking for a function f(a,b,c)=k.

My Attempt based on Graph Theory.

Below on figure you can see four patterns: 5-2-2, 3-2-4, 3-2-2 and 3-3-3 pattern. Start and finish points denoted by the square 1. For the 5-2-2 pattern you can see four crossing points, for the 3-2-4 pattern -- eight crossing points, for the 3-2-2 pattern -- 12 crossing points, for the 3-3-3 pattern -- self-crossing points are absent. In the last case we can say that path was repeated in four points (squares with numbers #1, #4, #7, #10).

enter image description here

When forming a triplet $(a, b, c)$ it is necessary to consider at least three cases: a) all numbers are equal to one another $a = b = c$, b) all numbers are unique $a \neq b \neq c$, and c) a triplet has the two repeating elements, for example, $a = b$. In the last case, there are three possible relations between $a$ and $b$ should be emphasized: a) $a = 2\cdot b$, b) $a> 2\cdot b$, and c) $a < 2\cdot b$.

We have found the seven different cases but can defined f() for five cases only:

$f(a,b,c)= \left\{ \begin{array}{ll} 0, & a=b=c, \\ 8, & a<b<c \quad \text{and} \quad c < a+b, \\ ?, & a<b<c \quad \text{and} \quad c=a+b, \\ ?, & a<b<c \quad \text{and} \quad a+b<c, \\ 12, & a=b<c \quad \text{and} \quad c<a+a, \\ 5, & a=b<c \quad \text{and} \quad c=a+a, \\ 4, & a=b<c \quad \text{and} \quad a+a<c. \end{array} \right.$

As one can see a resulted graph is connected, its vertices can have odd or even degrees (2, 3 and 4). On the figure the vertecies with degree equals to 2 is colored by red, the vertecies with degree equals to 3 is colored by green and the degree of blue vertecies is 4.

Based on examples above we can suggest that the number of self-crossing point k equals to the number of vertices that have degree more than 2.

My Attempt based on Complex Analisys.

Follow to the Chris Culter answer, we work in the complex plane. Let $z=e^{i\alpha}$. Then the first part of closed-path motion (red lines on the figures above) is: $$az^0+bz+cz^2 \tag{A}$$ and $\alpha=-\frac{\pi}{2}$. We return to the start point #1 after $N=4$ steps. We write equations for second, third and fourth segments by analogy:

$$az^3+bz^4+cz^5, \tag{B}$$ $$az^6+bz^7+cz^8, \tag{C}$$ $$az^{9}+bz^{10}+cz^{11}. \tag{D}$$

The full path equation is $$(az^0+bz+cz^2)+(az^3+bz^4+cz^5)+ (az^6+bz^7+cz^8)+ (az^{9}+bz^{10}+cz^{11})= 0. \tag{1}$$ Then $z=e^{i\alpha}=cos(\alpha)+i \cdot sin(\alpha)=cos(-\frac{\pi}{2})+i \cdot sin(-\frac{\pi}{2}). \tag{2}$ Substitute the expression (2) in the formula (1) and collect similar terms: $$a - i \cdot b - c + i \cdot a + b - i \cdot c - a + i \cdot b + c - i \cdot a - b + i \cdot c = 0.$$

Let us take the fist pair of relations (A) $az^0+bz+cz^2$, (B) $az^3+bz^4+cz^5$ and the 3-2-4 pattern ($a=3$, $b=2$, $c=4$).

Using the Wolfram alpha the equation $3+2 \cdot z+4\cdot z^2=3 \cdot z^3+2 \cdot z^4+4 \cdot z^5$ was solved. We found one real root $z=1$ and four complex solutions.

Refs

Marc Lackenby (2016) Elementary Knot Theory

$\endgroup$
  • 2
    $\begingroup$ Have you done any experiments? Tried any values of $a,b,c$ to see if there are patterns? $\endgroup$ – Gerry Myerson Apr 15 at 7:49
  • $\begingroup$ @GerryMyerson, I tried to analysis using the Graph Theory and Complex Analysis. $\endgroup$ – Nick May 13 at 7:18
  • $\begingroup$ I usually do some of these by Python turtle :D $\endgroup$ – anas pcpro May 17 at 13:29
  • $\begingroup$ @anaspcpro, I wrote the code on R, but I need the analytical solution. $\endgroup$ – Nick May 18 at 0:55
  • $\begingroup$ @Nick, I know it. It's easy on any programming language, that's not an answer that's a comment. $\endgroup$ – anas pcpro May 20 at 14:32
1
+50
$\begingroup$

Let $a,b,c = a_1,a_2,a_3$ and let $i,j,k\in\{1,2,3\}, i\ne j\ne k \ne i$, then:

$$ f(a_1,a_2,a_3)= \left\{ \begin{array}{ll} 0, & (a_i=a_j=a_k) \\ 4, & (a_i+a_j\lt a_k) \lor (a_i=a_j\gt a_k) \\ 5, & (a_i+a_j=a_k)\\ 8, & (a_i+a_j\gt a_k) \land (a_i\ne a_j\lt a_k)\\ 12, & (a_i+a_j\gt a_k) \land (a_i= a_j\lt a_k) \end{array} \right. $$

Works for any $a_1,a_2,a_3\in \mathbb N$.

I ran a python script to generate solutions, then conjectured these patterns based on that data, then reran the script for a lot more solutions to double check the conjecture has no counterexamples.

Finally, what is left is to expand each of the five conditions to get the locations of the intersections explicitly and prove the conjectured patterns.


Update - As requested:

If you are not satisfied with just geometrically reading out the five cases of shapes; You could exhaustively check and confirm all cases - I'm not sure if there is a nicer way?


That is,

Parametrize the line segments in the five shape classes, and compare pairs of segments to see under which conditions they contain an intersection - to get the five cases explicitly.

That is, when observing the $12$ coordinates of points visited by the walk, generally in terms of $a,b,c$:

$$(0,0)\to(0,a)\to(b,a)\to(b,a-c)\to(b-a,a-c)\to(b-a,a-c+b)\to(b-a+c,a-c+b)\to(b-a+c,-c+b)\to(-a+c,-c+b)\to(-a+c,b)\to(c,b)\to(c,0)\to(0,0)$$

You can parametrize the $12$ line segments:

$(0,0)\to(0,a) : (x=0)\land (y\in[0,a] \iff 0\lt y\lt a)$
$(0,a)\to(b,a) : (y=a)\land (x\in[0,b] \iff 0\lt x \lt b)$
$\dots$

And then compare pairs of segments to see under which conditions they can contain an intersection.


For Example, case $f(a,b,c)=12$, we have a geometrical sketch (First, consider $1)\text{ } a\le b\le c$ ):

enter image description here

Now observe under which conditions those intersections exist $(1./12.)$:

$1. : (b-a,a-c+b)$ is a distinct intersection $\iff$ $(x=0=b-a)\land(0 \lt y \lt a, y=a-c+b)$,

Which implies: $a=b$ and $(c\lt a+b \lt a+c)\iff((c\lt a+b)\land(b\lt c))$,

Which agrees with $f(a_1,a_2,a_3)$ when $(a_k=c)\land(a_i=a_j=a=b)$ gives:

$$(a_k\lt a_i+a_j)\land(a_i=a_j\lt a_k)$$

Observing under which conditions those intersections exist $(2./12.)$:

$2. : (-a+c,b)$ is a distinct intersection $\iff$ $(y=b=a)\land(0 \lt x \lt b, x=-a+c)$,

Which implies: $a=b$ and $a\lt c\lt b+a$,

Which agrees with $f(a_1,a_2,a_3)$ when $(a_k=c)\land(a_i=a_j=a=b)$ gives:

$$(a_k\lt a_i+a_j)\land(a_i=a_j\lt a_k)$$

Now, do this for all the rest $3.-12.$ intersections to confirm $f(a,b,c)=12$ for $a\le b\le c$.

$$\dots$$

Then do the same procedure for all other cases of $a_i\le a_j \le a_k$, where $a_i,a_j,a_k\in\{a,b,c\}$ for $1.-12.$, to cover all the other cases - Which I think isn't actually necessary because of symmetry.

$$\dots$$

Finally, you'd have exhaustively checked all possible cases, and arrived at:

$$f(a_1,a_2,a_3)=12 \iff (a_i+a_j\gt a_k) \land (a_i= a_j\lt a_k)$$


In the same way, you can exhaustively check other four cases.

$\endgroup$
  • $\begingroup$ Thank for the answer. How are you going to expand conditions? I have found coordinates for all cases. Is your idea will give an analytical provement? $\endgroup$ – Nick May 19 at 5:42
  • 1
    $\begingroup$ @Nick You can read out the cases geometrically. If you still aren't convinced, I guess you could write out the five shapes/cases and exhaustively verify each individual distinct intersection. I'm not sure if there's a better way. I've updated the answer with my idea and an example. $\endgroup$ – Vepir May 19 at 12:18
  • $\begingroup$ Your update is great. $\endgroup$ – Nick May 20 at 7:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.