Monthly Archives: April 2016

Apr27

Cross Diagonal Cover – III

Posted on by
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 …

 

Apr19

Cross Diagonal Cover – II

Posted on by
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.

Apr12

Cross Diagonal Cover – I

Posted on by
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.

Apr4

Integration & Summation

Posted on by
Standard

A few months ago I wrote a series of blog posts on “rigorous”  definitions of integration [Part 1, Part 2]. Last week I identified an interesting flaw in my “imagination” of integration in terms of “limiting summation” and it lead to an interesting investigation.

The Paradox

While defining integration as area under curve, we consider rectangles of equal width and let that width approach zero. Hence I used to imagine integration as summation of individual heights, since width approaches zero in limiting case. It was just like extending summation over integers to summation over real numbers.

integration (1)

My Thought Process..

But as per my above imagination, since width of line segment is zero,  I am considering rectangles of zero width. Then each rectangle is of zero area (I proved it recently). So the area under curve will be zero! Paradox!

I realized that, just like ancient greeks, I am using very bad imagination of limiting process!

The Insight

But, as it turns out, my imagination is NOT completely wrong.  I googled and stumbled upon this stack exchange post:

There is the answer by Jonathan to this question which captures my imagination:

The idea is that since \int_0^n f(x)dx can be approximated by the Riemann sum, thus \displaystyle{\sum_{i=0}^n f(i) = \int_{0}^n f(x)dx + \text{higher order corrections}}

The generalization of above idea gives us the Euler–Maclaurin formula 

\displaystyle{\sum_{i=m+1}^n f(i) = \int^n_m f(x)\,dx + B_1 \left(f(n) - f(m)\right) + \sum_{k=1}^p\frac{B_{2k}}{(2k)!}\left(f^{(2k - 1)}(n) - f^{(2k - 1)}(m)\right) + R}

where m,n,p are natural numbers, f (x) is a real valued continuous function, B_k are the Bernoulli numbers and R is an error term which is normally small for suitable values of p (depends on n, m, p and f).

Proof of above formula is by principle of mathematical induction. For more details, see this beautiful paper: Apostol, T. M.. (1999). An Elementary View of Euler’s Summation Formula. The American Mathematical Monthly, 106(5), 409–418. http://doi.org/10.2307/2589145