Consideremos primero el caso bidimensional para explicar los conceptos. Un segmento de línea de la longitud $L$ (Lo llamaré línea $L$ ) debe colocarse en una cuadrícula unitaria de tal manera que el número de celdas de la cuadrícula intersectadas se maximice. Las coordenadas de las celdas vienen dadas por sus esquinas inferiores izquierdas.
![Fig. 1]()
La figura muestra una línea de longitud 4,8 que comienza en la celda $(0, 0)$ y terminando en la celda $(4, 3)$ . El ángulo $\alpha$ entre esta línea y el eje x es $45^{\circ}$ . Podemos suponer sin pérdida de generalidad que la línea siempre comienza en la celda $(0, 0)$ y va hacia arriba y hacia la derecha de forma que $0 \le \alpha \le 45^{\circ}$ y termina en una celda $(X, Y)$ . Cuando movemos un punto $P$ a lo largo de la línea nos encontramos con los puntos de cruce con las celdas. Una celda sólo puede introducirse por su lado izquierdo (como $C_1$ ) o en su parte inferior (como $C_2$ ). Si se introduce una celda en su lado izquierdo, la página $x$ coordenada de cuadrícula de $P$ se incrementa en $1$ y el $y$ La coordenada de la cuadrícula no se modifica. Si se introduce una celda en su parte inferior la dirección $y$ coordenada de cuadrícula de $P$ se incrementa en $1$ y el $x$ La coordenada de la cuadrícula no cambia. Por lo tanto, en cada punto de entrada en una celda, exactamente una coordenada de cuadrícula de $P$ se incrementa por $1$ . Dado que el punto $P$ comienza en $(0, 0)$ y termina en $(X, Y)$ Hay exactamente $X + Y$ diferentes puntos de entrada, por lo que hay exactamente $X + Y$ celdas cruzadas (sin contar la celda inicial). En la figura tenemos $4 + 3 = 7$ células cruzadas. Dado que $X + Y \approx L \cos \alpha + L \sin\alpha$ el número máximo de células cruzadas se se alcanzará con $\alpha = 45^{\circ}$ .
Hay un caso degenerado cuando la línea entra en una celda por su esquina inferior esquina izquierda. En ese caso, ambas coordenadas de la cuadrícula aumentan, pero sólo se cruza una nueva celda se cruza. Como en este caso obtendríamos menos celdas cruzadas, evitamos este caso desplazando ligeramente la línea. Este siempre es posible porque los puntos inicial y final son números reales y hay hay a lo sumo un número finito de celdas consideradas.
Queda por encontrar $(X, Y)$ . Primero colocamos el punto de partida en el origen de coordenadas y dejamos que la línea pase por las esquinas de las celdas opuestas (paralelas a las diagonales de las celdas):
![Fig. 2]()
Si $L = n \sqrt 2 $ ( $n$ es un número entero) entonces la línea termina en una esquina de la celda $(n, n)$ . Ahora, se puede desplazar de manera que no pase por las esquinas y termine en la celda $(n, n)$ . El número máximo de celdas intersectadas (sin contar la celda inicial) es $n + n = 2n$ , donde $n = \lfloor L / \sqrt 2 \rfloor$ .
Si $L = n \sqrt 2 + r, 0 < r < \sqrt 2$ entonces la línea termina en la diagonal de la celda $(n, n)$ . Mover la línea a lo largo de $45^{\circ}$ hasta llegar a la siguiente celda y desplazándola, obtenemos la celda final $(n+1, n+1)$ . El número máximo de celdas intersectadas es $n+1 + n+1 = 2n + 2$ .
El caso tridimensional es análogo. Las celdas son ahora cubos unitarios, el segmento de línea es la varilla. Al movernos a lo largo de la varilla entramos en los cubos por una de las tres posibles caras y la coordenada correspondiente se incrementa. Por ejemplo, entrar en un cubo por su cara inferior aumenta la coordenada z en $1$ . El máximo número de cubos intersecados se consigue cuando la varilla se introduce por las esquinas opuestas de los cubos (a lo largo de las diagonales más largas) y luego se desplaza ligeramente para pasar por las caras. El máximo es X + Y + Z, donde (X, Y, Z) es el último cubo (sin contar el primer cubo).
Si $L = n \sqrt 3$ entonces la varilla termina en la esquina del cubo $(n, n, n)$ . Se puede desplazar de forma que termine en el cubo $(n, n, n)$ . El número máximo de cubos intersecados es $n + n + n = 3n$ .
Si $L = n \sqrt 3 + r, 0 < r < \sqrt 3$ entonces la varilla termina en la diagonal del cubo $(n, n, n)$ . Se puede desplazar de forma que termine en el cubo $(n+1, n+1, n+1)$ . El número máximo de cubos intersecados es ahora $n+1 + n+1 + n+1 = 3n + 3$ .
Resumamos:
$$L = \mbox{length of the rod}$$ $$n = \lfloor L / \sqrt 3 \rfloor$$ $$r = L - n \sqrt 3$$
$$ max = \begin{cases} 3n & \mbox{if} \;\; r = 0 \\ 3n + 3 & \mbox{if} \;\; r > 0 \;\; \end{cases} $$
