Processing math: 100%
 
  Fragen   
Sortierung: 
28.04.2014
 #5
avatar
0

Hallo Dieter,

wenn n=12:

Schrittweite = 1: T(12,1) = 12

Schrittweite = 2: T(12,2) = 9

Schrittweite = 3: T(12,2) = 10

Schrittweite = 4: T(12,2) = 1

Schrittweite = 5: T(12,2) = 1

Schrittweite = 6: T(12,2) = 3

Schrittweite = 7: T(12,2) = 12

Schrittweite = 8: T(12,2) = 5

Schrittweite = 9: T(12,2) = 2

Schrittweite = 10: T(12,2) =5

Schrittweite = 11: T(12,2) = 6

Schrittweite = 12: T(12,2) = 11

n=12: 12, 9, 10, 1, 1, 3, 12, 5, 2, 5, 6, 11 (Schrittweite 1 bis 12)

n=1: 1 (Schrittweite 1 bis 1)

n=2: 2, 1 (Schrittweite 1 bis 2)

n=3: 3, 3, 2 (Schrittweite 1 bis 3)

n=4: 4, 1, 1, 2 (Schrittweite 1 bis 4)

n=5: 5, 3, 4, 1, 2 (Schrittweite 1 bis 5)

n=6: 6, 5, 1, 5, 1, 4 (Schrittweite 1 bis 6)

n=7: 7, 7, 4, 2, 6, 3, 5 (Schrittweite 1 bis 7)

n=8: 8, 1, 7, 6, 3, 1, 4, 4 (Schrittweite 1 bis 8)

n=9: 9, 3, 1, 1, 8, 7, 2, 3, 8 (Schrittweite 1 bis 9)

n=10: 10, 5, 4, 5, 3, 3, 9, 1, 7, 8 (Schrittweite 1 bis 10)

n=11: 11, 7, 7, 9, 8, 9, 5, 9, 5, 7, 7 (Schrittweite 1 bis 11)

n=12: 12, 9, 10, 1, 1, 3, 12, 5, 2, 5, 6, 11 (Schrittweite 1 bis 12)

n=13: 13, 11, 13, 5, 6, 9, 6, 13, 11, 2, 4, 10, 8 (Schrittweite 1 bis 13)

n=14: 14, 13, 2, 9, 11, 1, 13, 7, 6, 12, 1, 8, 7, 13 (Schrittweite 1 bis 14)

...

Berechnung von T(12,2) wenn n = 12 und die Schrittweite = 2 (k=2):

T(1,2)=1T(2,2)=[T(1,2)+2]mod2=(1+2)mod2=1T(3,2)=[T(2,2)+2]mod2=(1+2)mod3=3T(4,2)=[T(3,2)+2]mod2=(3+2)mod4=1T(5,2)=[T(4,2)+2]mod2=(1+2)mod5=3T(6,2)=[T(5,2)+2]mod2=(3+2)mod6=5T(7,2)=[T(6,2)+2]mod2=(5+2)mod7=7T(8,2)=[T(7,2)+2]mod2=(7+2)mod8=1T(9,2)=[T(8,2)+2]mod2=(1+2)mod9=3T(10,2)=[T(9,2)+2]mod2=(3+2)mod10=5T(11,2)=[T(10,2)+2]mod2=(5+2)mod11=7T(12,2)=[T(11,2)+2]mod2=(7+2)mod12=9

Für die Schrittweite 2 gibt es auch eine geschlossene Lösung:

 L(n,2)=1+2n-2^(1+|_lgn_|),

Wobei ... die "Floor"-Funktion bedeutet (Abrundung auf die nächste Ganzzahl).

Und lg ist der Logarithmus zur Basis 2.

n=12:L(12,2)=1+2n21+lg(12)=1+2421+3.5849625=2521+3=2524=2516=9

 

Viele Grüße

S. aus H.

 

links:

http://oeis.org/search?q=12%2C9%2C10%2C1%2C1%2C3%2C12%2C5%2C2%2C5%2C6%2C11&sort=&language=german&go=Suche

http://mathworld.wolfram.com/JosephusProblem.html

28.04.2014
 #3
avatar
0
28.04.2014
 #3
avatar
0
28.04.2014
 #3
avatar
0

Hallo Dieter,

danke für die vielen guten Worte, doch nun zu deiner Osterei-Frage:

"Kannst du eine Formel herleiten, mit der man das Anfangs-Ei  A  berechnen kann, wenn das End-Ei  E gegeben ist ?"

 

I. Die spezielle Formel:

In der Tat gibt es so eine Formel. Wenn A die Anfangs-Ei-Nummer und E die End-Ei-Nummer ist, so lautet

sie: A=E5E=A+5A=E5 bzw. E=A+5

Die Verschiebung um +/- 5 um von A nach E oder von E nach A zu kommen, hattest du ja schon genannt.

Die Formeln oben haben aber einen Haken, sie liefern Werte <=0 für A bzw. >12 für E.

Um Werte für A unter 1 zu vermeiden, addieren wir 12: A=E5+12=E+7

Nun konnen aber Werte 13 oder > 13 auftreten, also müssen wir in diesen Fällen 12 wieder abziehen.

Wir erhalten so die Formel für A: A=E+712E+713

Entsprechend für E: E=A+512A+513

 bedeuten, runde ab auf die nächste Ganzzahl.  813=0  und 1313=1 bzw. 1413=1 mit anderen Worten mache daraus einen Integer.

Die Formeln gelten nur für 12 Ostereier ( n=12 ) und wenn mit 8 abgezählt wird ( k=8 ).

 

II. Die allgemeine Formel:

Ich ersetze in den Formeln die 12 durch n: A=E5+nnE5+nn+1

bzw. E=A+5nA+5n+1

Was uns noch fehlt, ist die Berechnung der "5" aus n=12 und k=8.

Wie wäre der Wert, wenn ich nicht mit 8 abgezählt hätte sondern mit 7 oder 6 etc. Wie wäre der Wert wenn ich nicht 12 Ostereier sondern 13 Ostereier im Kreis auf dem Tisch durchnummeriet hätte oder wenn ich nur 5 Eier in den Kreis gelegt hätte und mit 3 abgezählt hätte?

Für n=12 und k=8 kennen wir den Wert bereits. Er lautet T(12,8)=5. Für n=5 und k=3 lautet der Wert T(5,3)=4.

Gesucht ist also eine Funktion für T(n,k). Hier bin ich im Internet fündig geworden. Die Lösung lautet für den "Josephus elimination process": T(1,k)=1T(n,k)=[T(n1,k)+k]modn

Wenn sich ein Rest 0 ergibt, wird der Wert auf n gesetzt!

Wobei mod die Modulo-Funktion(Restefunktion) bezeichnet. Wenn ich also 7 durch 3 teile ergibt sich ein

Rest von 1. Wenn ich 7 durch 7 teile ergibt sich ein Rest von 0.

 

Die Berechnung von T(12,8)=?:

T(1,8)=1T(2,8)=[T(1,8)+8]mod2=(1+8)mod2=1T(3,8)=[T(2,8)+8]mod3=(1+8)mod3=3T(4,8)=[T(3,8)+8]mod4=(3+8)mod4=3T(5,8)=[T(4,8)+8]mod5=(3+8)mod5=1T(6,8)=[T(5,8)+8]mod6=(1+8)mod6=3T(7,8)=[T(6,8)+8]mod7=(3+8)mod7=4T(8,8)=[T(7,8)+8]mod8=(4+8)mod8=4T(9,8)=[T(8,8)+8]mod9=(4+8)mod9=3T(10,8)=[T(9,8)+8]mod10=(3+8)mod10=1T(11,8)=[T(10,8)+8]mod11=(1+8)mod11=9T(12,8)=[T(11,8)+8]mod12=(9+8)mod12=5

T(12,8)=5.

Nun können wir unsere Formeln allgemein schreiben:

A=ET(n,k)+nnET(n,k)+nn+1

E=A+T(n,k)nA+T(n,k)n+1

Viele Grüße

S. aus H.

28.04.2014
27.04.2014

4 Benutzer online