{"id":2230,"date":"2018-01-08T12:08:30","date_gmt":"2018-01-08T11:08:30","guid":{"rendered":"http:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/?p=2230"},"modified":"2018-01-10T12:59:43","modified_gmt":"2018-01-10T11:59:43","slug":"das-josephus-problem","status":"publish","type":"post","link":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/2018\/01\/08\/das-josephus-problem\/","title":{"rendered":"Das Josephus-Problem"},"content":{"rendered":"

Eine genaue Beschreibung des Hintergrunds des Problems findet sich in der Wikipedia<\/a>.<\/p>\n

Problemstellung:
\nEine bestimmte Zahl von Personen (n) steht im Kreis.
\nEs gibt eine „Startperson“. Geben wir ihr Nummer 1 und nummerieren wir fortlaufend im Kreis herum. Dann wird jede zweite Person aus dem Spiel genommen und zwar so lange, bis nur mehr eine Person \u00fcbrig ist.
\nBei 4 Personen werden also zun\u00e4chst die Personen 2 und 4 aus dem Spiel genommen und wir sind wieder bei Person 1. Von dieser Startposition aus wird Person 3 aus dem Spiel genommen und 1 bleibt \u00fcber.
\nDas gilt allgemeiner: Wann immer die Zahl der Personen gerade ist, dann ist man nach einer Runde genau wieder bei der urspr\u00fcnglichen Startposition und das Verfahren wird fortgesetzt. Wenn die Zahl n eine Zweierpotenz ist (2, 4, 8, 16, …)ist, dann ist man nach jeder Runde an der Startposition und daher ist die Person an der Startposition auch die Person, die \u00fcber bleibt.<\/p>\n

Bei den anderen Zahlen ist die \u00dcberlegung etwas komplizierter. Sehen wir uns den Fall n=19 an.<\/p>\n

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

Wenn man das Spiel komplett zu Ende durchspielt, dann sieht man, dass von Startperson 1 aus gez\u00e4hlt Person 7 \u00fcber bleibt.
\nWir k\u00f6nnen auch sagen: Bei 19 Personen ist die Person 6 Positionen vor der Startperson die, die \u00fcber bleibt. (Vor bedeutet in Pfeilrichtung.)<\/p>\n

Wenn wir jetzt einen einzelnen Schritt des Ausscheidungsverfahrens durchf\u00fchren, dann sehen wir folgendes Bild:<\/p>\n

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

Wir haben eine neue Konfiguration mit n=18 und einer neuen Startposition. Die vorher und nachher rot markierte Position ist in beiden F\u00e4llen die Position der Person, die \u00fcber bleibt.<\/p>\n

Diese \u201e\u00dcberbleibposition\u201c ist in der neuen Konfiguration 4 Schritte, also 2 Schritte weniger als in der alten Konfiguration von der Startposition entfernt. Das gilt fast immer, es gibt nur 2 m\u00f6gliche Ausnahmen. Wenn die Startposition und die \u00dcberbleibposition identisch sind, dann funktioniert diese \u00dcberlegung nicht. Wenn die \u00dcberbleibposition nur einen Schritt hinter der Startposition l\u00e4ge, dann w\u00fcrde das ebenfalls nicht funktionieren. Die Position unmittelbar hinter der Startposition kann aber nie die Endposition sein, da die Person dort ja auf jeden Fall im n\u00e4chsten Schritt entfernt wird.<\/p>\n

Wir k\u00f6nnen diese \u00dcberlegung auch in umgekehrter Richtung anwenden. Wenn eine Position dazukommt, dann erh\u00f6ht sich der Abstand zur \u00dcberbleibposition um 2.<\/p>\n

Wir wissen also: Wenn n eine Zweierpotenz ist, dann ist die Startpostion auch die \u00dcberbleibposition.
\nDamit k\u00f6nnen wir die \u00dcberbleibposition f\u00fcr alle F\u00e4lle bestimmen. F\u00fcr Zweierpotenzen ist 1 die L\u00f6sungszahl, und f\u00fcr jede
\nzus\u00e4tzliche Position wird die L\u00f6sungszahl um 2 erh\u00f6ht (wir m\u00fcssen ja um 2 Positionen weitergehen). Sobad wir beim Dazugeben von Positionen zur n\u00e4chsten Zweierpotenz kommen starten wir wieder mit L\u00f6sungszahl 1.<\/p>\n

\n<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Positionen<\/td>\nbleibt \u00fcber<\/td>\n<\/tr>\n
1<\/td>\n1<\/td>\n<\/tr>\n
2<\/td>\n1<\/td>\n<\/tr>\n
3<\/td>\n3<\/td>\n<\/tr>\n
4<\/td>\n1<\/td>\n<\/tr>\n
5<\/td>\n3<\/td>\n<\/tr>\n
6<\/td>\n5<\/td>\n<\/tr>\n
7<\/td>\n7<\/td>\n<\/tr>\n
8<\/td>\n1<\/td>\n<\/tr>\n
9<\/td>\n3<\/td>\n<\/tr>\n
10<\/td>\n5<\/td>\n<\/tr>\n
11<\/td>\n7<\/td>\n<\/tr>\n
12<\/td>\n9<\/td>\n<\/tr>\n
13<\/td>\n11<\/td>\n<\/tr>\n
14<\/td>\n13<\/td>\n<\/tr>\n
15<\/td>\n15<\/td>\n<\/tr>\n
16<\/td>\n1<\/td>\n<\/tr>\n
17<\/td>\n3<\/td>\n<\/tr>\n
18<\/td>\n5<\/td>\n<\/tr>\n
19<\/td>\n7<\/td>\n<\/tr>\n
20<\/td>\n9<\/td>\n<\/tr>\n

<\/p>\n

<\/td>\n<\/td>\n<\/tr>\n


\n<\/table>\n<\/div>\n

\nDidaktische Nachbemerkung
\n<\/h2>\n

Es gibt mehrere M\u00f6glichkeiten, die L\u00f6sung mathematisch abzuleiten und zu begr\u00fcnden. Die bekannteste davon findet sich im Buch „Concrete Mathematics“ von Donald Knuth, Ron Graham und Oren Patashnik. Eine andere Erkl\u00e4rung der L\u00f6sung mit einer sehr netten Animation gibt es bei Numberphile auf YouTube<\/a>.<\/p>\n

Bei beiden Erkl\u00e4rungen gibt es keine unmittelbar einleuchtende Begr\u00fcndung daf\u00fcr, warum in den meisten F\u00e4llen eine zus\u00e4tzliche Person die L\u00f6sungszahl um zwei erh\u00f6ht. Hauptgrund ist, dass man in beiden Ans\u00e4tzen \u00fcber die Nummerierung der Personen, also einen absoluten Bezug spricht. Im obigen Ansatz spielt der Abstand zwischen Startposition und Endposition die wichtigste Rolle, und das ist ein relativer, kein absoluter Bezug. Mein Eindruck ist, dass dieser Wechsel des Beschreibungssystems den L\u00f6sungsweg leichter verst\u00e4ndlich macht.<\/p>\n

<\/a><\/div>","protected":false},"excerpt":{"rendered":"

Eine genaue Beschreibung des Hintergrunds des Problems findet sich in der Wikipedia. Problemstellung: Eine bestimmte Zahl von Personen (n) steht im Kreis. Es gibt eine „Startperson“. Geben wir ihr Nummer 1 und nummerieren wir fortlaufend im Kreis herum. Dann wird jede zweite Person aus dem Spiel genommen und zwar so lange, bis nur mehr eine […]<\/p>\n

<\/a><\/div>","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/posts\/2230"}],"collection":[{"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/comments?post=2230"}],"version-history":[{"count":17,"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/posts\/2230\/revisions"}],"predecessor-version":[{"id":2293,"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/posts\/2230\/revisions\/2293"}],"wp:attachment":[{"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/media?parent=2230"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/categories?post=2230"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.neuwirth.priv.at\/bildungundstatistik\/wp-json\/wp\/v2\/tags?post=2230"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}