Rzadki władca

Rzadka linijka to linijka, w której może brakować niektórych znaczników odległości. $jest$ bardziej abstrakcyjnie, rzadka linijka o długości $.$ znakami ciągiem liczb $a_ {1}, a_ {2}, ..., a_ {m}}$ gdzie ${\ Displaystyle 0 = a_ {1}<a_ {2}<... <a_ {m} = L}$ . Znaki i za $\$ $}$ odpowiadają końcom linijki. Aby $zmierzyć$ $,$ przy istnieć i $za$ $_ {j}}$ takie, że $\ Displaystyle a_ {j} -a_ {i} = K}$ .

Kompletna rzadka linijka pozwala mierzyć dowolną odległość całkowitą aż do jej pełnej długości . Kompletna rzadka linijka nazywana jest $znakami$ jeśli $nie$ ma kompletnej rzadkiej linijki o ze Innymi słowy, jeśli którykolwiek ze znaków zostanie usunięty, nie można już zmierzyć wszystkich odległości, nawet jeśli można by zmienić kolejność znaków. Całkowitą rzadką linijkę nazywamy maksymalną , jeśli nie ma kompletnej linijki rzadkiej o długości ${\ Displaystyle L + 1}$ ze znakami ${\ displaystyle m}$ . Rzadką linijkę nazywamy optymalną , jeśli jest zarówno minimalna, jak i maksymalna.

$,$ liczba różnych par znaków wynosi górna granica długości dowolnej maksymalnej rzadkiej linijki $L$ ${\ displaystyle m}$ . Ta górna granica może być osiągnięta tylko za 2, 3 lub 4 oceny. Przy większej liczbie znaków różnica między optymalną długością a wiązaniem rośnie stopniowo i nierównomiernie.

Na przykład dla 6 znaków górna granica wynosi 15, ale maksymalna długość to 13. Istnieją 3 różne konfiguracje rzadkich linijek o długości 13 z 6 znakami. Jeden to {0, 1, 2, 6, 10, 13}. Aby zmierzyć długość, powiedzmy, 7, za pomocą tej linijki należy zmierzyć odległość między znakami na 6 i 13.

Władca Golomba $, aby$ różnice różne. Ogólnie rzecz biorąc, linijka Golomba ze ${\ Displaystyle m (m-1) /2}$ $będzie$ dłuższa niż optymalna rzadka linijka ze $znakami$ , ponieważ jest dolną granicą długości linijki Golomba. Długi linijka Golomba będzie miał luki, to znaczy będzie miał odległości, których nie może zmierzyć. Na przykład optymalna linijka Golomba {0, 1, 4, 10, 12, 17} ma długość 17, ale nie może mierzyć długości 14 lub 15.

władców Wichmanna

Wiele optymalnych linijek ma postać
${\ Displaystyle W (r, s) = 1 ^ {r}, r + 1, (2r + 1) ^ {r}, (4r + 3) ^ {s}, (2r + 2) ^ {(r + 1)}, 1 ^ {r},}$ gdzie ${\ displaystyle a ^ {b}}$ $reprezentuje$ segmenty o długości za $}$ . Tak więc, jeśli i $\ Displaystyle$ $s = 2}$ , to ma w kolejności): segment $\ Displaystyle W (1,2)}$ o długości 1,

1 odcinek o długości 2, 1 odcinek o długości 3, 2 segmenty o długości 7, 2 segmenty o długości 4, 1 odcinek o długości 1

To daje linijce {0, 1, 3, 6, 13, 20, 24, 28, 29}. Długość linijki Wichmanna wynosi ${\ Displaystyle 4r (r + s + 2) + 3 (s + 1)},$ a liczba znaków to ${\ Displaystyle 4r + s + 3}$ . Należy zauważyć, że nie wszystkie linijki Wichmanna są optymalne i nie wszystkie linijki optymalne można wygenerować w ten sposób. Żadna z optymalnych linijek o długości 1, 13, 17, 23 i 58 nie jest zgodna z tym wzorem. Ta sekwencja kończy się na 58, jeśli Optymalna hipoteza władcy Petera Luschnego jest poprawna. Wiadomo, że przypuszczenie jest prawdziwe dla długości 213.

asymptotyczne

Dla każdego $będzie$ najmniejszą $n$ znaków dla linijki o długości $}$ n Na przykład ${\ displaystyle l (6) = 4}$ . Asymptotyka funkcji $Erdosa ,$ który udowodnił, że granica
${\ Displaystyle \ lim _ {n \ do \ infty} {l (n) ^ {2}} / n}$ istnieje i jest dolny i górny ograniczony przez ${\ Displaystyle 2 + {\ tfrac {4} {3 \ pi}} = 2,424 ... <2,434 ... = \ max _ {0 <\ teta <2 \ pi }2(1-{\tfrac {\sin(\theta )}{\theta }})\leq \lim _{n\to \infty}{\frac {l(n)^{2}}{n }}\leq {\frac {375}{112}}=3,348...}$

$Istnieją$ znacznie lepsze górne granice dla władców. Są to podzbiory $zapisać$ , że każdą liczbę dodatnią można jako różnicę $\ równoważnik n}$ ${\ Displaystyle$ ${\ displaystyle k = ab}$ dla niektórych ${\ Displaystyle a, b \ w A}$ . Dla każdej liczby ${\ displaystyle n}$ niech ${\ displaystyle k (n)}$ będzie najmniejszą licznością ${\ displaystyle n}$ -doskonałej linijki. Jest oczywiste, że ${\ Displaystyle k (n) \ równoważnik l (n)}$ . Asymptotyka ciągu ${\ Displaystyle k (n)}$
badali Redei, Renyi (1949), a następnie Leech (1956) i Golay (1972). Dzięki ich staraniom uzyskano następujące granice górne i dolne: ${\ Displaystyle \ max _ {0 <\ theta <2 \ pi} 2 (1- {\ tfrac {\ sin (\ theta)} {\ theta}}} \ równoważnik \ lim _ {n \ do \ infty}} \frac {k(n)^{2}}{n}}=\inf _{n\in \mathbb {N}}}{\frac {k(n)^{2}}{n}}\leq { \frac {128^{2}}{6166}}=2,6571...<{\frac {8}{3}}.}$

mi ${\ Displaystyle E (n) = l (n) - \ lceil {\ sqrt {3n + {\ tfrac {9}$ . W 2020 roku Pegg udowodnił na podstawie konstrukcji, że ${\ displaystyle E (n)}$ ≤ 1 dla wszystkich długości ${\ displaystyle n}$ . Jeśli hipoteza optymalnego władcy jest prawdziwa, to ${\ Displaystyle E (n) = 0 | 1}$ $dla$ wszystkich co prowadzi do wzoru „ciemnych młynów” po ułożeniu w kolumny, OEIS A326499. Żadna z najbardziej znanych rzadkich linijek nie $> 213$ minimalna od września 2020 r. Wiele z obecnie najbardziej znanych $} >213}$ $\$ > uważa się za nieminimalne, zwłaszcza wartości „chmury”.

Ryc. 1. Jasne cyfry +0, ciemne cyfry +1 dla wzoru minimalnego nadmiaru znaku w rzadkiej linijce. Wszystkie wartości minimalne do długości 213 są udowodnione.
Ryc. 2. „Ciemne młyny w pochmurny dzień” — NJA Sloane. Wzór nadmiaru dla rzadkich linijek, najbardziej znane wartości dla L>213.

Przykłady

Poniżej przedstawiono przykłady minimalnych rzadkich linijek. Optymalne linijki są podświetlone. Gdy jest ich zbyt wiele, aby je wymienić, nie wszystkie są uwzględnione. Odbicia lustrzane nie są wyświetlane.

Długość	Znaki	Numer	Przykłady	Formularz listy	Wichmanna
1	2	1	II	{0, 1}
2	3	1	III	{0, 1, 2}
3	3	1	II.I	{0, 1, 3}	W(0,0)
4	4	2	III.I II.II	{0, 1, 2, 4} {0, 1, 3, 4}
5	4	2	III..I II.II	{0, 1, 2, 5} {0, 1, 3, 5}
6	4	1	II..II	{0, 1, 4, 6}	W(0,1)
7	5	6	IIII...I III.I..I III..II II.III II.I..II II..II.I	{0, 1, 2, 3, 7} {0, 1, 2, 4, 7} {0, 1, 2, 5, 7} {0, 1, 3, 5, 7} {0, 1, 3 , 6, 7} {0, 1, 4, 5, 7}
8	5	4	III..I..I II.I...II II..III II...II.I	{0, 1, 2, 5, 8} {0, 1, 3, 7, 8} {0, 1, 4, 6, 8} {0, 1, 5, 6, 8}
9	5	2	III...I..I II..I..II	{0, 1, 2, 6, 9} {0, 1, 4, 7, 9}	- W(0,2)
10	6	19	III..I...I	{0, 1, 2, 3, 6, 10}
11	6	15	III...I...I	{0, 1, 2, 3, 7, 11}
12	6	7	IIII....I...I III...I..I..I II.II....II II.I...I...II II..II....II II ..I.I..II II.....II.II	{0, 1, 2, 3, 8, 12} {0, 1, 2, 6, 9, 12} {0, 1, 3, 5, 11, 12} {0, 1, 3, 7, 11, 12} {0, 1, 4, 5, 10, 12} {0, 1, 4, 7, 10, 12} {0, 1, 7, 8, 10, 12}	- - - - - W(0,3) -
13	6	3	III...I...I..I II..II.....II II....I..III	{0, 1, 2, 6, 10, 13} {0, 1, 4, 5, 11, 13} {0, 1, 6, 9, 11, 13}
14	7	65	IIIIII....I....I	{0, 1, 2, 3, 4, 9, 14}
15	7	40	II.I..I...I...II II..I..I..I..II	{0, 1, 3, 6, 10, 14, 15} {0, 1, 4, 7, 10, 13, 15}	Z(1,0) Z(0,4)
16	7	16	III....I...I...I	{0, 1, 2, 3, 8, 12, 16}
17	7	6	IIII....I....I...I III...I...I...I..I III.....I...II.I III..... I...I..II II..I.....II.II II......I..IIII	{0, 1, 2, 3, 8, 13, 17} {0, 1, 2, 6, 10, 14, 17} {0, 1, 2, 8, 12, 14, 17} {0, 1, 2, 8, 12, 15, 17} {0, 1, 4, 10, 12, 15, 17} {0, 1, 8, 11, 13, 15, 17}
18	8	250	II..I..I..I.I..II	{0, 1, 4, 7, 10, 13, 16, 18}	W(0,5)
19	8	163	IIIIII....I...I....I	{0, 1, 2, 3, 4, 9, 14, 19}
20	8	75	IIIII.....I....I....I	{0, 1, 2, 3, 4, 10, 15, 20}
21	8	33	IIIII.....I.....I....I	{0, 1, 2, 3, 4, 10, 16, 21}
22	8	9	IIII....I....I....I...I III.......I....I..I..II II.II....... II.....II II.I..I......I...I...II II.I.....I.....I...II.I II ..II......II....II II....II..I.......III II....I..I......IIII II. ....II........II.II	{0, 1, 2, 3, 8, 13, 18, 22} {0, 1, 2, 10, 15, 18, 21, 22} {0, 1, 3, 5, 14, 15, 21, 22 } {0, 1, 3, 6, 13, 17, 21, 22} {0, 1, 3, 9, 15, 19, 20, 22} {0, 1, 4, 5, 12, 14, 20, 22} {0, 1, 6, 7, 10, 18, 20, 22} {0, 1, 6, 9, 16, 18, 20, 22} {0, 1, 7, 8, 17, 18, 20 , 22}	- - - W(1,1) - - - - -
23	8	2	III........I...I..I..II II..I.....I.....II.II	{0, 1, 2, 11, 15, 18, 21, 23} {0, 1, 4, 10, 16, 18, 21, 23}
24	9	472	IIIIII......I.....I.....I	{0, 1, 2, 3, 4, 5, 12, 18, 24}
25	9	230	IIIIII......I......I.....I	{0, 1, 2, 3, 4, 5, 12, 19, 25}
26	9	83	IIIII.....I....I....I....I	{0, 1, 2, 3, 4, 10, 15, 21, 26}
27	9	28	IIIII.....I.....I.....I....I	{0, 1, 2, 3, 4, 10, 16, 22, 27}
28	9	6	III..........I....I..I..I..II II.III..........II.......II II.I ..I..I......I.......I...II II.I.......I..I.......I...II. I II.....I...I.......I..I.II.I II.......II..........II.III	{0, 1, 2, 13, 18, 21, 24, 27, 28} {0, 1, 3, 5, 7, 18, 19, 27, 28} {0, 1, 3, 6, 9, 16 , 23, 27, 28} {0, 1, 3, 9, 15, 21, 25, 26, 28} {0, 1, 7, 11, 20, 23, 25, 26, 28} {0, 1, 9, 10, 21, 22, 24, 26, 28}
29	9	3	III...........I...I..I..I..II II.I..I......I......I...I ...II II..I.....I.....I.....II.II	{0, 1, 2, 14, 18, 21, 24, 27, 29} { 0, 1, 3, 6, 13, 20, 24, 28, 29} {0, 1, 4, 10, 16, 22 , 24, 27, 29}	- W(1,2) -
35	10	5	III..............I...I..I..I..II..II II.I..I..I......I.. ....I......I...II II.I..I..I..........I...I......I...II II..II..........II.....II....II II..I.......I.....I.....I.. ...II.II	{0, 1, 2, 17, 21, 24, 27, 30, 33, 35} { 0, 1, 3, 6, 9, 16, 23, 30, 34, 35} {0, 1, 3, 6 , 9, 19, 23, 30, 34, 35} {0, 1, 4, 5, 16, 18, 25, 27, 33, 35} {0, 1, 4, 10, 16, 22, 28, 30 , 33, 35}
36	10	1	II.I..I......I.......I..I..I...II	{0, 1, 3, 6, 13, 20, 27, 31, 35, 36}	W(1,3)
43	11	1	II.I..I......I.......I..I.......I..I...II	{0, 1, 3, 6, 13, 20, 27, 34, 38, 42, 43}	W(1,4)
46	12	342	III..I....I..I..........I..I..I.......I.......III	{0, 1, 2, 5, 10, 15, 26, 32, 38, 44, 45, 46}	W(2,1)
50	12	2	IIII..............I....I...I...I...I...I..I..I II. ja... ja...... ja... ja... ja... ja... ja... ja... II	{0, 1, 2, 3, 23, 28, 32, 36, 40, 44, 47, 50} {0, 1, 3, 6, 13, 20, 27, 34, 41, 45, 49, 50}	- W(1,5)
57	13	12	III..I...Ja..I..........I..........I..I.......I..I.. ...III II.I..I......I.......I.......I.......I..I.......I....... .I...I...II	{0, 1, 2, 5, 10, 15, 26, 37, 43, 49, 55, 56, 57} {0, 1, 3, 6, 13, 20, 27, 34, 41, 48, 52 , 56, 57}	Z(2,2) Z(1,6)
58	13	6	IIII............................I....Ja...Ja...Ja...Ja...Ja...I ..I..I III...II.......I........I........I.......I..I. .....I..II III.....I.......II..........I.......I....... ..I..I...II.I II.I..I..........I..I.......I.......I... ......Ja...Ja...Ja...II II.I..I..........I......I..I... ......Ja...Ja...Ja...II II... I..I...I.......Ja... .....I.......I.......I....II.II	{0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58} {0, 1, 2, 6, 8, 17, 26, 35, 44, 47, 54 , 57, 58} {0, 1, 2, 8, 15, 16, 26, 36, 46, 49, 53, 55, 58} {0, 1, 3, 6, 17, 20, 27, 35, 45 , 49, 53, 57, 58} {0, 1, 3, 6, 17, 24, 27, 38, 45, 49, 53, 57, 58} {0, 1, 5, 8, 12, 21, 30, 39, 48, 53, 54, 56, 58}
68	14	2	III..I...Ja..I..........I..........I..........Ja... ..I.....I.....III III.....I.......II..........I..........I. ........I.........I..I...II.I	{0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68} {0, 1, 2, 8, 15, 16, 26, 36, 46, 56 , 59, 63, 65, 68}	W(2,3) -
79	15	1	III..I...Ja..I..........I..........I..........Ja... .......I.....I.....I.....III	{0, 1, 2, 5, 10, 15, 26, 37, 48, 59, 65, 71, 77, 78, 79}	W(2,4)
90	16	1	III..I...Ja..I..........I..........I..........Ja... .......I..........I.....I.....I.....III	{0, 1, 2, 5, 10, 15, 26, 37, 48, 59, 70, 76, 82, 88, 89, 90}	W(2,5)
101	17	1	III..I...Ja..I..........I..........I..........Ja... .......Ja..........Ja............I.......I.......I.....III	{0,1,2,5,10,15,26,37,48,59,70,81,87,93,99,100,101}	W(2,6)
112	18	1	III..I...Ja..I..........I..........I..........Ja... .......Ja............Ja..........Ja..........Ja.....Ja... ...I.....III	{0,1,2,5,10,15,26,37,48,59,70,81,92,98,104,110,111,112}	W(2,7)
123	19	2	IIII...I......I.......Ja.......Ja.............I.......... .....Ja..............Ja..............Ja.......Ja...... .I.......I.......IIII III..I...Ja..I..........I..........I..........Ja... .......Ja..........Ja..........Ja..........Ja.......... .I.....I.....I.....III	{0,1,2,3,7,14,21,28,43,58,73,88,96,104,112,120,121,122,123} {0,1,2,5,10,15,26,37,48,59,70, 81,92,103,109,115,121,122,123}	Z(3,4) Z(2,8)
138	20	1	IIII...I......I.......Ja.......Ja.............I.......... .....Ja..............Ja..............Ja............ Ja.......I.......I.......I.......IIII	{0,1,2,3,7,14,21,28,43,58,73,88,103,111,119,127,135,136,137,138}	W(3,5)

Niekompletne rzadkie linijki

Kilka niekompletnych linijek może w pełni zmierzyć większą odległość niż optymalna rzadka linijka z taką samą liczbą znaków. ${\ Displaystyle \ {0,2,7,14,15,18,24 \}}$ , ${\ Displaystyle \ {0,2,7,13,16,17,25 \}}$ , ${\ Displaystyle \ {0,5,7,13,16,17,31 \}}$ i ${\ Displaystyle \{0,6,10,15,17,18,31\}}$ każda może mierzyć do 18, podczas gdy optymalna rzadka linijka z 7 znakami może mierzyć tylko do 17. Poniższa tabela zawiera listę tych linijek, aż do linijek z 13 znakami. Odbicia lustrzane nie są wyświetlane. Podświetlone są linijki, które mogą w pełni mierzyć do większej odległości niż jakakolwiek krótsza linijka z taką samą liczbą znaków.

Znaki	Długość	Środki do	Linijka
7	24	18	{0, 2, 7, 14, 15, 18, 24}
7	25	18	{0, 2, 7, 13, 16, 17, 25}
7	31	18	{0, 5, 7, 13, 16, 17, 31}
7	31	18	{0, 6, 10, 15, 17, 18, 31}
8	39	24	{0, 8, 15, 17, 20, 21, 31, 39}
10	64	37	{0, 7, 22, 27, 28, 31, 39, 41, 57, 64}
10	73	37	{0, 16, 17, 28, 36, 42, 46, 49, 51, 73}
11	68	44	{0, 7, 10, 27, 29, 38, 42, 43, 44, 50, 68}
11	91	45	{0, 18, 19, 22, 31, 42, 48, 56, 58, 63, 91}
12	53	51	{0, 2, 3, 6, 9, 17, 25, 33, 41, 46, 51, 53}
12	60	51	{0, 5, 9, 13, 19, 26, 33, 48, 49, 50, 51, 60}
12	73	51	{0, 2, 3, 10, 17, 23, 35, 42, 46, 47, 51, 73}
12	75	51	{0, 2, 10, 13, 29, 33, 36, 45, 50, 51, 57, 75}
12	82	51	{0, 8, 28, 31, 34, 38, 45, 47, 49, 50, 74, 82}
12	83	51	{0, 2, 10, 24, 25, 29, 36, 42, 45, 73, 75, 83}
12	85	51	{0, 8, 10, 19, 35, 41, 42, 47, 55, 56, 59, 85}
12	87	51	{0, 12, 24, 26, 37, 39, 42, 43, 46, 47, 75, 87}
13	61	59	{0, 2, 3, 6, 9, 17, 25, 33, 41, 49, 54, 59, 61}
13	69	59	{0, 6, 10, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
13	69	59	{0, 6, 11, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
13	82	59	{0, 4, 5, 9, 25, 27, 39, 42, 50, 53, 56, 63, 82}
13	83	59	{0, 1, 2, 24, 34, 36, 38, 43, 51, 54, 57, 82, 83}
13	88	59	{0, 1, 3, 9, 16, 26, 36, 40, 47, 54, 58, 59, 88}
13	88	59	{0, 1, 5, 29, 34, 36, 47, 48, 50, 56, 58, 73, 88}
13	90	59	{0, 7, 12, 16, 37, 38, 43, 55, 56, 57, 58, 66, 90}
13	91	59	{0, 5, 9, 12, 16, 32, 38, 42, 55, 56, 57, 63, 91}
13	92	59	{0, 6, 10, 13, 25, 34, 39, 54, 55, 56, 57, 65, 92}
13	94	59	{0, 1, 3, 16, 28, 37, 45, 48, 54, 55, 59, 78, 94}
13	95	59	{0, 4, 32, 37, 38, 40, 48, 53, 54, 56, 63, 83, 95}
13	96	59	{0, 3, 7, 27, 37, 39, 50, 55, 56, 58, 72, 81, 96}
13	101	59	{0, 4, 24, 37, 43, 45, 52, 54, 55, 59, 77, 81, 101}
13	108	59	{0, 8, 17, 40, 50, 53, 64, 65, 69, 71, 91, 99, 108}
13	113	61	{0, 6, 22, 36, 45, 47, 57, 60, 64, 65, 91, 97, 113}
13	133	60	{0, 26, 29, 40, 42, 46, 67, 74, 79, 89, 97, 98, 133}

Zobacz też