cortar un pastel sin destruir los ingredientes

Question

Hay una plaza de la torta. Contiene N ingredientes - N discontinuo alineado al eje rectángulos. Los ingredientes pueden tener diferentes anchos y alturas, y no necesariamente cubrir todo el pastel.

Quiero dividir la torta en 2 no vacía piezas rectangulares, ya sea por un corte horizontal o vertical, de tal manera que el número de coberturas de destruir (es decir, de la cruz en el interior) es mínimo.

¿Cuál es el número de ingredientes que voy a tener que destruir, en el peor de los casos, como una función de N?

LÍMITES:

Límite superior $N/2$:

Tomar cualquier corte horizontal. Si se pasa de no más de N/2 ingredientes, entonces hemos terminado. De lo contrario, hacer un corte vertical entre dos de los cruzados rectángulos. Este corte vertical no cruzar ninguna rectángulo atravesado por la corte horizontal, por lo que se cruza en la mayoría de los N/2 ingredientes.

Límite inferior $N/4$:

En el siguiente bizcocho, con 4 ingredientes, cada corte debe cruzar al menos 1 topping:

aaaaaaaa bb
aaaaaaaa bb
cc ..... bb
cc ..... bb
cc ..... bb
cc dddddddd
cc dddddddd

Como MvG sugerido, es posible cortar cada rectángulo en $N/4$ tiras paralelas, lo que obligó a cortar para destruir al menos $⌊N/4⌋$ ingredientes.

NOTA: me acabo de enterar de que este problema está relacionado con el tema de la Geométrica de los separadores. El límite inferior y el límite superior de las pruebas se presentan en la Sección 4 de Smith y Wormald (1998). Todavía hay una brecha entre el límite inferior y superior.

Answer 1

El límite inferior $r=\lfloor \frac N4\rfloor$ es también un límite superior:

Se supone que en un cuadrado con los ingredientes, uno debe cortar al menos $r>1$ ingredientes con cada corte. El número de los bordes de la plaza, con $E_1,E_2,E_3,E_4$ de las agujas del reloj, y establecer $\varepsilon_i=min\{d(E_i,R_j)\ :\ d(E_i,R_j)>0\}$, donde $R_j$ es cualquiera de los bordes de un rectángulo de los ingredientes, la cual es paralela a $E_i$. Tenga en cuenta que $\varepsilon_i$ puede ser la distancia de un rectángulo en el borde de la $E_i$ o el ancho del rectángulo (y en ese caso el rectángulo tiene un borde en $E_i$). Elija uno de los rectángulos que definen $\varepsilon_i$ nombre $R_i$.

Set $T_i$ a ser la línea paralela a $E_i$ a una distancia $\varepsilon_i$. Por nuestra suposición, $T_i$ debe cortar al menos $r$ rectángulos, denota el conjunto de estos rectángulos con $S_i$. Tenga en cuenta que, por el minimality de $\varepsilon_i$, todos los rectángulos en $S_i$ tienen un borde contenida en $E_i$.

Claramente $R_i\notin S_i$, y también es fácil comprobar que $R_i\notin S_{i+2}$, los subíndices tomada $i\mod 4$, ya que entonces no sería un corte a lo largo de un lado de la $R_i$ que los recortes en la mayoría de los 1 topping. También tenemos $S_1\cap S_3=\emptyset$, ya que un rectángulo $R$ $S_1\cap S_3$ nos permite cortar a través de la media de $R$, en paralelo a $E_2$, de corte a través de un único rectángulo (topping). Del mismo modo $S_2\cap S_4=\emptyset$. Ahora suponemos que para un determinado número de $r$ (de un mínimo número de ingredientes destruido por un corte) el número de $N$ de los rectángulos es mínima. Podemos suponer que en esta configuración podemos elegir los rectángulos $R_i$ tener una ventaja contenida en $E_i$. De hecho, si no hay un rectángulo con un borde en $T_i$ toques $E_i$, entonces podemos extender uno de los rectángulos con la distancia $\varepsilon_i$ , por lo que toca a $E_i$. La nueva configuración tiene el mismo número de rectángulos, y el número de ingredientes destruido por cada corte es igual o ha aumentado en uno.

Deje $r_1$ ser el nuevo número mínimo de ingredientes destruido por un corte, y por lo $r_1\ge r$. Tenga en cuenta que, finalmente, el $\varepsilon_i$ han cambiado. Pero ahora, para cada arista $E_i$ hay $r_1+1$ rectángulos con un borde contenida en $E_i$, $r_1$ rectángulos (el nuevo) $S_1$ y el rectángulo $R_i$. Ninguno de estos rectángulos pueden tener dos aristas contenidas en los bordes opuestos $E_i,E_{i+2}$, y no puede haber más de un rectángulo con una esquina en $E_i,E_{i+1}$. Por lo tanto, hay por lo menos $|S_1|+|S_2|+|S_3|+|S_4|+4-4$ distintos rectángulos. Llegamos a $$ N\ge |S_1|+|S_2|+|S_3|+|S_4|\ge 4r_1\ge 4r\quad\Rightarrow \quad 4r\le N \quad\Rightarrow \quad r\le \left\lfloor \frac N4\right\rfloor. $$

Answer 2

Suponiendo que el pastel está abierto, y los ingredientes que están abiertas, podemos posición para un corte entre el borde y el relleno es imposible, y los cortes entre los ingredientes son posibles.

Parece que $\lfloor \frac{N}{4} \rfloor$ es el consumo máximo de caso para un determinado$N>1$, en sus dos dimensiones de la torta, como se demuestra por su $N=4$ disposición. Para $N=8$ poner en paralelo dos ingredientes, donde cada uno de ustedes. Para $N=4k$ puesto $k$ paralelo ingredientes.

Para $N=1$ sólo tiene que utilizar una sola batida cubriendo toda la superficie.

La prueba de que para $N=2$ o $N=3$ no hay ninguna disposición que requiere un corte relleno es un primer paso para demostrar la $\lfloor \frac{N}{4} \rfloor$ es la fórmula correcta.