5
$\begingroup$

Introduction

With a friend of mine we were studying the following problem: given a $m\times n$ grid draw this pattern (I don't know how to describe it in words)

enter image description here enter image description here

The first image has $3$ loops and the second image has only $1$ loop.

The question is: is it possible to know the number of loops ($=l$) in advance by knowing the size of the grid?
The answer is yes and simply the answer is:

$$l=\gcd(m,n)$$

Question

After finding this result we complicated the problem:
Is it possible to know the number of loops if there are holes in the grid?

We noticed that if you have an $n\times n$ grid and you remove the corner the number of loops is $n-1$, but in general we did not notice a pattern for a generic situation.

But we have made these observations:

  1. The location of the holes affects the result
  2. The number of loops is invariant for rotations and symmetries
  3. The presence of a hole can increase or decrease the number of loops.

Here is an example of why rule $1$ applies:
enter image description here
Here the first graph has $2$ loops and the second graph has $1$ loop (in both cases you have a $3\times 3$ grid with only $1$ hole)

Here is an example of why rule $3$ applies:
enter image description here enter image description here
In the first case there is one less loop compared to the $3\times3$ scheme (the image is above), in the second image instead there is one more loop

In general however we wanted to consider any grid with any number of holes in any position

My idea

My idea was to consider a binary matrix in which $$(a)_{ij}=\begin{cases}1&\text{There is }\textbf{not}\text{ an hole}\\0&\text{There is an hole}\end{cases}$$ This consideration is useful because hypothetically I could consider any grid as a larger grid where the rest it's empty

Obviously this problem can also be seen as:

  1. A bouncing ball in a room with obastacles.
  2. A laser reflected in a room of mirrors

The purpose of the problem however is to know how many loops there are given a given grid.

Update

I don't know if it can be useful, but in knot theory there are these two formulas:

Given an adjacency matrix $\mathbf{A}$, let $E$ the set of the edges in the graph and $T$ the set of the triangles in the graph.

$$\text{trace}(\mathbf{A}^2)=2\cdot|E|$$ $$\text{trace}(\mathbf{A}^3)=6\cdot|T|$$

Maybe there is a similar relationship for this case.

$\endgroup$
2
  • 1
    $\begingroup$ Obviously the braiding is not terribly relevant. The only thing is that each path reflects off edges at the midpoint... Oh I like this. Okay one thing I thought of: an ear doesn't count, the P pentomino is exactly like the 2x2 square with slightly less bounce in that one direction. If a single length 1 edge cuts the object into two pieces then the shape can be simplified. $\endgroup$
    – Dan Uznanski
    Commented Oct 23, 2023 at 10:48
  • 1
    $\begingroup$ @DanUznanski Yup, the problem can be seen from multiple points of view, this was the most fascinating one from a graphic point of view ahaha $\endgroup$
    – Math Attack
    Commented Oct 23, 2023 at 10:52

0

Reset to default

You must log in to answer this question.