{"id":3435,"date":"2012-04-12T07:28:25","date_gmt":"2012-04-12T05:28:25","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=3435"},"modified":"2012-04-12T07:28:25","modified_gmt":"2012-04-12T05:28:25","slug":"piec-drzew","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2012\/04\/12\/piec-drzew\/","title":{"rendered":"Pi\u0119\u0107 drzew"},"content":{"rendered":"

U\u0142o\u017cy\u0107 zadanie i nie potrafi\u0107 go rozwi\u0105za\u0107. Tak czasem bywa, ale cz\u0119\u015bciej zdarza mi si\u0119 znajdywa\u0107 rozwi\u0105zanie, kt\u00f3re – jak si\u0119 p\u00f3\u017aniej okazuje – albo nie jest najlepsze, albo nie jedyne. Co ciekawe, konsultanci te\u017c czasem zawodz\u0105 i dopiero niekt\u00f3rzy czytelnicy wy\u0142apuj\u0105 potkni\u0119cia. Ostatnio taki przypadek mia\u0142 miejsce w marcowym \u015awiecie Nauki<\/em>.<\/p>\n

Artyku\u0142 nawi\u0105zywa\u0142 do tzw. problemu sadzenia drzew, kt\u00f3ry w og\u00f3lnym uj\u0119ciu polega na posadzeniu n<\/strong><\/em> drzew w r<\/em><\/strong> rz\u0119dach tak, aby w ka\u017cdym rz\u0119dzie ros\u0142o dok\u0142adnie k<\/em><\/strong> drzew. Bardziej konkretnie, chodzi o znalezienie maksymalnego r<\/em><\/strong> dla ustalonych n<\/em><\/strong> i k<\/strong><\/em>. Na przyk\u0142ad, je\u015bli n<\/strong><\/em> = 8 i k<\/em><\/strong> = 3, to rz\u0119d\u00f3w r<\/em><\/strong> mo\u017ce by\u0107 najwy\u017cej 7, a drzewa nale\u017cy posadzi\u0107 tak:<\/p>\n

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

Jedno z zada\u0144 konkursowych by\u0142o nieco zakr\u0119cone, bo drzewa znajdowa\u0142y si\u0119 w w\u0119z\u0142ach siatki kwadratowej, a ponadto wyst\u0119powa\u0142y dwie warto\u015bci r<\/em><\/strong> i k<\/strong><\/em>.<\/p>\n

W sadzie ro\u015bnie 169 drzew. Na rysunku odpowiadaj\u0105 im w\u0119z\u0142y siatki kwadratowej. Osiem drzew przeznaczono do wykarczowania – trzy z nich (oznaczone na rysunku) znajduj\u0105 si\u0119 w rogach sadu, czyli w punktach a1, a13 i m1. Gdzie ro\u015bnie pi\u0119\u0107 pozosta\u0142ych, je\u015bli wszystkie osiem tworzy siedem rz\u0119d\u00f3w: sze\u015b\u0107 rz\u0119d\u00f3w po trzy drzewa w ka\u017cdym (nie wi\u0119cej) oraz jeden rz\u0105d z czterema drzewami?<\/em><\/p>\n

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

Na zmaganie si\u0119 z tym zadaniem, podobnie jak na ca\u0142y problem sadzenia drzew, nie ma uniwersalnej metody. Trzeba pr\u00f3bowa\u0107 i kombinowa\u0107, co te\u017c czyni\u0142em i znalaz\u0142em nast\u0119puj\u0105ce rozwi\u0105zanie: pi\u0119\u0107 drzew tkwi w punktach a7, d4, e1, e5, g1. Graficznie, z zaznaczonymi siedmioma rz\u0119dami, wygl\u0105da to tak:<\/p>\n

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

Co ciekawe, konsultant te\u017c wpad\u0142 na takie rozwi\u0105zanie, a na \u017cadne inne nie, co utwierdzi\u0142o mnie w podejrzeniu, \u017ce innego nie ma. Jakie\u017c wi\u0119c by\u0142o moje zdziwienie, gdy okaza\u0142o si\u0119, \u017ce \u017cadna z blisko setki os\u00f3b, uczestnicz\u0105cych w konkursie, nie nades\u0142a\u0142a takiego rozwi\u0105zania.<\/p>\n

Ile r\u00f3\u017cnych rozwi\u0105za\u0144 ma to zadanie – nie wiem, a ile r\u00f3\u017cnych nades\u0142ali czytelnicy – na razie nie ujawni\u0119. By\u0107 mo\u017ce niekt\u00f3rzy z Pa\u0144stwa spr\u00f3buj\u0105 znale\u017a\u0107 i nades\u0142a\u0107 cho\u0107 jedno – oczywi\u015bcie inne ni\u017c podane wy\u017cej – i mo\u017ce b\u0119dzie w\u015br\u00f3d nich takie, kt\u00f3rego nie znam. Wszystkie staro- i nowoodkryte podam za kilka dni, o ile kto\u015b z Pa\u0144stwa wcze\u015bniej do cna nie rozgryzie tego zadania.<\/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":"

U\u0142o\u017cy\u0107 zadanie i nie potrafi\u0107 go rozwi\u0105za\u0107. Tak czasem bywa, ale cz\u0119\u015bciej zdarza mi si\u0119 znajdywa\u0107 rozwi\u0105zanie, kt\u00f3re – jak si\u0119 p\u00f3\u017aniej okazuje – albo nie jest najlepsze, albo nie jedyne. Co ciekawe, konsultanci te\u017c czasem zawodz\u0105 i dopiero niekt\u00f3rzy czytelnicy wy\u0142apuj\u0105 potkni\u0119cia. Ostatnio taki przypadek mia\u0142 miejsce w marcowym \u015awiecie Nauki. Artyku\u0142 nawi\u0105zywa\u0142 do […]<\/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\/3435"}],"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=3435"}],"version-history":[{"count":8,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3435\/revisions"}],"predecessor-version":[{"id":3473,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3435\/revisions\/3473"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=3435"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=3435"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=3435"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}