Category Archives: Cross Diagonal Cover Problem

Cross Diagonal Cover – VI

Standard

The problem has finally been solved by Matthew Scroggs.

{\text{\# filled squares} = (\mathrm{lcm}(m-1,n-1)+1 )- \frac12\left(\frac{\mathrm{lcm}(m-1,n-1)}{m-1}-1\right)\left(\frac{\mathrm{lcm}(m-1,n-1)}{n-1}-1\right)}

He and I, independently,  found a counterexample  for the conjecture by replacing lowest common multiple by greatest common factor using the relation: ab=\mathrm{lcm}(a,b)\gcd(a,b).

In 15×5, there are 26 filled squares and gcd(15,5)=5, so 15×5 is a counterexample to the conjecture!

As it turns out, SAGE is giving float(26/5) = 5.0 when I run it inside the program, but return 5.2 when I run it independently. Leading to wrong conjecture.

The solution is pretty beautiful and  this is the outline:

There are 3 levels of simplifications of the problem:

Original Grid –> Dual Grid –> Mirror Grid –> Inner-point Grid

Counting the “Corners visited twice” (the subtracted term) was something I wasn’t able to do. Corners visited was essentially what I called “number of steps needed for algorithm to stop“. So, his mirror argument provides a proof without words of that result.

Advertisements

Cross Diagonal Cover – V

Standard

This has been an exciting week! Prof. Sukanta Pati proved an interesting theorem that enables us to get decomposition of 2m-1\times n grids into simpler grids, hence simplifying counting to large extent (note that m=n is also allowed). It enables us to surpass the difficulty posed by “more than two crosses in one square”, thus supporting the idea of colouring (i.e. not giving importance to two crosses in a square).

Given m\times n grid which has consisting of m rows and n columns such that the terminating corner square lie in m^{th} row. Let the number of covered squares in m\times n grid be C(m,n) . Then for  2m-1\times n grid we have C(2m-1, n)= 2C(m,n)-\beta(m,n)  where \beta(m,n) is the number of covered squares in m^{th} row of m\times n grid.

Instead of giving its proof, I will give an  example when m=5, n=10.

New Doc 26_1

I omitted the repetitions of crosses (x) since the number of x in each square doesn’t matter. Note that if we reflect 5×10 about the middle of 5th row we will get 9×10.

Here, C(5,10) = 25 and C(9,10) = 2\times 25 - 5 = 45. Using this example you can easily prove the generalized statement by exploiting the bilateral symmetry of grid and x about ythe dotted line.

Though  I suspected that least common multiple of m-1, n-1 determine the number of steps my algorithm evaluates, Pritam Laskar  found the exact formula.

Given a m\times n grid, the Cross Diagonal Cover algorithm terminates after  lcm(m-1, n-1) + 1  steps.

For proof, follow the arguments of grant93jr in his/her comment (he/she mistakenly called their lcm to be their gcd).

Using the SageMath Program, about which I wrote in previous post, I am pretty sure that \gcd(m,n) always divides the number of filled squares. So, now the question is

Why the greatest common divisor of m and n always divides the number of filled squares?

 

Cross Diagonal Cover – IV

Standard

While discussing this problem with Dr. Shailesh Shirali, he commented that there has to be a way to phrase the problem in terms of a ray of light being reflected off the walls of the rectangle, bouncing around, proceeding from one corner to some other corner.

The problem in re-stating my problem in “light reflection” form was that reflections must be from center of squares and this is not the way light “actually” reflects from surfaces. But, I clubbed that idea with “graph theory” (directed graphs), which actually answers the first question I asked in my previous post:

Why no filled square has more than 2 crosses?

As per my “Cross diagonal cover algorithm” we can’t retrace a path and each square has just two diagonals. Hence, if we replace all the squares by their centers then each center is of degree two (i.e. can allow intersection of at most two distinct paths). Hence proving that no filled square can have more than 2 crosses. For example:

New Doc 22_1

Now moving to the bigger question of counting the total number of filled squares, there hasn’t been much progress yet (even on arriving at a concrete conjecture). But, Prof. Amritanshu Prasad wrote a SageMath  program for my algorithm which enables us to find number of the filled squares for individual cases without actually drawing them! For Example: for m=101 , n=102 grid, there will be 5151 = (101 * 102 )/ 2 filled squares. Pretty cool 🙂

SageMath is is an open source implementation of mathematics and scientific software based on Python 2.  Unfortunately, since the SageMath program is essentially a Python script I am not allowed to embed  it in my WordPress.com blog. But, motivated by my discussions with Ms. Marina Ibrishimova, I tweaked Prof. Prasad’s original source-code and added comments (initialized by #) to make it self explanatory.

Here is the SageMath (or Python) code to count the number of filled squares for 2 \leq m\leq n\leq 10

#-----START OF PYTHON FUNCTION FOR CROSS DIAGONAL COVER ALGORITHM-----

def cover(m,n):
#a function to count the number of squares covered in a grid with m rows
#and n columns
    xinc = 1
#we will use this variable to increment (or decrement) the value of
#x-coordinate (row position) by 1 unit after each step
    yinc = 1
#we will use this variable to increment (or decrement) the value of
#y-coordinate (column position) by 1 unit after each step
    pos = [1, 1]
#we are assuming our grid to have at least 2 rows and 2 columns
#and will initialize counting from (1,1) position.
    visited = [[0, 0], [1, 1]]
#since we start from (1,1) position, we implicitly assume to have
#counted (0,0) position.
    while pos != [m-1, 0] and pos != [0, n-1] and pos != [m - 1, n - 1]:
#whenever we reach any corner the algorithm terminates, so need to include
#position of other three corners apart from starting corner in condition.
          if pos[0] in [0, m-1]:
#evaluates to true if x-coordinate of current position is a
#member of the collection [0,m-1]
             xinc = - xinc
#if x-coordinate is either 0 or m-1 then we will switch diagonal
#by switching the sign of xinc
          if pos[1] in [0, n-1]:
#evaluates to true if y-coordinate of current position is a member
#of the collection [0,n-1]
             yinc = -yinc
#if y-coordinate is either 0 or n-1 then we will switch diagonal
#by switching the sign of yinc
          pos[0] += xinc
#update the x-coordinate of new position as x(new) = x(old) + xinc,
# where xinc = 1 or -1.
          pos[1] += yinc
#update the y-coordinate of new position as y(new) = y(old) + yinc,
# where yinc = 1 or -1.
          if not (pos in visited):
#if this new state is not there in visited positions list
             visited.append([pos[0], pos[1]])
#then add this new position to the list of visited positions.
    return visited 

#---------------END OF FUNCTION---------------

#we will write a small code to be able to use above function to find number of
#filled squares for all grids where m,n lie between 1 and 11 (both excluded).

for i in range (2, 11):
#The range() function provides an easy way to construct a list of integers.
#The range() function only does numbers from the first to the last,
#not including the last.
    for j in range(i, 11):
        print i, j, len(cover(i, j))
# len(indata) counts the bytes of data in indata here it
#counts the number of elements is visited list.

To run the above code, please copy-paste it in SageMathCell and click evaluate button. You will get the list displaying m, n and the number of filled squares in each of the grid (with 1<m,n<11).

In case you want to understand above Python function, here is an illustration when m=3 and n=4:

New Doc 23_1

Note that though (1,1) position is encountered twice but it is added to “visited squares” list only once.

So far I haven’t been able to derive a useful interpretation even after getting access to lot of data. I hope to formulate a conjecture soon…

 

Cross Diagonal Cover – III

Standard

I found many counterexamples to my conjecture, like

  • for Case 2 in 7 by 5 grid we have 12, 11 by 5 grid we have 19 and 15 by 5 grid we have 26 filled squares
  • for Case 3 in 4 by 10 grid we have 10 filled squares

In a comment by grant93jr   following part of of my initial question, to determine the number of squares in m\times n grid that can be covered by crosses (x) by following Cross Diagonal Cover Algorithm, was proved:

Given m>n, whenever n-1 divides m-1 we have m filled squares.

Examples of such grids are: 3 by 5, 4 by 7, 4 by 10, ….

Also in that comment it has been suggested that the algorithm terminates after k(m-1) = l(n-1) steps where k, l are natural numbers. It is certainly true, but I haven’t been able to use this idea for counting number of filled squares when n-1 does not divide m-1 since in that case some squares are filled twice.

There is another unexplained observation:

Why no filled square has more than 2 crosses?

Frustrated by so many unanswered questions I started colouring squares, so that number of times I visited a square is not visible. Since I really don’t care about how many times I visited  given square while counting the number of filled squares this may help in understanding the underlying symmetry.

New Doc 21_1

Replacing cross (x) by any colour and applying Cross Diagonal Cover Algorithm

After observing above diagrams I suspect that my algorithm leads to a non-deterministic cellular automata.

So, the question which still remains to be answered is:

How many filled squares are there when  m>n and n-1 does not divide m-1 ?

Examples of such grids are: 7 by 5, 11 by 5, 15 by 5 …

 

Cross Diagonal Cover – II

Standard

I will continue the previous post. Now the question to  be answered is that:

What percentage (or how many) of given m\times n grid can be covered by following Cross Diagonal Cover Algorithm?

I did some calculations, for example:

 

New Doc 16_1

As per my calculations, I have following conjecture:

The following 3 cases are possible:

  1. If m = n, then m squares will be covered.
  2. If m>n and both m,n are odd, then m squares will be covered.
  3. If at least one of m,n is even then \frac{mn}{2} squares will be covered.

As you can see that Case – 1 is quite trivial. I tried to prove other two cases for one week, but failed, so decided to post it as conjecture.

Cross Diagonal Cover – I

Standard

While doodling in my college classes, I designed an algorithm which I called Cross Diagonal Cover Algorithm:

I have a m\times n rectangle divided into unit squares. I start by placing a x (cross) in leftmost corner. Every time I visit a square in diagonal direction I place a  x in the squares till I reach any boundary of rectangle, from where I switch to adjacent diagonal.

New Doc 17_1

Illustrating the algorithm… Follow the arrow numbers to fill the grid.

Please note that it doesn’t matter that how many x (cross) are there in each square. The number of x (cross) in each square just signify number of times I visited that square while executing the algorithm.

Then I asked myself the following question:

Can I cover whole grid with at least one x in each unit square?

The answer to my above question is NO! The proof is pretty easy.

If m=n then it’s trivial that I can’t cover the whole grid with x since I will  be tracing the main diagonal again and again.

Moreover, the key observation here is that I will be stuck in loop (which can’t cover whole grid) whenever I reach another corner of the grid since it supports only one diagonal. Since I want to cover whole grid I must visit all the corners but they are dead ends!

Quod Erat Demonstrandum.

Any references about this idea from literature would be appreciated. I am working on a better question on “Cross Diagonal Cover Algorithm”, which I will discuss in next post.