Regla escasa

---

Una regla dispersa es una regla en la que pueden faltar algunas de las marcas de distancia. De manera más abstracta, una regla escasa de longitud con marcas es una secuencia de números enteros donde . Las marcas y corresponden a los extremos de la regla. Para medir la distancia , debe haber marcas y tal .${\ Displaystyle L}$${\ Displaystyle m}$${\ Displaystyle a_ {1}, a_ {2}, ..., a_ {m}}$${\ Displaystyle 0 = a_ {1} <a_ {2} <... <a_ {m} = L}$${\ Displaystyle a_ {1}}$${\displaystyle a_{m}}$${\displaystyle K}$${\displaystyle 0\leq K\leq L}$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle a_{j}-a_{i}=K}$

Una regla dispersa completa le permite medir cualquier distancia entera hasta su longitud total. Una regla dispersa completa se llama mínima si no hay una regla dispersa completa de longitud con marcas. En otras palabras, si se elimina alguna de las marcas, ya no se pueden medir todas las distancias, incluso si las marcas pudieran reorganizarse. Una regla dispersa completa se llama máxima si no hay una regla dispersa completa de longitud con marcas. Una regla dispersa se llama óptima si es mínima y máxima.${\displaystyle L}$${\displaystyle m-1}$${\displaystyle L+1}$${\displaystyle m}$

Dado que el número de pares distintos de marcas es , este es un límite superior en la longitud de cualquier regla dispersa máxima con marcas. Este límite superior solo se puede lograr con 2, 3 o 4 puntos. Para un mayor número de marcas, la diferencia entre la longitud óptima y el límite aumenta de forma gradual y desigual.${\displaystyle m(m-1)/2}$${\displaystyle L}$${\displaystyle m}$

Por ejemplo, para 6 marcas, el límite superior es 15, pero la longitud máxima es 13. Hay 3 configuraciones diferentes de reglas dispersas de 13 con 6 marcas. Uno es {0, 1, 2, 6, 10, 13}. Para medir una longitud de 7, digamos, con esta regla tomaría la distancia entre las marcas en 6 y 13.

Una regla de Golomb es una regla dispersa que requiere que todas las diferencias sean distintas. En general, una regla de Golomb con marcas será considerablemente más larga que una regla dispersa óptima con marcas, ya que es un límite inferior para la longitud de una regla de Golomb. Una regla de Golomb larga tendrá espacios, es decir, tendrá distancias que no podrá medir. Por ejemplo, la regla de Golomb óptima {0, 1, 4, 10, 12, 17} tiene una longitud de 17, pero no puede medir longitudes de 14 o 15.${\displaystyle a_{j}-a_{i}}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m(m-1)/2}$

---