Przed trzema laty napomkn\u0105\u0142em\u00a0w \u0141amiblogu\u00a0o tzw. problemie Flawiusza. Odpowiadaj\u0105c w\u00f3wczas na jeden z komentarzy, napisa\u0142em o zamiarze pope\u0142nienia d\u0142u\u017cszego artyku\u0142u na ten temat. Artyku\u0142 ukaza\u0142 si\u0119 w marcowym numerze „\u015awiata Nauki”. Wspominam o tym, kontynuuj\u0105c temat b\u0142\u0119d\u00f3w autorskich z poprzedniego wpisu, bowiem w artykule tym pope\u0142ni\u0142em pewien szczeg\u00f3lny b\u0142\u0105d… \u015bwiadomie. Ciekaw by\u0142em, czy kto\u015b z czytelnik\u00f3w go zauwa\u017cy. I nie zawiod\u0142em si\u0119.
\nKr\u00f3tko przypomn\u0119 spraw\u0119 Flawiusza, przytaczaj\u0105c klasyczn\u0105 historyjk\u0119, cho\u0107 nieco zmodyfikowan\u0105\u00a0przez w\u0142oskiego matematyka Girolamo Cardano w XVI wieku.<\/p>\n
Rzymianie otoczyli ukryt\u0105 w jaskini grup\u0119 41 \u017cydowskich powsta\u0144c\u00f3w. Jednym z nich, dow\u00f3dc\u0105, by\u0142 Flawiusz (chodzi o autentyczn\u0105 posta\u0107 J\u00f3zefa Flawiusza i rzeczywiste wydarzenie\u00a0– wojn\u0119 \u017cydowsk\u0105, kt\u00f3ra mia\u0142a miejsce w Judei w latach 66-73; imi\u0119 J\u00f3zef jest o tyle istotne, \u017ce rzymskim dow\u00f3dc\u0105 w tej wojnie by\u0142 tak\u017ce Flawiusz, ale Tytus). Aby nie zgin\u0105\u0107 z r\u0119ki wroga, otoczeni postanowili pope\u0142ni\u0107 samob\u00f3jstwo. Flawiusz, uwa\u017caj\u0105c, \u017ce by\u0142by to ci\u0119\u017cki grzech, zaproponowa\u0142, aby wszyscy utworzyli okr\u0105g i rozpocz\u0119li wyliczank\u0119 do trzech, zabijaj\u0105c ka\u017cdego co trzeciego, za\u015b samob\u00f3jstwo pope\u0142ni\u0142by tylko ostatni. Wiele wskazuje na to, \u017ce by\u0142a to propozycja sprytna i ob\u0142udna, cho\u0107 Flawiusz wspomina, \u017ce „tak zrz\u0105dzi\u0142 los albo Opatrzno\u015b\u0107 Bo\u017ca”, \u017ce zosta\u0142 jako ostatni na „placu samozag\u0142ady” i…\u00a0 podda\u0142 si\u0119 Rzymianom, kt\u00f3rzy darowali mu \u017cycie.<\/p>\n
Problem polega, w konkretnym przypadku, na o ustaleniu, kt\u00f3re miejsce zaj\u0105\u0142 Flawiusz, by prze\u017cy\u0107, a w og\u00f3lnym przypadku brzmi tak:<\/p>\n
poruszaj\u0105c si\u0119 w kierunku zgodnym z ruchem wskaz\u00f3wek zegara po okr\u0119gu utworzonym z n<\/em> ponumerowanych element\u00f3w, usuwamy\u00a0– zaczynaj\u0105c od pierwszego\u00a0– co k<\/em>-ty element dot\u0105d, a\u017c pozostanie jeden; nale\u017cy ustali\u0107 numer p<\/em> tego ostatniego ocalonego elementu.<\/strong><\/p>\n Wz\u00f3r og\u00f3lny, okre\u015blaj\u0105cy zale\u017cno\u015b\u0107 p<\/em> od n<\/em> i k<\/em> nie jest znany, cho\u0107 oczywi\u015bcie „na piechot\u0119” albo korzystaj\u0105c z programu mo\u017cna\u00a0upora\u0107 si\u0119\u00a0z konkretn\u0105 sytuacj\u0105, czyli sprawdzi\u0107, \u017ce np. dla n<\/em> = 41 i\u00a0k<\/em> \u00a0= 3 Flawiusz mia\u0142 numer p<\/em> = 31.\u00a0Nietrudno tak\u017ce poradzi\u0107 sobie w pewnej szczeg\u00f3lnej sytuacji: tu\u017c przed rozpocz\u0119ciem wyliczanki do k\u00f3\u0142ka do\u0142\u0105cza jedna osoba,\u00a0czyli n wzrasta do 42. Flawiusz, aby prze\u017cy\u0107,\u00a0powinien w\u00f3wczas przesun\u0105\u0107 si\u0119 o trzy miejsca w lewo (p<\/em> = 34), poniewa\u017c gdy n<\/em> zwi\u0119ksza si\u0119 o 1, to p<\/em> wzrasta o k<\/em>. A to dlatego, \u017ce po pierwszym odliczeniu o k<\/em> powstanie sytuacja taka, jak przy 41 osobach. Je\u015bli zatem znamy p<\/em> dla n<\/em> i k<\/em>, to mo\u017cemy \u0142atwo policzy\u0107, jakie b\u0119dzie dla n+1<\/em> i k<\/em>.\u00a0„Wzorowo” wygl\u0105da to tak:<\/p>\n p<\/em> (n<\/em>+1, k<\/em>) = [p<\/em> (n<\/em>, k<\/em>) + k<\/em>] (mod n<\/em>+1)<\/p>\n albo jeszcze og\u00f3lniej, czyli gdyby do k\u00f3\u0142ka do\u0142\u0105czy\u0142o x<\/em> os\u00f3b:<\/p>\n p<\/em> (n<\/em>+x<\/em>, k<\/em>) = [p<\/em> (n<\/em>, k<\/em>) + kx<\/em>] (mod n<\/em>+x<\/em>)<\/p>\n I tu pojawia si\u0119 „b\u0142\u0105d”, kt\u00f3ry wy\u0142apa\u0142o kilku czytelnik\u00f3w. Ot\u00f3\u017c ostatni wz\u00f3r jest prawdziwy tylko dla x<\/em> nie wi\u0119kszych od pewnej warto\u015bci a<\/strong>,<\/em> natomiast w artykule poda\u0142em przyk\u0142ad dla x<\/em> wi\u0119kszego o 1 od a<\/strong><\/em>.<\/p>\n Jaka jest warto\u015b\u0107 a<\/strong><\/em>: Kto czyta\u0142 i pami\u0119ta\u00a0wspomniany artyku\u0142 lub mo\u017ce do niego zajrze\u0107, dla tego udzielenie odpowiedzi na pierwsze pytanie\u00a0jest trywialne, wi\u0119c adresuj\u0119 je do pozosta\u0142ych. B\u0119d\u0119 natomiast niezmiernie zaskoczony, je\u017celi pojawi si\u0119 poprawna odpowied\u017a na drugie pytanie.<\/p>\n Komentarze z prawid\u0142owymi<\/strong> rozwi\u0105zaniami uwalniane s\u0105 wieczorem w przeddzie\u0144 kolejnego wpisu. Wpisy pojawiaj\u0105 si\u0119 co 3-4 dni.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":" Przed trzema laty napomkn\u0105\u0142em\u00a0w \u0141amiblogu\u00a0o tzw. problemie Flawiusza. Odpowiadaj\u0105c w\u00f3wczas na jeden z komentarzy, napisa\u0142em o zamiarze pope\u0142nienia d\u0142u\u017cszego artyku\u0142u na ten temat. Artyku\u0142 ukaza\u0142 si\u0119 w marcowym numerze „\u015awiata Nauki”. Wspominam o tym, kontynuuj\u0105c temat b\u0142\u0119d\u00f3w autorskich z poprzedniego wpisu, bowiem w artykule tym pope\u0142ni\u0142em pewien szczeg\u00f3lny b\u0142\u0105d… \u015bwiadomie. Ciekaw by\u0142em, czy kto\u015b z […]<\/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\/1123"}],"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=1123"}],"version-history":[{"count":21,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/1123\/revisions"}],"predecessor-version":[{"id":1145,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/1123\/revisions\/1145"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=1123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=1123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=1123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n1) w przypadku Flawiusza (n<\/em> = 41, k<\/em> = 3, p<\/em> = 31)?
\n2) w og\u00f3lnym przypadku (wz\u00f3r), czyli a<\/strong><\/em> = f (n<\/em>, k<\/em>, p<\/em>)?<\/p>\n