{"id":4140,"date":"2012-10-14T09:40:20","date_gmt":"2012-10-14T07:40:20","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=4140"},"modified":"2012-10-14T09:40:20","modified_gmt":"2012-10-14T07:40:20","slug":"co-policzyl-bazyli","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2012\/10\/14\/co-policzyl-bazyli\/","title":{"rendered":"Co policzy\u0142 Bazyli"},"content":{"rendered":"

Przypominam problem postawiony przez Esteona:
\nIle jest r\u00f3\u017cnych bezpiecznych ustawie\u0144 najwi\u0119kszej liczby wie\u017coskoczk\u00f3w na szachownicy (8×8)?<\/strong><\/em>
\nWie\u017coskoczek jest tzw. figur\u0105 „bajkow\u0105”, kt\u00f3ra porusza si\u0119 jak wie\u017ca i skoczek. Ustawienia s\u0105:
\n– bezpieczne, je\u015bli \u017caden wie\u017coskoczek nie atakuje \u017cadnego innego;
\n– r\u00f3\u017cne, je\u015bli \u017cadnego z nich nie mo\u017cna przekszta\u0142ci\u0107 w inne w wyniku obrot\u00f3w lub\/i odbi\u0107 lustrzanych.<\/p>\n

Odpowied\u017a na powy\u017csze pytanie nie jest znana, co nasuwa podejrzenia, \u017ce problem jest trudny obliczeniowo. Brytyjski szachista Thomas Dawson znalaz\u0142 „na piechot\u0119” rozwi\u0105zania dla plansz do 6 \u00d7 6 w\u0142\u0105cznie i opublikowa\u0142 je w 1931 r. Oczywistym jest, \u017ce na planszy n<\/em> \u00d7 n<\/em> da si\u0119 ustawi\u0107 co najwy\u017cej n<\/em> wie\u017coskoczk\u00f3w (n<\/em> = 1, 2, 3,…). Ci\u0105g liczb tych ustawie\u0144 zaczyna si\u0119 tak:
\n1, 1, 1, 3, 6, 21,…
\nDalej, czyli dla n<\/em>>6, jest mg\u0142a, kt\u00f3rej dot\u0105d nikomu nie uda\u0142o si\u0119 rozwia\u0107.
\nTymczasem Bazyli w komentarzu poda\u0142 rozwi\u0105zanie problemu Esteona znalezione przy wykorzystaniu arkusza kalkulacyjnego. W pierwszej chwili nie chcia\u0142o mi si\u0119 w to wierzy\u0107 – i s\u0142usznie. Wynik podany przez Bazylego jest bowiem liczb\u0105 wszystkich<\/strong> ustawie\u0144, a nie r\u00f3\u017cnych<\/strong>. Ta liczba (2766) jest znana; znany jest tak\u017ce ci\u0105g liczb wszystkich ustawie\u0144 dla plansz r\u00f3\u017cnej wielko\u015bci: 1, 2, 2, 8, 20, 94, 438, 2766, 19480, 163058 ,… (OEIS A000903<\/a>). Schody zaczynaj\u0105 si\u0119 przy pr\u00f3bie przekszta\u0142cenia wszystkiego<\/strong> w r\u00f3\u017cne<\/strong>. Dot\u0105d nikt tych schod\u00f3w nie pokona\u0142 dla n>6. Z lenistwa?<\/p>\n

Na zako\u0144czenie wie\u017coskoczkowego tematu zwyk\u0142a dwuchod\u00f3wka, ale oczywi\u015bcie z jedn\u0105 niezwyk\u0142\u0105 figur\u0105.<\/p>\n

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

Wystarczy wskaza\u0107 pierwszy ruch bia\u0142ych.
\nZadanie liczy sobie 123 lata, ale przez ten czas wcale nie „zmi\u0119k\u0142o”. Wci\u0105\u017c jest twardym orzechem.<\/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.<\/sup><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Przypominam problem postawiony przez Esteona: Ile jest r\u00f3\u017cnych bezpiecznych ustawie\u0144 najwi\u0119kszej liczby wie\u017coskoczk\u00f3w na szachownicy (8×8)? Wie\u017coskoczek jest tzw. figur\u0105 „bajkow\u0105”, kt\u00f3ra porusza si\u0119 jak wie\u017ca i skoczek. Ustawienia s\u0105: – bezpieczne, je\u015bli \u017caden wie\u017coskoczek nie atakuje \u017cadnego innego; – r\u00f3\u017cne, je\u015bli \u017cadnego z nich nie mo\u017cna przekszta\u0142ci\u0107 w inne w wyniku obrot\u00f3w lub\/i odbi\u0107 […]<\/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\/4140"}],"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=4140"}],"version-history":[{"count":19,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/4140\/revisions"}],"predecessor-version":[{"id":4160,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/4140\/revisions\/4160"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=4140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=4140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=4140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}