{"id":3484,"date":"2012-04-20T07:11:20","date_gmt":"2012-04-20T05:11:20","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=3484"},"modified":"2012-04-20T23:33:53","modified_gmt":"2012-04-20T21:33:53","slug":"drzeworzedy","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2012\/04\/20\/drzeworzedy\/","title":{"rendered":"Drzeworz\u0119dy"},"content":{"rendered":"

Przywi\u0105za\u0142em si\u0119 do drzew, wi\u0119c jeszcze przez chwil\u0119 na ten temat.
\nDrzewo jakie jest, ka\u017cdy widzi. Przynajmniej trzy drzewa na jednej prostej to rz\u0105d. A drzeworz\u0105d? To dziwne okre\u015blenie wi\u0105\u017ce si\u0119 z zadaniem, z kt\u00f3rym nie mog\u0119 si\u0119 rozsta\u0107 od dw\u00f3ch wpis\u00f3w. Drzeworz\u0105d to drzewo-w-rz\u0119dzie, ale – drzewo na przeci\u0119ciu dw\u00f3ch rz\u0119d\u00f3w, to dwa drzeworz\u0119dy, na przeci\u0119ciu trzech – trzy itd. Je\u015bli wi\u0119c posadzimy np. 8 drzew w 6 rz\u0119dach – tak, jak poni\u017cej – i obok ka\u017cdego wpiszemy liczb\u0119 r\u00f3wn\u0105 liczbie rz\u0119d\u00f3w, w kt\u00f3rych dane drzewo si\u0119 znajduje,<\/p>\n

\"\"<\/a><\/p>\n

to suma wszystkich liczb b\u0119dzie r\u00f3wna liczbie drzeworz\u0119d\u00f3w danego uk\u0142adu, czyli w tym przypadku 19.<\/p>\n

W tzw. problemie sadzenia drzew<\/a>, „wyros\u0142ym” na pograniczu geometrii dyskretnej i kombinatorycznej, chodzi o posadzenie n<\/em><\/strong> drzew w jak najwi\u0119kszej liczbie rz\u0119d\u00f3w r<\/strong><\/em> po k<\/em><\/strong> drzewa w ka\u017cdym rz\u0119dzie. Poni\u017cej rozwi\u0105zania dla k<\/strong><\/em> = 3 i n<\/em><\/strong> = 6, 7, 8, 9 i 10.<\/p>\n

\"\"<\/a><\/p>\n

Liczba drzeworz\u0119d\u00f3w d<\/strong><\/em> w ka\u017cdym z tych rozwi\u0105za\u0144 r\u00f3wna jest k<\/em><\/strong>*r<\/strong><\/em>.
\nCzy je\u015bli pominiemy k<\/em><\/strong> i zapytamy o maksymaln\u0105 warto\u015b\u0107 d<\/strong><\/em> dla danego n<\/em><\/strong>, to wynik b\u0119dzie zawsze taki sam, jak w problemie sadzenia drzew? Z zadania goszcz\u0105cego w dw\u00f3ch poprzednich wpisach wynika, \u017ce nie, bowiem dla n<\/strong><\/em> = 8 warto\u015b\u0107 d<\/em><\/strong> mo\u017ce by\u0107 o jeden wi\u0119ksza, ni\u017c to wynika ze wzoru k<\/strong><\/em>*r<\/em><\/strong>, a wi\u0119c r\u00f3wna 22 – w jednym rz\u0119dzie mog\u0105 znale\u017a\u0107 si\u0119 4 drzewa:<\/p>\n

\"\"<\/a><\/p>\n

Jest to najmniejsza warto\u015b\u0107 d<\/strong><\/em> wi\u0119ksza od tej, kt\u00f3ra wynika z problemu sadzenia drzew – czyli dla danego n<\/em><\/strong>, ale z pomini\u0119ciem warunku, \u017ce liczba drzew k<\/strong><\/em> w ka\u017cdym rz\u0119dzie powinna by\u0107 jednakowa. Co ciekawe, jest to, jak dot\u0105d, jedyny znany mi taki przypadek. Inaczej m\u00f3wi\u0105c, nie uda\u0142o mi si\u0119 zwi\u0119kszy\u0107 liczby drzeworz\u0119d\u00f3w w rozwi\u0105zaniu problemu sadzenia drzew dla \u017cadnej innej warto\u015bci n<\/strong><\/em> i k<\/em><\/strong>. Gdyby kto\u015b z Pa\u0144stwa bli\u017cej zainteresowa\u0142 si\u0119 tym zagadnieniem i przeskoczy\u0142 o jedno oczko jakie\u015b inne d<\/em><\/strong> (dla danego n<\/strong><\/em>) wynikaj\u0105ce ze wzoru k<\/em><\/strong>*r<\/strong><\/em>, to wdzi\u0119czny b\u0119d\u0119 za informacj\u0119.<\/p>\n

A dla wszystkich znacznie prostsze zadanie, b\u0119d\u0105ce jakby odwrotno\u015bci\u0105 problemu sadzenia drzew.<\/p>\n

\"\"<\/a><\/p>\n

Na planie sadu drzewa znajduj\u0105 si\u0119 tylko w 12 w\u0119z\u0142ach siatki kwadratowej 5×7. Prosz\u0119 oznaczy\u0107 trzy w\u0119z\u0142y, w kt\u00f3rych nale\u017cy posadzi\u0107 jeszcze 3 drzewa tak, aby po tej czynno\u015bci \u017cadne 4 z 15 drzew nie ros\u0142y w jednym rz\u0119dzie. Nale\u017cy jednak zrobi\u0107 to tak, aby zachowany by\u0142 nast\u0119puj\u0105cy warunek: od ka\u017cdego drzewa do ka\u017cdego innego powinno by\u0107 mo\u017cliwe doj\u015bcie po liniach siatki bez konieczno\u015bci przechodzenia przez „bezdrzewny” w\u0119ze\u0142. Inaczej m\u00f3wi\u0105c, uk\u0142ad drzew powinien by\u0107 sp\u00f3jny.<\/p>\n

Komentarze z prawid\u0142owymi rozwi\u0105zaniami uwalniane s\u0105 wieczorem w przeddzie\u0144 kolejnego wpisu. Wpisy pojawiaj\u0105 si\u0119 co kilka dni.<\/sub><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Przywi\u0105za\u0142em si\u0119 do drzew, wi\u0119c jeszcze przez chwil\u0119 na ten temat. Drzewo jakie jest, ka\u017cdy widzi. Przynajmniej trzy drzewa na jednej prostej to rz\u0105d. A drzeworz\u0105d? To dziwne okre\u015blenie wi\u0105\u017ce si\u0119 z zadaniem, z kt\u00f3rym nie mog\u0119 si\u0119 rozsta\u0107 od dw\u00f3ch wpis\u00f3w. Drzeworz\u0105d to drzewo-w-rz\u0119dzie, ale – drzewo na przeci\u0119ciu dw\u00f3ch rz\u0119d\u00f3w, to dwa drzeworz\u0119dy, […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3484"}],"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=3484"}],"version-history":[{"count":15,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3484\/revisions"}],"predecessor-version":[{"id":3503,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3484\/revisions\/3503"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=3484"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=3484"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=3484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}