Forums Neueste Beiträge
 

Ich möchte etwas beweisen - Josephus oder allgemeiner "Auszählfolgen"

29/09/2010 - 17:53 von siggi | Report spam
Moin moin Ihr!

Dieses ist keine Übungsaufgabe oder ànliches,
ich mache das just for fun ...
(Soll es geben! Die spinnen, die Mathematiker ... ;o) )

Ich möchte etwas beweisen -- siehe gleich --,
weiß aber nicht recht wie!?

Gesucht, die vollstàndige Induktion
für folgendes Problem:

Stichwort: Josephus

Es stehen Personen im Kreis und (z.B.)
jeder m. - hier m=3 - wird ausgezàhlt
(wie beim Kinderreim "ene mem muh, raus bis du "
mit einer gewissen Anzahl m von Silben):

Bei 5 Personen:
der Reihe nach also (3 1 5 2 4),
eine Permutation von (1 2 3 4 5).
Aus bestimmten Gründen beginne ich aber nun mit Null "0"
und erhalte -- klar! - (01234) ==> (20413).
Bei 6 Personen (von 0 gezàhlt) bekommt man die Auszàhlreihenfolge:
253140, bei 7 dann 2516403 u.s.w.

Eine Liste (beginnend mit der lfd. Nr. 0, einer Person --" der 0")
liefert etwas übersichtlicher:

0 0
1 01
2 201
3 2130
4 20413
5 253140
6 2516403
7 ...
...
n-1 ...
...

Das gleiche kann man mit verschiedenen "m" machen,
wodurch man ggf. sieht, daß die erste Ziffer der Aufstellung
sich ergibt zu (m-1) mod (n+1) .

Diese Auflistung kann auch als untere Dreieckmatrix gelesen werden:
U = ( u(i,j) ) mit i=0,...,n-1 und j=0,...,n-1 und
u(i,j) = 0 für j>i
u(i,0) = (m-1) mod (i+1), i=0,1,2,3,...
u(i+1,j+1)= [ m+u(i,j) ] mod (i+1)

Durch u(i,0)= (m-1) mod (i+1) wird man zu
u(i+1,j+1)= [ m+u(i,j) ] mod (i+1) animiert

Nun, man könnte natürlich auch die Definition der u(i,j)
als vorgegeben betrachten,
dann ergibt sich U eben aus dieser Definition.
Andererseits, erfüllen die Zeilen
u(i=n,j) für j=1,2,...,n aber offenbar auch gerade
die "Auszàhlreihenfolge" für (n+1) Personen
wie sich zeigt (jeweils) für beliebiges m (aus IN).

Aber, wie beweise ich das?

Meine bisher am erfolgreichsten scheinende Idee ist:

Betrachte für (irgendein) n 0 1 2 3 ... n n+1 um (m-1) verschoben,
also 2 3 ... n n+1 0 1 , und eine entsprechende Zeile aus U, die die
Auszàhlfolge für n ist. Wenn wir diese "Anwenden" - die dadurch
gegebene
Permutation nachvollziehen -- auf
(2) 3 ... n n+1 0 1 - mit ja "nur n Personen" -,
dann erhàlt man tatsàchlich die entsprechende Zeile aus U zu n+1!

So etwas kann man sicher formal (Permutationsschreibweise)
aufschreiben.
Ich kann aber einfach keinen Zusammenhang mit der Frage sehen, daß das
die Identitàt mit der (n+1). Auszàhlfolge beweisen würde.


Bitte -- bin ich nur blind? -,
warum paßt U so gut zur Auszàhlfolgen,
und wie beweise ich das eben???


Wer kann helfen.


Wie immer
mit freundlichen Grüßen

Siggi N. - Hamburg / Harburg ...
... der Stadt mit der größten Vorstadt der Welt!
 

Lesen sie die antworten

#1 Vogel
30/09/2010 - 03:38 | Warnen spam
siggi wrote in news:4186053b-aa35-4632-802f-
:

Moin moin Ihr!

Dieses ist keine Übungsaufgabe oder ànliches,
ich mache das just for fun ...
(Soll es geben! Die spinnen, die Mathematiker ... ;o) )

Ich möchte etwas beweisen -- siehe gleich --,
weiß aber nicht recht wie!?



Du weisst anscheinend auch nicht recht was du beweisen willst.



Ein kurze pràgnante und klare Schilderung deinerseits wàre da hilfreich.

Ähnliche fragen