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
    I included the rule to help read the matrix. Otherwise, I thin$k$ the title itself clarifies that I'm interested in the matri$x$ 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
    @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