Линейка Голомба

Линейка Голомба 4-го порядка длиной 6. Эта линейка оптимальна и совершенна.

Линейка Голомба в теории чисел — набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки нельзя найти два числа, разность между которыми повторялась бы дважды [1].

Названы в честь американского математика Соломона Голомба [2], хотя первые упоминания подобных конструкций встречаются в более ранних публикациях Сидона [en] [3] и Бэбкока [4].

Определения

Пример конференц-зала с перегородками на расстояниях пропорциональных делениям линейки Голомба [0, 2, 7, 8, 11], что позволяет получить залы 10 различных размеров.

Число делений на линейке Голомба называют её порядком, а наибольшее расстояние между двумя её делениями — длиной. Например, линейка с делениями 0 1 4 9 11 является линейкой пятого порядка длины 11. Иногда линейки Голомба описываются расстояниями между соседними делениями, а не абсолютными координатами делений, поэтому приведённая выше линейка будет выглядеть как 1-3-5-2. Максимальное число пар, которые можно составить из делений линейки порядка n, равно числу сочетаний .

Линейки, полученные из данной путём сдвига каждого деления на фиксированное число — например, 1 2 5 10 12, — или перечислением делений линейки в обратном порядке (зеркально-отражённые) — например, 0 2 7 10 11, — считаются эквивалентными. Поэтому в каноническом представлении линейки Голомба наименьшее деление соответствует нулевой координате, а следующее за ним деление располагается на наименьшем из двух возможных расстояний.

Линейка Голомба не всегда пригодна для измерения всех целочисленных расстояний в пределах её длины, однако если пригодна, то такую линейку называют совершенной (Perfect Golomb Ruler (англ.), PGR). Совершенные линейки существуют только для порядков, меньших пяти.

Линейку Голомба называют оптимальной (Optimal Golomb Ruler (англ.), OGR), если не существует более коротких линеек того же порядка. Другими словами, линейка является оптимальной, если в каноническом представлении значение её последнего деления минимально возможное.

Создать линейку Голомба относительно просто, но вот доказательство оптимальности линейки является трудоёмким вычислительным процессом. В настоящее время способ получения оптимальной линейки Голомба произвольной длины n неизвестен, однако полагают, что эта задача является NP-трудной.

другие языки
Deutsch: Golomb-Lineal
English: Golomb ruler
español: Regla de Golomb
français: Règle de Golomb
日本語: ゴロム定規
Nederlands: Golomb-liniaal
српски / srpski: Голомбов лењир
svenska: Golomblinjal
Tiếng Việt: Thước Golomb