Dado un $n\times n\times n$ cubo, ¿cuál es el mayor número de $1\times 1\times 1$ bloques que un avión puede cortar a través de?

Question

Esta pregunta es de la recreación de la naturaleza, pero podría ser más grave.

Dado un $3\times 3\times 3$ cubo, ¿cuál es el número máximo de pequeño $1\times 1\times 1$ bloques de un avión puede cortar a través de? De manera más general, acerca de cómo un $n\times n\times n$ cubo?

Hay referencia general sobre este tipo de preguntas?

---

Batominovski de edición:

Un Límite Inferior

Tenga en cuenta que, en una $3\times 3$ plaza, es posible cortar cinco $1\times 1$ células con una línea. Por lo tanto, es posible cortar, al menos, $3\cdot 5=15$ unidad de bloques de un $3\times 3\times 3$ cubo con un plano. Por lo tanto, $15$ es un límite inferior para la respuesta correcta.

Para el caso general, puede ser fácilmente visto que podemos cortar un $n\times n$ cuadrado con una línea que pasa a través de $2n-1$ unidad de las células. Así, en el $3$-ajuste dimensional, podemos cortar un $n\times n\times n$ cubo con un plano que pasa a través de $n(2n-1)$ unidad de los bloques. Por lo tanto, $n(2n-1)$ es un límite inferior para la respuesta correcta.

Answer 1

Esta respuesta se soluciona el $3\times 3\times 3$ caso y hace una conjetura acerca de nuevos casos.

Para dar una respuesta, primero imaginar cómo podemos crear el da $n\times n\times n$ cubo en el primer lugar de tomar todos los de $\mathbb R^3$. Dibujar $(n+1)$ paralelas igualmente espaciadas planos. Deseche todo mentira "fuera" de la parte más externa de dos planos e imaginar el espacio dentro para ser cortado por cada uno de los restantes $(n-1)$ aviones. Repita este proceso para crear un conjunto de planos perpendiculares a la serie original y, a continuación, para un conjunto de planos perpendiculares a ambos conjuntos hasta ahora, cada espaciados por igual a la primera.

Tenga en cuenta que "perpendicular" aquí es irrelevante como es el de la igualdad de la separación entre los tres grupos, ya que el problema solo se hace referencia lineal de la estructura, así como elegimos a las orientaciones de los planos para ser independiente y mantener el espacio dentro de cada conjunto de constantes, el problema es invariable.

El truco es elegir el avión que desea utilizar para cortar el cubo de la primera y, a continuación, realice el procedimiento anterior y ver lo que sucede en el plano. En particular, después de los dos primeros conjuntos de los sectores, de que el avión se han reducido y se cortan en un $n\times n$ cuadrícula de paralelogramos y, una vez más, sólo una estructura lineal de ser pertinente, se puede reducir a la siguiente pregunta:

Supongamos que tenemos una $n\times n$ cuadrícula de cuadrados. Sorteo de un set de $(n+1)$ paralelas y líneas equidistantes. Deseche todos los cuadrados totalmente fuera de los límites de estas líneas y de imaginar las plazas a cortar en cada uno de los restantes $(n-1)$ líneas. Cuántas regiones podrían quedan?

Esta pregunta parece más accesible - como ocurre en 2D de la cuadrícula en lugar de un espacio 3D. Un montón de sutilezas que sucede cuando uno intenta resolver la pregunta anterior, a pesar de que usted ciertamente no tiene ninguna de las líneas adicionales pasar a través de cualquier de las esquinas de las plazas, como la perturbación de cualquier corte tenga esta propiedad daría más piezas. Por otra parte, se puede expresar el número de piezas como "el número de plazas no totalmente descartado, más el número de segmentos de línea cortada de las líneas intermedias por las plazas."

Ciertamente no se puede hacer mejor que el corte de $n^2 + (n-1)(2n-1)=3n^2-3n+1$ regiones siguiendo la lógica anterior, pero para lograr esto requerirá que ningún plaza está completamente descartado, pero cada corte intermedio atraviesa el máximo de $(2n-1)$ plazas interiores - que es claramente imposible para la gran $n$.

Yo podría adivinar que la configuración óptima para $n\geq 3$ es tomar el más largo de la diagonal en la $n\times n$ plazas y sacar el mayor $(n+1)$ líneas para entrar en cada punto en el que la diagonal y que esta cada cuadrado en el plazo de dos plazas de la diagonal tiene al menos parte de la misma entre el exterior de la delimitación de las líneas y de modo que cada línea intermedia de aciertos de cada cuadrado de la diagonal, sin ser exactamente diagonal - lo que significa que cada línea intermedia cruces $(2n-1)$ plazas y que $n+2(n-1)+2(n-2)$ plazas no están totalmente descartados y $(n-1)(2n-1)$ son cortadas por el intermedio de líneas para un total de $2n^2+2n - 5$ regiones a la izquierda - es decir, que un avión a través de una $n\times n \times n$ cubo puede golpear al menos $2n^2+2n-5$ de la $1\times 1\times 1$ cubos. Esta podría ser la óptima, pero no es claro si el ensanchamiento de la distancia entre las líneas exteriores para incluir más plazas, al menos parcialmente, podría compensar que algunas líneas, a continuación, cree un menor número de nuevas regiones - y el razonamiento a la figura que parece muy sensible, ya que no importa lo que haga, parece que, no importa lo que hagas, vas a permanecer en la orden de $2n^2$ con sólo un orden inferior de los términos en juego.

Observe que el límite inferior y límite superior son iguales a $19$ cuando $n=3$ - así que esta es la respuesta para un $3\times 3\times 3$ cubo y una hipótesis para cubos grandes. Para la concreción, si asumimos que este es el cubo de $[-3,3]\times [0,3]\times [0,3]$, un avión alcanzar este máximo está definido por $z = x+y-\frac{3}2$, señalando relevante de cada cuadrado de la $x$-$y$ plano se encuentra al menos parcialmente, en la región de $0\leq x+y - \frac{3}2\leq 3$ - por lo que un cubo en cada $z$ columna se incluye - y las líneas de $x+y-\frac{3}2=1$ y $x+y-\frac{3}2=2$ cada golpe de cinco plazas - aportando un extra de cubo para cada uno de estos incidentes, para un total de $10$ cubos (o, específicamente: dos columnas de esquina ha $1$ cubo de aciertos de cada uno, los cuatro medio-de-borde de las columnas $2$ cubos de aciertos de cada uno, y las tres diagonales de las columnas de cada uno obtenga $3$ cubos de aciertos de cada uno, para un total de $19$ cubos golpeado por el avión).

---

Edit: Algunos resultados computacionales: si sólo tenemos en cuenta los planos de la forma $x+y+k\cdot z = (k+2)n/2$ - que son los planos que pasan por el centro pivotante alrededor de un cierto eje (elegido de manera que en el diagrama de plazas, el añadido de las líneas en diagonal - aunque no hay ningún tipo de razón para creer que esta es la óptima) - podemos, de hecho, sólo tiene que utilizar un ordenador para ver lo que el óptimo $k$ son. La propuesta de instalación óptima de arriba es no apto para todos los $n$ (y no es la sugerencia de la elección de $k=1$).

Para $n=3$, un máximo de $19$ cubos de afectados por estos planos se logra por $2/3 < k < 2$. Para $n=4$, un máximo de $35$ cubos pueden ser golpeado por $1/2 < k < 1$. Para $n=5$ a un máximo de $57$ cubos pueden ser golpeado por $5/4 < k < 4/3$. Para $n=6$ a un máximo de $81$ son golpeados por $2/3 < k < 1$. Para $n=7$ a un máximo de $113$ cubos pueden ser golpeado por $8/7 < k < 5/4$. Para $n=8$ obtenemos un máximo de $145$ para $3/4 < k < 1$. Para $n=9$, se obtiene un máximo de $187$ cubos de éxito para $10/9 < k < 9/8$. Parece ser que hay algunos patrones, pero las tramas de la cantidad de cubos que golpea de frente a la pendiente son muy irregulares, saltando arriba y abajo aparentemente al azar y claramente dependiendo de la paridad. Este problema puede no ser tan clara como yo había pensado que no tenemos ni idea de cómo resolverlo en general.

Answer 2

Dado un cubo de $n \times n \times n$ o $[0,\, n]^3$ queremos encontrar el avión $ax+by+cz=d$ que cruza el mayor número de cubos unitarios dentro de $[0,\, n]^3$, y encontrar ese número.

Podemos hallar una sola unidad de cubo de la $[x_k,\, x_k+1] \times [y_j,\, y_j+1] \times [z_l,\, z_l+1]$, con $j,k,l \in [0, \, n-1]$.

Los cubos atravesado por el avión va a ser aquellos para los cuales $$ \eqalign{ & ax_{\,k} + by_{\,j} + cz_{\,l} < d < a\left( {x_{\,k} + 1} \right) + b\left( {y_{\,j} + 1} \right) + c\left( {z_{\,l} + 1} \right)\quad \Rightarrow \cr & \Rightarrow \quad d - \left( {a + b + c} \right) < ax_{\,k} + by_{\,j} + cz_{\,l} < d\quad \Rightarrow \cr & \Rightarrow \quad {d \over {a + b + c}} - 1 < {{ax_{\,k} + by_{\,j} + cz_{\,l} } \over {a + b + c}} < {d \over {a + b + c}} \cr} $$

Considere la posibilidad de $x_k$ como la realización de un uniforme discreta variable aleatoria $x$ sobre el apoyo a la $[0,\, n-1]$, con una probabilidad de $1/n$, la media de $(n-1)/2$ y la varianza $(n^2-1)/12$ .
Mismo para $y, \, z$.

Su suma ponderada $$ {{ax_{\,k} + by_{\,j} + cz_{\,l} } \over {a + b + c}} $$ tendrá media, moda y mediana en $(n-1)/2$ y la varianza $$ \sigma ^2 = {{a^2 + b^2 + c^2 } \over {\left( {a + b + c} \right)^2 }}\left( {{{n^2 - 1} \over {12}}} \right) $$

Claramente, la menor es la varianza de la más grande es la porción de la pmf que satisface la desigualdad dada anteriormente, puesto que la desigualdad del medidor es constante en $1$.
Y la varianza es claramente mínimo para la igualdad de pesos.

Así llegamos a considerar la desigualdad $$ \bbox[lightyellow] { \left\{ \matriz{ x_{\,k} ,y_{\,j} ,z_{\,l} ,n,s \in \mathbb Z \hfill \cr d \in \mathbb R \hfill \cr 0 \le x_{\,k} ,y_{\,j} ,z_{\,l} \le n - 1 \hfill \cr d - 3 < x_{\,k} + y_{\,j} + z_{\,l} = s < d \hfill \cr} \right. \etiqueta{1}}$$

Ahora, el número de puntos en el plano diagonal de un $m$-D cube $$N_{\,b} (s,r,m) = \text{No}\text{. de soluciones a}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{reunieron} \right.$$ está dada por $$ \bbox[lightyellow] { N_b (s,r,m)\quad \left| {\;0 \leqslant \text{números enteros }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{i+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {i + 1} \right) } { s - k\left( {i + 1} \right)}\ } \etiqueta{2.un}}$$ como se explica en este post.

Por otra parte el número de puntos en o por debajo de la diagonal del plano son $$ \bbox[lightyellow] { \eqalign{ & M_b (s,r,m)\quad \left| {\;0 \le {\rm enteros }s,m,r} \right.\quad = \cr & = \sum\limits_{0\, \le \,\,j\,\, \le \,s} {N_b (s,r,m)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over {i + 1}}\, \le \,m} \right)} {\left( { - 1} \right)^k \left( \matriz{ m \hfill \cr k \hfill \cr} \right)\left( \matriz{ s + m - k\left( {i + 1} \right) \cr s - k\left( {i + 1} \right) \cr} \right)} \cr} \etiqueta{2.b}}$$

En este punto necesitamos la ayuda de una visualización gráfica para comprender el comportamiento de la desigualdad 1) wrt $N_b$

El dibujo representa los histogramas de $N_{\,b} (s,n-1,3)$ para $n=3$ e $n=4$.
$N_{\,b} (s,n-1,3)/n^3$ es el pmf de la suma de $s$ de los tres uniformes discretas variables aleatorias.
El dibujo muestra que la mayor parte de el histograma es interceptado cuando el medidor de ancho de $3$ de la desigualdad es casi centrado alrededor de la media.
Que es en realidad, así que cuando n es impar, mientras que para incluso $n$ vamos a cambiar el calibre ligeramente a la izquierda (o a la derecha).
Por desgracia, la fórmula para $N_b$ sólo es válida para la integral parámetros (reescritura de la binomial a través de gamma produce una función discontinua).

Podemos eludir el de arriba y el uniforme de la desigualdad mediante la introducción de un fijo $1/2$ cambio de la media y, a continuación, la reescritura de la desigualdad como $$ \eqalign{ & d - 3 < x_{\,k} + y_{\,j} + z_{\,l} = s < d\quad \Rightarrow \cr & \Rightarrow \quad 3{{n - 1} \over 2} - 3/2 - 1/2 < s \le 3{{n - 1} \over 2} + 3/2 - 1/2\quad \Rightarrow \cr & \Rightarrow \quad \left\lfloor {3{{n - 1} \over 2} - 3/2 - 1/2} \right\rfloor < s \le \left\lfloor {3{{n - 1} \over 2} + 3/2 - 1/2} \right\rfloor \cr} $$ y en general, para una dimensión $m$ $$ \bbox[lightyellow] { \eqalign{ & d - m < x_{\,k} + y_{\,j} + z_{\,l} = s < d\quad \Rightarrow \cr & \Rightarrow \quad m{{n - 1} \over 2} - m/2 - 1/2 < s \le m{{n - 1} \over 2} + m/2 - 1/2\quad \Rightarrow \cr & \Rightarrow \quad \left\lfloor {{{mn - 1} \over 2}} \right\rfloor - m < s \le \left\lfloor {{{mn - 1} \over 2}} \right\rfloor \cr} \etiqueta{3}}$$ lo que conduce a $$ \bbox[lightyellow] { N(n,m) = M_b \left( {\left\lfloor {{{mn - 1} \over 2}} \right\rfloor ,\;n - 1,\;m} \right) - M_b \left( {\left\lfloor {{{mn - 1} \over 2}} \right\rfloor - m,\;n - 1,\;m} \right) \etiqueta{4}}$$

Los valores para los más pequeños de $m$ e $n$ dado por la fórmula se

que comprobar en directo la computación.

Answer 3

La explicación anterior son demasiado complicadas para mí. Hice un error en el conteo así que aquí está cómo hacerlo y a partir de este diagrama algunos de generalización puede ser hecho. La imagen es una vista superior del cubo de 3X3X3. Las líneas diagonales son el corte de las intersecciones con los bordes de las capas de cubos de 3X3. El número representa los cubos que se cortan en cada capa - 1 para la capa inferior, 2 para la capa de en medio, y 3 para la capa superior.

Parte inferior (1) y superior (3) capas tienen 6 cubos de corte y el medio (2) de la capa 7 - un total de 19. No veo una manera de hacer 20.

Answer 4

El hexagonal de la sección transversal a mitad de camino entre la diagonal ooposite vértices tiene cara de longitud $n/\sqrt2$ y de área $(3\sqrt3/4)n^2$. Se corta un cubo cuando el cubo del centro de la ciudad dentro de $\sqrt3/2$ del avión. El volumen disponible es entonces $ (9/4)n^2$, por lo que el líder de número de la orden de cortar cubos podría ser $(9/4)n^2$.
Vamos a una normal al plano del ser $(a,b,c)$. Por simetría, podemos asumir que $a,b,c$ son todas positivas.
Cuando la sección transversal es un hexágono, el vector normal $(a,b,c)$ satisface el triángulo de las desigualdades $$a\lt b+c \\b\lt a+c \\c \lt a+b$$
Así que podemos escribir $a=u+v, b=u+w, c=v+w$ positivos $u,v,w$.
El área de la sección transversal de un dado normal es mayor cuando el plano pasa por el centro de la $n×n×n$ cubo.
El volumen disponible para el corte de cubos en los centros de
$$\left(\frac{(a+b+c)^3-2(a+b+c)(a^2+b^2+c^2)}{4abc}\right)n^2 \\ =\left(\frac{2(uv+uw+vw)(u+v+w)}{(u+v)(u+w)(v+w)}\right)n^2 \\ =\left(\frac94-\frac{u(v-w)^2+v(u-w)^2+w(u-v)^2}{4(u+v)(u+w)(v+w)}\right)n^2$$ Por lo que el volumen disponible es en la mayoría de las $9n^2/4$ cuando la sección transversal es un hexágono.

Answer 5

Digamos que el origen del sistema de coordenadas es el centro de la $n \times n \times n$ cubo.
También, cada cara del cubo es paralelo a cada uno de los ejes del sistema de coordenadas.
Deje que el avión $P$ recortes del cubo. ecuación de avión $P$ es
$$ P : ax+by+cz+d=0 \; \; (a \geq 0 , b\geq 0 , c \geq 0 , a^2+b^2+c^2=1)$$
(Porque es la misma cosa cuando se gira, $(a \geq 0 , b\geq 0 , c \geq 0)$)

Caso 1: $n$ es impar
el área de cada bloque de $B_{k m l}$ se da de la siguiente manera.
(Para tres enteros $k,m,l$ que satisfacer $|k|,|m|,|l| \leq \left [ \frac{n}{2} \right ] $) $$B_{k m l} := \left \{ (x,y,z) : |x-k| \leq 1/2 , |y-m| \leq 1/2 , |z-l| \leq 1/2 \right \}$$
En fina caso, Establezca $E_{k m l}$ , se compone de todos los vértices en el bloque $B_{k m l}$ se da de la siguiente manera
$$E_{k m l} := \left \{ (x,y,z) : x= k\pm1/2 , y=m\pm1/2 , z = l \pm 1/2 \right \} $$

Si el bloque de $B_{k m l}$ es cortado por el plano de $P$, algunos $ \mathbf{a},\mathbf{b} \in E_{k m l}$,$f(\mathbf{a})f(\mathbf{b})<0$ donde $f(x,y,z) := ax +by +cz+d$
Para $\mathbf{a} \in E_{k m l}$ , definir el valor mínimo de $f(\mathbf{a})$ como $\min(k,m,l)$ , y definir el valor máximo de $f(\mathbf{a})$ como $\max(k,m,l)$.
A continuación, $$ \min(k,m,l) = f(k,m,l) -\frac{1}{2}(a+b+c) \; , \; \max(k,m,l) = f(k,m,l) + \frac{1}{2}(a+b+c) $$
Por lo tanto, $ |f(k,m,l)| < \frac{1}{2}(a+b+c)$ es una condición necesaria y suficiente para el bloque $B_{k m l}$ a cortar por el plano de $P$.
Esta condición significa, punto de $(k,m,l)$ debe estar entre los planos de $P^{+} : ax+by+cz+d = \frac{1}{2}(a+b+c)$ e $P^{-} : ax+by+cz+d = -\frac{1}{2}(a+b+c)$.
Tenga en cuenta que La distancia entre los dos planos es $\sqrt{3}$.

Supongo que debe ser $d=0$ , Y creo que no será un valor apropiado de $(a,b,c)$ (sin importar el valor de $n$).
Lo siento, pero no conozco la forma específica para probar esto.