Usando un compás y una regla, ¿cuál es el camino más corto para dividir un segmento de línea en $n$ a partes iguales?

Question

A veces le ayudo a mi vecino de al lado de la hija con su tarea. Hoy en día ella tenía que trisect un segmento de línea usando un compás y una regla. Sin duda, yo tuve que buscar en la red, y me encontré con este útil sitio. Allí afirman que el menor número de "pasos" necesarios para trisect el segmento de es $4$, donde por un "paso" nos referimos a cualquier trazo de lápiz, ya sea con el compás y la regla.

De inmediato, esto me puso a pensar acerca de la duración de otros óptimo de las construcciones, lo que ha llevado a la pregunta de este post:

¿Cuál es el mínimo número de pasos necesarios para construir un segmento de longitud $\frac{1}{n}$ dado un segmento de longitud $1$?

Si $s(n)$ es la cantidad en cuestión, entonces, esta muy útiles sitio muestra que $s(n)\le n+6$. Sin embargo, $s(2)=3$$s(3)=4$, por lo que el obligado no es nítida. También, podemos ver que $s(mn)\le s(m)+s(n)$ mediante la creación de un segmento de longitud $\frac{1}{mn}$ a partir del uno de la longitud de la $\frac{1}{n}$.

Por último, en la parte inferior de la primer sitio, que hacen alusión a un método de construcción, que consiste en el dibujo de círculos cada vez más grandes. Suponiendo que su sugerencia conduce a una construcción óptima (que debería ser demostrado), creo que los primeros ocho valores de $s(n)$ a partir de con $n=1$ son:

$$0,3,4,5,5,5,5,6$$

Este no devuelve nada en OEIS. (Los números de arriba asumir que el segmento inicial de la longitud de la $1$ están marcadas en un muy largo ray, cosa que tendríamos que añadir uno para $n\ge3$ a alargar el segmento adecuadamente).

Alguna idea?

Answer 1

Vamos a iniciar segmento es $AB$. Como se puede ver en el primer enlace, a partir de la condición es "segmento-en-el-line". De todos modos uno puede agregar $1$ línea en el comienzo para llegar a esta condición de partida.

Considerar extraño $n$.

Deje que las coordenadas de los puntos de partida son: $A(-1,0)$, $B(0,0)$.

Si el punto de $C$ tiene coordenadas $C(n,0)$, (ver Figura 1) las coordenadas de otros puntos son: $D\left(\dfrac{1}{2n},\dfrac{\sqrt{4n^2-1}}{2n}\right)$; $\qquad$ $E(1,0)$; $\qquad$ $P\left(-1+\dfrac{1}{n},0\right)$.

Figura 1:

Considere la posibilidad de , incluso, $n$.

Deje que las coordenadas de los puntos de partida son: $A(0,0)$, $B(1,0)$.

Si el punto de $C$ tiene coordenadas $C\left(\dfrac{n}{2},0\right)$, (ver Figura 2) coordenadas de otros puntos son: $D\left(\dfrac{1}{n},\dfrac{\sqrt{n^2-1}}{n}\right)$; $\qquad$ $E\left(\dfrac{1}{n},-\dfrac{\sqrt{n^2-1}}{n}\right)$; $\qquad$ $P\left(\dfrac{1}{n},0\right)$.

Figura 2:

---

Idea principal: Para los que recibieron $m$ a dibujar punto de $C(m,0)$ tan rápido como sea posible.

Como he comprobado (a a $m=2048$), es posible dibujar el punto de $C(m,0)$, aplicando

$$ 1+\lfloor \log_2 m \rfloor $$

pasos, donde $\lfloor \cdot \rfloor$ es suelo de redondeo de la función.

De acuerdo a lo descrito construcción, el límite superior de (total) de los pasos es $$ 3+\lfloor \log_2 n \rfloor, \mbox{ si } n \mbox{ es impar} ; $$ $$ 2+\lfloor \log_2 n \rfloor, \mbox{ si } n \mbox{ es aún}. $$

Límites superiores de los pasos (a partir de la con $n=1$) son: $$ 0; ~~ 3, 4; ~~ 4, 5, 4, 5; ~~ 5,6,5,6,5,6,5,6; ~~ 6,7,6,7, ... $$

---

Ejemplos:

$n=11$: crear punto de $C(11,0)$ y siga la figura 1 (total $6$ pasos).

$n=12$: crear punto de $C(6,0)$ y siga en la figura 2 (total $5$ pasos).