Cross Diagonal Cover - VI
Published:
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 15x5, there are 26 filled squares and gcd(15,5)=5, so 15x5 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.
PAST BLOG POSTS: Part I, Part II, Part III, Part IV, and Part V.