Golomba<\/a> – poniewa\u017c odleg\u0142o\u015b\u0107 mi\u0119dzy ka\u017cd\u0105 par\u0105 kresek (nie tylko kolejnych) jest inna. Optymalna\u00a0– poniewa\u017c najkr\u00f3tsza danego rz\u0119du. Nawiasem m\u00f3wi\u0105c, znane s\u0105 jeszcze cztery inne (niekt\u00f3re kreski w innych miejscach) OLGi 6. rz\u0119du, czyli o d\u0142ugo\u015bci 17.<\/p>\nPrzed rokiem „pad\u0142a” linijka 25. rz\u0119du\u00a0– po 8 latach eksploracji. Je\u015bli komputery nie przyspiesz\u0105, to nast\u0119pnych rz\u0119d\u00f3w nie doczekam. Prosz\u0119 wi\u0119c o zintensyfikowanie poszukiwa\u0144, abym m\u00f3g\u0142 na \u0142o\u017cu \u015bmierci pozna\u0107 t\u0119 z 28 kreskami, bo 28 to moja szcz\u0119\u015bliwa liczba \ud83d\ude42 . Pocieszaj\u0105ce jest to, \u017ce znamy nast\u0119pn\u0105 kandydatk\u0119. Wygl\u0105da tak:<\/p>\n
0_1_33_83_104_110_124_163_185_200_203_249_251_<\/strong><\/p>\n_258_314_318_343_356_386_430_440_456_464_475_<\/strong><\/p>\n487_492.<\/strong><\/p>\nTrzeba tylko sprawdzi\u0107, czy jaka\u015b kr\u00f3tsza ni\u017c si\u0119gaj\u0105ca do\u00a0492 si\u0119 przed ni\u0105 nie ukrywa.<\/p>\n
Po co te poszukiwania? To jest tak zwane dobre pytanie, po kt\u00f3rym prosi si\u0119 o nast\u0119pne. Z najkr\u00f3tszych OLG mo\u017cna wprawdzie wycisn\u0105\u0107 praktyczne zastosowania (urz\u0105dzenia oparte na tzw. technologii uk\u0142adu sfazowanego, anteny przeka\u017anikowe, badania krystalograficzne), ale z d\u0142u\u017cszych nie ma po\u017cytku, a pogo\u0144 za ekstremalnymi, to\u00a0– przynajmniej na razie\u00a0– „czyste szale\u0144stwo”. Mo\u017cna z nich natomiast spr\u00f3bowa\u0107 wycisn\u0105\u0107 zadania do g\u0142\u00f3wkowania. Spr\u00f3bowa\u0142em w formie konkursu w listopadowym \u015awiecie Nauki<\/em>. Konkurs dobieg\u0142 ko\u0144ca, wi\u0119c zadanie mo\u017ce trafi\u0107 do \u0141amiblogu, gwoli kontroli i ku rozerwaniu tych z Pa\u0144stwa, kt\u00f3rzy go z wersji papierowej nie znaj\u0105.<\/p>\nOptymaln\u0105 linijk\u0119 Golomba mo\u017cna zdefiniowa\u0107 jako ci\u0105g sko\u0144czony liczb ca\u0142kowitych, spe\u0142niaj\u0105cy podane wy\u017cej warunki. Wszystkie takie ci\u0105gi, je\u015bli sk\u0142adaj\u0105 si\u0119 z co najmniej pi\u0119ciu wyraz\u00f3w, czyli stanowi\u0105 OLG-i rz\u0119du wi\u0119kszego ni\u017c 4\u00a0– s\u0105 „wybrakowane” w tym sensie, \u017ce cho\u0107 to linijki – do mierzenia si\u0119 nie nadaj\u0105. Po prostu nie ma na nich niekt\u00f3rych odleg\u0142o\u015bci, czemu zreszt\u0105 trudno si\u0119 dziwi\u0107, bo liczba wszystkich mo\u017cliwych dystans\u00f3w mi\u0119dzy kreskami jest zawsze mniejsza ni\u017c d\u0142ugo\u015b\u0107 linijki Golomba.<\/p>\n
Oto jedyna znana OLG 9. rz\u0119du:<\/p>\n
0_1_5_12_25_27_35_41_44.<\/strong><\/p>\n\u0141atwo zauwa\u017cy\u0107, \u017ce brak na niej dystans\u00f3w: 18, 21, 28<\/strong>, 31, 33, 37, 38, 42.
\nZadanie polega na przekszta\u0142ceniu jej w narz\u0119dzie miernicze, czyli tak, aby wyst\u0119powa\u0142a na nim mi\u0119dzy kreskami ka\u017cda odleg\u0142o\u015b\u0107 mniejsza od d\u0142ugo\u015bci linijki d<\/strong>. Przekszta\u0142cenie powinno polega\u0107 wy\u0142\u0105cznie na zmianach po\u0142o\u017cenia niekt\u00f3rych kresek podzia\u0142ki. Inaczej m\u00f3wi\u0105c, z ci\u0105gu nale\u017cy usun\u0105\u0107 n<\/strong> liczb, a nast\u0119pnie doda\u0107 n<\/strong> innych liczb tak, aby:
\n–\u00a0zmian by\u0142o jak najmniej, czyli n<\/strong> = min.;
\n–\u00a0ci\u0105g nadal sk\u0142ada\u0142 si\u0119 z 9 wyraz\u00f3w\u00a0– od a1<\/sub><\/span><\/strong> = 0 do a9<\/sub><\/span><\/strong> = d<\/strong>;
\n–\u00a0w\u015br\u00f3d r\u00f3\u017cnic mi\u0119dzy dwoma dowolnymi wyrazami ci\u0105gu nie brakowa\u0142o \u017cadnej mniejszej od d<\/strong>;
\n–\u00a0ci\u0105g by\u0142 jak najd\u0142u\u017cszy, czyli a9<\/sub><\/span><\/strong> = max.
\nPo utworzeniu miarki zniknie oczywi\u015bcie optymalna linijka Golomba – zmieni si\u0119 (zmniejszy)\u00a0jej d\u0142ugo\u015b\u0107 d<\/strong>, a niekt\u00f3re odleg\u0142o\u015bci b\u0119d\u0105 si\u0119 powtarza\u0107.<\/p>\n","protected":false},"excerpt":{"rendered":"Od ponad roku trwaj\u0105 poszukiwania optymalnej linijki Golomba (OLG) 26. rz\u0119du. Uczestnicz\u0105 w nich tysi\u0105ce internaut\u00f3w, ofiarnie zatrudniaj\u0105cych swoje komputery w ramach tzw. projektu oblicze\u0144 rozproszonych. Czego szukaj\u0105? Czego\u015b mniej wi\u0119cej takiego, tylko znacznie d\u0142u\u017cszego: To jest OLG sz\u00f3stego rz\u0119du. Sz\u00f3stego\u00a0– poniewa\u017c jest na niej 6 kresek podzia\u0142ki. Golomba – poniewa\u017c odleg\u0142o\u015b\u0107 mi\u0119dzy ka\u017cd\u0105 par\u0105 […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/639"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=639"}],"version-history":[{"count":4,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/639\/revisions"}],"predecessor-version":[{"id":3855,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/639\/revisions\/3855"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=639"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=639"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=639"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"](\"\/wp-content\/uploads\/2009\/12\/olg_1.jpg\" "\\"olg_1\\"")
<\/a><\/p>\n