ゴロム定規

想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺とも。
ソロモン・ゴロム（Solomon Wolf Golomb）が名前の由来。
マーク数を「次数」、2つのマーク間の距離のうち最大の距離を「長さ」という。
ゴロム定規の概念はそれほど難しいものではなく、一般に最小のマークを 0 として一方の端に置き、その次のマークは2つの位置があり得る場合は小さい方に置く。
ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全ゴロム定規」という。
5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている。
また、同一次数（マーク数）で最短のゴロム定規を「最短ゴロム定規」という。
ゴロム定規を作るのは簡単だが、特定次数の最短ゴロム定規を見つけるのは計算上大変な作業となる。
今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難問題だと考えられている。

最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。

既知の最短ゴロム定規を表にしたものは以下の通り（但し、対称型（マークの配置が表にあるものと逆のもの）は省く）。
次数：長さ：(マークの位置)
1：0：(0)
2：1：(0,1)
3：3：(0,1,3)
4：6：(0,1,4,6)
5：11：(0,1,4,9,11),(0,2,7,8,11)
6：17：(0,1,4,10,12,17),(0,1,4,10,15,17),(0,1,8,11,13,17),(0,1,8,12,14,17)
7：25：(0,1,4,10,18,23,25),(0,1,7,11,20,23,25),(0,1,11,16,19,23,25),(0,2,3,10,16,21,25),(0,2,7,13,21,22,25)
8：34：(0,1,4,9,15,22,32,34)
9：44：(0,1,5,12,25,27,35,41,44)
10：55：(0,1,6,10,23,26,34,41,53,55)
11：72：(0,1,4,13,28,33,47,54,64,70,72),(0,1,9,19,24,31,52,56,58,69,72)
12：85：(0,2,6,24,29,40,43,55,68,75,76,85)
13：106：(0,2,5,25,37,43,59,70,85,89,98,99,106)
14：127：(0,4,6,20,35,52,59,77,78,86,89,99,122,127)
15：151：(0,4,20,30,57,59,62,76,100,111,123,136,144,145,151)
16：177：(0,1,4,11,26,32,56,68,76,115,117,134,150,163,168,177)
17：199：(0,5,7,17,52,56,67,80,81,100,122,138,159,165,168,191,199)
18：216：(0,2,10,22,53,56,82,83,89,98,130,148,153,167,188,192,205,216)
19：246：(0,1,6,25,32,72,100,108,120,130,153,169,187,190,204,231,233,242,246)
20：283：(0,1,8,11,68,77,94,116,121,156,158,179,194,208,212,228,240,253,259,283)
21：333：(0,2,24,56,77,82,83,95,129,144,179,186,195,255,265,285,293,296,310,329,333)
22：356：(0,1,9,14,43,70,106,122,124,128,159,179,204,223,253,263,270,291,330,341,353,356)
23：372：(0,3,7,17,61,66,91,99,114,159,171,199,200,226,235,246,277,316,329,348,350,366,372)
24：425：(0,9,33,37,38,97,122,129,140,142,152,191,205,208,252,278,286,326,332,353,368,384,403,425)
25：480：(0,12,29,39,72,91,146,157,160,161,166,191,207,214,258,290,316,354,372,394,396,431,459,467,480)
26：492：(0,1,33,83,104,110,124,163,185,200,203,249,251,258,314,318,343,356,386,430,440,456,464,475,487,492)

※　画像は次数 3 長さ 3 のゴロム定規と、次数 4 長さ 6 のゴロム定規。ともに最短で完全である。

ttp://ja.wikipedia.org/wiki/%E3%82%B4%E3%83%AD%E3%83%A0%E5%AE%9A%E8%A6%8F
ttp://en.wikipedia.org/wiki/Golomb_ruler
ttp://mathworld.wolfram.com/GolombRuler.html

参照（過去の日記）：NP困難とNP完全
ttp://mixi.jp/view_diary.pl?id=666798284&owner_id=14882521