Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was working with a piece of code when I stumbled across a matrix, which is similar to this:

$$\begin{matrix} 0&1&0&1&0&1&0&\cdots\\ 1&1&1&1&1&1&1&\cdots\\ 0&1&0&1&0&1&0&\cdots\\ 1&1&1&1&1&1&1&\cdots\\ 0&1&0&1&0&1&0&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots \end{matrix}$$

The rule is: no $0$ should be adjacent to another (diagonally/vertically/horizontally)

The matrix is my representation for the rule.

I was trying to figure out the formula for finding for any given $N \times M$ matrix (like the one above), what will be the maximum number of $0$'s possible.

Finally, I gave up and settled for a code which did the labor counted them. I was hoping if someone here could help with a formula or a better approach?

share|improve this question
    
there are many other representations of the rule. I think you should clarity that you are interested only in your technique of looking at it. –  picakhu Nov 17 '11 at 15:50
    
I included the rule to help read the matrix. Otherwise, I think the title itself clarifies that I'm interested in the matrix alone. –  loxxy Nov 17 '11 at 15:54

2 Answers 2

up vote 3 down vote accepted

It is not hard. Let us first consider the rows. If a row has size $\leq 2$, you have $1$ zero; if it has size $\leq 4$, you have $2$ zeros; $\ldots$ if it has size $\leq M$, you have $\left\lceil \frac{M}{2} \right\rceil$ zeroes (the odd sign is the ceiling function) in the rows, and similarly $\left\lceil \frac{N}{2} \right\rceil$ in the columns.

Therefore, you get:

$$f(N,M) = \left\lceil \frac{M}{2} \right\rceil \cdot \left\lceil \frac{N}{2} \right\rceil$$

share|improve this answer
1  
Thank you for the clear explanation. –  loxxy Nov 17 '11 at 14:04

Letting $\mathbf M$ be your matrix, we can use either the Kronecker delta function or Iverson brackets to represent the entries $m_{jk}$.

Using Iverson brackets, we have the rule

$$m_{jk}=[(j\bmod 2=0)\lor(k\bmod 2=0)]$$

while the version with Kronecker delta is

$$m_{jk}=1-\delta_{j\,\bmod \,2,1}\delta_{k\,\bmod \,2,1}$$


Counting the number of $0$'s in an $n\times r$ version of $\mathbf M$ is easily done through the sum

$$\sum_{j=1}^n\sum_{k=1}^r (1-[(j\bmod 2=0)\lor(k\bmod 2=0)])$$

Using de Morgan's laws along with the properties $1-[p]=[\lnot p]$ and $[p \land q]=[p][q]$, we have the equivalent representation

$$\sum_{j=1}^n\sum_{k=1}^r [j\bmod 2=1][k\bmod 2=1]$$

which can be rearranged to

$$\left(\sum_{j=1}^n [j\bmod 2=1]\right)\left(\sum_{k=1}^r [k\bmod 2=1]\right)$$

which simplifies to

$$\left(\left\lfloor\frac{n-1}{2}\right\rfloor+1\right)\left(\left\lfloor\frac{r-1}{2}\right\rfloor+1\right)$$

or

$$\left\lfloor\frac{n+1}{2}\right\rfloor\cdot\left\lfloor\frac{r+1}{2}\right\rfloor$$

which is equivalent to Listing's expression.

share|improve this answer
    
Nice way to get it, I think our formulas are equivalent too. –  Listing Nov 17 '11 at 14:34
1  
Heh, I was in the middle of fiddling Iverson brackets when your answer showed up. :) I think you're right, since $\left\lfloor\frac{n+1}{2}\right\rfloor=\left\lceil\frac{n}{2}\right\rceil$ for integer $n$... –  J. M. Nov 17 '11 at 14:39
    
Nice to see a good proof for the solution. Thanks. –  loxxy Nov 17 '11 at 15:55
    
@loxxy You seem to be quite new here, note that if you like this answer more than mine you can always change your current accepted answer to another one ;-) –  Listing Nov 17 '11 at 17:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.