Cross Diagonal Cover – VI


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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s