{"id":9545,"date":"2024-06-08T07:57:07","date_gmt":"2024-06-08T06:57:07","guid":{"rendered":"https:\/\/penszko.blog.polityka.pl\/?p=9545"},"modified":"2024-06-08T09:11:21","modified_gmt":"2024-06-08T08:11:21","slug":"barierki","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2024\/06\/08\/barierki\/","title":{"rendered":"Barierki"},"content":{"rendered":"\n<p>Na ile ca\u0142kowicie r\u00f3\u017cnych sposob\u00f3w (z dok\u0142adno\u015bci\u0105 do odbi\u0107 i obrot\u00f3w) mo\u017cna obej\u015b\u0107 wie\u017c\u0105 po trasie zamkni\u0119tej diagram <em>n<\/em>\u00d7<em>n<\/em>, goszcz\u0105c tylko raz w ka\u017cdym polu? Wypada doda\u0107, \u017ce jest to mo\u017cliwe tylko dla parzystych <em>n<\/em>, wi\u0119c w\u0142a\u015bciwie chodzi o diagram 2<em>n<\/em>\u00d72<em>n<\/em>. Dla <em>n<\/em>=1 spos\u00f3b jest oczywi\u015bcie jeden, dla <em>n<\/em>=2 \u2013 dwa.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"\/wp-content\/uploads\/2024\/06\/Bar_1.jpg\"><img loading=\"lazy\" decoding=\"async\" width=\"1000\" height=\"367\" src=\"\/wp-content\/uploads\/2024\/06\/Bar_1.jpg\" alt=\"\" class=\"wp-image-9546\"\/><\/a><\/figure>\n\n\n\n<p>Dalej liczba sposob\u00f3w bardzo szybko ro\u015bnie: dla <em>n<\/em>=3 jest ich 149, a dla <em>n<\/em>=4, czyli dla szachownicy \u2013 580717.<br>Pytanie, kt\u00f3re pojawi\u0142o si\u0119 ju\u017c w \u0141amiblogu przed wielu laty brzmi: ile co najmniej barier nale\u017cy ustawi\u0107 mi\u0119dzy polami diagramu 2<em>n<\/em>\u00d72<em>n<\/em>, aby mo\u017cliwe by\u0142o obej\u015bcie diagramu wie\u017c\u0105 tylko w jeden spos\u00f3b? Pytanie to dotyczy\u0142o jednak w\u00f3wczas konkretnie <em>n<\/em>=3, czyli diagramu 6\u00d76 (dla <em>n<\/em>=2 potrzebne s\u0105 dwie bariery, a ich mo\u017cliwe ustawienie, zreszt\u0105 niejedno, \u0142atwo znale\u017a\u0107). W jednym z komentarzy pojawi\u0142o si\u0119 rozwi\u0105zanie z 4 barierami i liczba ta uchodzi dzi\u015b za minimaln\u0105, cho\u0107 dowodu, \u017ce 3 bariery nie s\u0105 mo\u017cliwe \u2013 brak.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"\/wp-content\/uploads\/2024\/06\/Bar_2.jpg\"><img loading=\"lazy\" decoding=\"async\" width=\"1000\" height=\"1000\" src=\"\/wp-content\/uploads\/2024\/06\/Bar_2.jpg\" alt=\"\" class=\"wp-image-9547\"\/><\/a><\/figure>\n\n\n\n<p>Tym razem analogiczne pytanie dotyczy szachownicy (<em>n<\/em>=4), wi\u0119c jest znacznie trudniejsze. Odpowiedzi nie znam i o ile wiem, nikt takiego pytania dot\u0105d nie zadawa\u0142. Wst\u0119pem do tego tematu mo\u017ce by\u0107 poni\u017csze zadanie, w kt\u00f3rym barier jest a\u017c 16.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"\/wp-content\/uploads\/2024\/06\/Bar_3.jpg\"><img loading=\"lazy\" decoding=\"async\" width=\"1000\" height=\"999\" src=\"\/wp-content\/uploads\/2024\/06\/Bar_3.jpg\" alt=\"\" class=\"wp-image-9548\"\/><\/a><\/figure>\n\n\n\n<p>Rozwi\u0105zanie polega na:<br>(a) narysowaniu okr\u0119\u017cnej trasy wie\u017cy, zaliczaj\u0105cej wszystkie pola \u2013 ka\u017cde tylko raz (jako odpowied\u017a wystarczy poda\u0107 liczb\u0119 za\u0142ama\u0144 trasy na przek\u0105tnych diagramu);<br>(b) pr\u00f3bie usuni\u0119cia kt\u00f3rej\u015b blokady (blokad) tak, by jedno rozwi\u0105zanie by\u0142o zachowane.<br>Ju\u017c (a) jest moim zdaniem nieproste, a (<strong>b<\/strong>) \u2013 <strong>b<\/strong>enedykty\u0144skie, nie wspominaj\u0105c o pocz\u0105tkowym pytaniu o minimaln\u0105 liczb\u0119 blokad.<\/p>\n\n\n\n<p><em>Komentarze z&nbsp;prawid\u0142owym rozwi\u0105zaniem ujawniane s\u0105 wieczorem w&nbsp;przeddzie\u0144 kolejnego wpisu (z b\u0142\u0119dnym zwykle od razu). Wpisy pojawiaj\u0105 si\u0119 co 7 dni.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Na ile ca\u0142kowicie r\u00f3\u017cnych sposob\u00f3w (z dok\u0142adno\u015bci\u0105 do odbi\u0107 i obrot\u00f3w) mo\u017cna obej\u015b\u0107 wie\u017c\u0105 po trasie zamkni\u0119tej diagram n\u00d7n, goszcz\u0105c tylko raz w ka\u017cdym polu? Wypada doda\u0107, \u017ce jest to mo\u017cliwe tylko dla parzystych n, wi\u0119c w\u0142a\u015bciwie chodzi o diagram 2n\u00d72n. Dla n=1 spos\u00f3b jest oczywi\u015bcie jeden, dla n=2 \u2013 dwa. Dalej liczba sposob\u00f3w bardzo [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":true,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/9545"}],"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=9545"}],"version-history":[{"count":3,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/9545\/revisions"}],"predecessor-version":[{"id":9552,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/9545\/revisions\/9552"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=9545"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=9545"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=9545"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}