{"id":512,"date":"2009-08-01T09:12:45","date_gmt":"2009-08-01T07:12:45","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=512"},"modified":"2009-10-06T09:05:34","modified_gmt":"2009-10-06T07:05:34","slug":"ziarnko-do-ziarnka","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2009\/08\/01\/ziarnko-do-ziarnka\/","title":{"rendered":"Ziarnko do ziarnka"},"content":{"rendered":"

W lipcowym numerze \u015awiata Nauki<\/em> sadzi\u0142em ziarenka\u00a0– mi\u0119dzy innymi na grz\u0105dce. To, \u017ce na grz\u0105dce, a nie na grz\u0105dkach, jest istotne, bo nasionka umieszczane by\u0142y w rz\u0119dzie. Zmie\u0144my jednak przej\u015bciowo ogrodnika na matematyka i powiedzmy bez ogr\u00f3dka…,\u00a0to znaczy\u00a0bez ogr\u00f3dek:
\noznacza\u0142em na osi liczbowej punkty odpowiadaj\u0105ce liczbom ca\u0142kowitym nieujemnym<\/strong>.
\nM\u00f3wi\u0105c \u015bci\u015blej, chodzi\u0142o o to, aby punkt\u00f3w ulokowa\u0107 jak najwi\u0119cej na jak najkr\u00f3tszym odcinku<\/strong>, zachowuj\u0105c nast\u0119puj\u0105c\u0105 zasad\u0119:
\nwszystkie odleg\u0142o\u015bci mi\u0119dzy punktami powinny by\u0107 r\u00f3\u017cne<\/strong> (a wi\u0119c nie tylko mi\u0119dzy kolejnymi, ale mi\u0119dzy ka\u017cd\u0105 par\u0105 punkt\u00f3w).
\nKorzystaj\u0105c z informacji o kilku ciekawych ci\u0105gach zaproponowa\u0142em prosty i (na poz\u00f3r) skuteczny spos\u00f3b radzenia sobie z zadaniem.<\/p>\n

Zaczynamy od oznaczenia punkt\u00f3w 0<\/strong> i 1<\/strong>, a nast\u0119pne wybieramy po kolei, przesuwaj\u0105c si\u0119 zawsze o najkr\u00f3tszy dystans dot\u0105d nie wykorzystany. Po odleg\u0142o\u015bci r\u00f3wnej 1<\/em>\u00a0– mi\u0119dzy 0<\/strong> a 1<\/strong>\u00a0– kolej na dystans 2<\/em>, czyli punkt 3<\/strong>, co r\u00f3wnocze\u015bnie za\u0142atwi odleg\u0142o\u015b\u0107 3<\/em> mi\u0119dzy 0<\/strong> a 3<\/strong>. Nast\u0119pnym najbli\u017cszym punktem b\u0119dzie 7<\/strong>\u00a0– w ten spos\u00f3b „obskoczy si\u0119” dystanse 4<\/em> (7<\/strong>–3<\/strong>), 6<\/em> (7<\/strong>–1<\/strong>) i 7<\/em> (7<\/strong>–0<\/strong>). Teraz pora na najkr\u00f3tsz\u0105 z opuszczonych odleg\u0142o\u015bci, czyli 5<\/em>, a wi\u0119c oznaczamy punkt 12<\/strong> itd. W rezultacie oznaczane punkty utworz\u0105 tzw. ci\u0105g B2: 0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147, 181, 203, 251, 289, 360, 400<\/strong>,…, kt\u00f3ry z regu\u0142y definiowany jest rekurencyjnie nieco inaczej, ni\u017c wynika\u0142oby to z powy\u017cszego sposobu jego tworzenia (r\u00f3\u017cne s\u0105 sumy par liczb, uwzgl\u0119dniaj\u0105c tak\u017ce pary utworzone z wzi\u0119tej dwukrotnie tej samej liczby).<\/p>\n

Opisany spos\u00f3b jest bardzo prosty i wydaje si\u0119 skuteczny. A jednak… czy zawsze maj\u0105c n<\/em> ziarenek (wracamy do ogr\u00f3dka, pozostaj\u0105c oczywi\u015bcie przy liczbach ca\u0142kowitych) potrzebujemy grz\u0105dki o d\u0142ugo\u015bci r\u00f3wnej warto\u015bci n<\/em>-tego wyrazu ci\u0105gu B2 (zak\u0142adamy, \u017ce ko\u0144ce grz\u0105dki nale\u017c\u0105 do grz\u0105dki)? Czy grz\u0105dka nie mo\u017ce by\u0107 kr\u00f3tsza?
\nAlbo inaczej: czy dysponuj\u0105c grz\u0105dk\u0105 o d\u0142ugo\u015bci d<\/em> zawsze umie\u015bcimy na niej najwy\u017cej tyle ziarenek, ile wyraz\u00f3w w ci\u0105gu jest nie wi\u0119kszych od tego o warto\u015bci r\u00f3wnej d<\/em>? Czy nie da si\u0119 upchn\u0105\u0107 ich wi\u0119cej?<\/p>\n

Nie zach\u0119cam Pa\u0144stwa do zmagania si\u0119 z tym problemem\u00a0– \u017ce tak powiem\u00a0– w ca\u0142ej rozci\u0105g\u0142o\u015bci, bo zagadnienie jest benedykty\u0144skie nawet dla komputera. Nale\u017cy prawdopodobnie do tzw. problem\u00f3w NP-trudnych i przed laty by\u0142o analizowane w ramach projektu oblicze\u0144 rozproszonych.
\nProponuj\u0119 natomiast zmierzy\u0107 si\u0119 z jednym konkretnym zadaniem.<\/p>\n

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

Kt\u00f3re cztery nasionka nale\u017cy usun\u0105\u0107, aby wszystkie odleg\u0142o\u015bci mi\u0119dzy pozostawionymi by\u0142y r\u00f3\u017cne?<\/p>\n","protected":false},"excerpt":{"rendered":"

W lipcowym numerze \u015awiata Nauki sadzi\u0142em ziarenka\u00a0– mi\u0119dzy innymi na grz\u0105dce. To, \u017ce na grz\u0105dce, a nie na grz\u0105dkach, jest istotne, bo nasionka umieszczane by\u0142y w rz\u0119dzie. Zmie\u0144my jednak przej\u015bciowo ogrodnika na matematyka i powiedzmy bez ogr\u00f3dka…,\u00a0to znaczy\u00a0bez ogr\u00f3dek: oznacza\u0142em na osi liczbowej punkty odpowiadaj\u0105ce liczbom ca\u0142kowitym nieujemnym. M\u00f3wi\u0105c \u015bci\u015blej, chodzi\u0142o o to, aby punkt\u00f3w […]<\/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\/512"}],"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=512"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/512\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}