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