Tuesday, April 01, 2014

How many walls/borders has a nxn grid?

While implementing an algorithm for a hobby project, I came across the question how many walls (or borders) has a nxn grid? Here I present the solutions of my line of thought: the first one is quite complicated, but was also the first which came into my mind. After convinced of the correctness of this one, a much easier idea occured... :-)

Lets start: A 1x1 grid has 4 walls which is easy to see:
 _
|_| = 1 cells --> 4 walls

Lets have a look at a 2x2 grid:
 _ _
|_|_|
|_|_| = 2 cells --> 12 walls (feel free to count it :-)

So my idea to get the equation of a nxn grid is based on following image / procedure:

   1 2 ... n
   _ _     _
1 |_|_|...|_|
2 |_|_|_|_|_|   
   . _|   .
   _ _|   .
n |_|_|... _|
  
1. Start with the (orange) cell in the topleft corner which has 4 walls: 4
2. Lets move in the top row further to the right (cyan). For each of the remaining n-1 cells in this row, there are 3 walls per cell left: (n-1) * 3
3. The same applies if we go down in the first column step by step until the red cell. So for each cell there are also 3 walls left: (n-1) * 3
4.  Then there is (n-1) x (n-1) grid left. However if we go there row by row and column by column, it turns out that for each cell only two more walls come along (the wall at the bottom and at the right), because the left and top wall were then already taken into account. So (n-1) * (n-1) * 2 walls are left.

So in total we have come up with following equation for an nxn grid:
x = 4 + (n-1)*3 + (n-1)*3 + (n-1)*(n-1)*2
   = 4 + 3n - 3 + 3n - 3 + (n^2 -2n +1)*2
   = 4 + 6n - 6 + 2n^2 - 4n + 2
   = 2n^2 + 2n
   = 2n (n+1)

Manually checking of the cases n=3 and n=4 turned out to be correct, so I guess it's ok.

However, afterwards a more simple solution came into my mind by just looking at the vertical walls only and at the horizontal walls separately:

   1 2 ... n
   _ _     _
1 |_|_|   |_|
2 |_|_|   |_|
  .
   _ _     _
n |_|_|...|_| 

1. If just looking at the vertical walls (red), we see that there are n rows, each having n+1 walls: n * (n+1) walls in total.
2. The same applies for the horizontal walls (cyan): n columns * (n+1) walls.

This is in total:
y = n * (n+1) + n * (n+1)
  = n^2 + n * n^2 + n
  = 2n^2 + 2n
  = 2n (n+1)
  = x

That's it :-)

No comments: