Fórmula para el número de 0's en una matriz alternada 0-1

Question

Estaba trabajando con un trozo de código cuando me topé con una matriz, que es similar a esta:

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

La regla es: no $0$ deben ser adyacentes a otro (en diagonal/vertical/horizontal)

La matriz es mi representación de la regla.

Estaba tratando de averiguar la fórmula para encontrar para cualquier $N \times M$ matriz (como la anterior), ¿cuál será el número máximo de $0$ es posible.

Finalmente, me rendí y me conformé con un código que hacía el trabajo contado. Esperaba que si alguien aquí pudiera ayudar con una fórmula o un mejor enfoque?

Answer 1

No es difícil. Consideremos primero las filas. Si una fila tiene un tamaño $\leq 2$ , usted tiene $1$ cero; si tiene tamaño $\leq 4$ , usted tiene $2$ ceros; $\ldots$ si tiene tamaño $\leq M$ , usted tiene $\left\lceil \frac{M}{2} \right\rceil$ ceros (el signo impar es el función de techo ) en las filas, y de forma similar $\left\lceil \frac{N}{2} \right\rceil$ en las columnas.

Por lo tanto, se obtiene:

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

Answer 2

Dejar $\mathbf M$ sea su matriz, podemos utilizar el Función delta de Kronecker o Soportes Iverson para representar las entradas $m_{jk}$ .

Utilizando los paréntesis de Iverson, tenemos la regla

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

mientras que la versión con delta de Kronecker es

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

---

Contar el número de $0$ 's en un $n\times r$ versión de $\mathbf M$ se hace fácilmente a través de la suma

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

Utilizando Las leyes de Morgan junto con las propiedades $1-[p]=[\lnot p]$ y $[p \land q]=[p][q]$ tenemos la representación equivalente

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

que se puede reordenar como

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

que se simplifica a

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

o

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

que es equivalente a la expresión de Listing.