Совершенные и оптимальные линейки
Краткое введение.

На линейках, которые мы можем купить в обычном магазине, мы видим следующую последовательность меток:

'-'-'-'-'-'-'

Достаточно однообразно и скучно. Однако недавно производители линеек обнаружили, что они могут сократить издержки производства, не снижая качество выполняемых линейкой функций. Например, с помощью линейки 

'-'---'--'

можно отмерить столько расстояний, сколько и с обычной линейкой такой же длины. 

Сколько же меток можно удалить, не ограничивая при этом возможность измерить все расстояния определенной длины? Именно этот вопрос будет здесь рассмотрен; вопрос, который превращает скучную линейку в интересный предмет для комбинаторики.

Во-первых, мы должны убедиться в том, что с помощью линейки мы сможем отмерить все расстояния одинаковые или короче, чем длина линейки. Достаточно очевидно, что это непременное условие разумной линейки. 

Линейку, обладающую этим свойством, мы назовем «полной», так как у неё достаточно отметок для выполнения этой элементарной задачи. Линейки, на это неспособные («неполные»), здесь рассматриваться не будут.

После этого мы обратим наше внимание на те полные линейки, у которых как можно меньше отметок. Их мы назовём «совершенными» линейками. Это полные линейки, у которых удаление одной единственной отметки сделало бы их неполными. С полными линейками связаны определённые эстетические представления, так как они достигают результата менее сложным путём.

Интересно отметить, что даже среди совершенных линеек с одинаковым количеством меток есть различия. Рассмотрим три совершенные линейки. У каждой из них 4 метки. (Цифры указывают порядок разметки на линейке).

[0, 1, 3, 4], [0, 1, 3, 5], [0, 1, 4, 6]

Третьей линейкой можно отмерить на 33% больше расстояний, чем первой. И при необходимости вы бы несомненно купили третью линейку.

Однако отличительной чертой третьей линейки является то, что не существует линейки с 4 метками, с помощью которой можно измерить большие расстояния. 

Таким образом, метки охватывают максимальный диапазон для измерения. Линейки, обладающие этим качеством, называются «оптимальными». Они соединяют в себе эстетику минимальной сложности с максимумом пользы.

Линейки, обладающие этим свойством, встречаются довольно таки редко. В качестве примера можно взять совершенные линейки с 14 метками. Их существует 52912, но лишь 4 из них являются оптимальными. Нашей основной задачей станет вычисление полных, совершенных и оптимальных линеек.

Оптимальные линейки, существующие для каждого числа меток, всегда определенной длины. В зависимости от количества меток, их длина будет равна:

0, 1, 3, 6, 9, 13, 17, 23, ...

Эти же числа выражают максимальное число границ в простой графе на n-узлах, связывая, таким образом, изучение совершенных линеек с теорией граф, комбинаторикой и теорией чисел.

Естественно, нас интересует знание построения подобных оптимальных линеек. На первый взгляд, это кажется нелёгким заданием.

Но существует захватывающая, ещё не доказанная гипотеза, что есть план, который обеспечил бы простое построение оптимальных линеек. В ней говорится, что линейка с более чем 14 метками, оптимальна только в том случае, если она является «линейкой Вихманна», названной в честь Б. Вихманна, который представил ее в 1962 в своей заметке «A note on restricted difference bases».

О линейки в двух словах

Линейка - это строгая конечная возрастающая последовательность меток, которым соответствуют неотрицательные числа. За первую отметку, условно, берётся 0. 

Линейки определяются длиной и количеством отрезков S (отрезок - расстояние между двумя соседними метками). Линейка с М метками имеет S=M-1 отрезков. 

Линейки бывают: 

  • Полными, если этой линейкой можно измерить все расстояния d при 1<=d<=L.
     
  • Совершенными,  если не существует полной линейки той же длины, но с меньшим количеством меток.
     
  • Оптимальными,  если не существует полной линейки с одинаковым количеством меток, но большей длины.
home