2
$\begingroup$

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?

  • 0
    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.2011-11-17
  • 0
    I included the rule to help read the matrix. Otherwise, I think the title itself clarifies that I'm interested in the matrix alone.2011-11-17

2 Answers 2

3

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$$

  • 1
    Thank you for the clear explanation.2011-11-17
3

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.

  • 0
    Nice way to get it, I think our formulas are equivalent too.2011-11-17
  • 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$...2011-11-17
  • 0
    Nice to see a good proof for the solution. Thanks.2011-11-17
  • 0
    @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 ;-)2011-11-17