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)=1\\
T(2,2) =[T(1,2)+2] \bmod 2=(1+2) \bmod 2=1\\
T(3,2) =[T(2,2)+2] \bmod 2=(1+2) \bmod 3=3\\
T(4,2) =[T(3,2)+2] \bmod 2=(3+2) \bmod 4=1\\
T(5,2) =[T(4,2)+2] \bmod 2=(1+2) \bmod 5=3\\
T(6,2) =[T(5,2)+2] \bmod 2=(3+2) \bmod 6=5\\
T(7,2) =[T(6,2)+2] \bmod 2=(5+2) \bmod 7=7\\
T(8,2) =[T(7,2)+2] \bmod 2=(7+2) \bmod 8=1\\
T(9,2) =[T(8,2)+2] \bmod 2=(1+2) \bmod 9=3\\
T(10,2)=[T(9,2)+2] \bmod 2=(3+2) \bmod 10=5\\
T(11,2)=[T(10,2)+2] \bmod 2=(5+2) \bmod 11=7\\
\textcolor[rgb]{1,0,0}{T(12,2)=}[T(11,2)+2] \bmod 2=(7+2) \bmod 12=\textcolor[rgb]{1,0,0}{9}\\$$

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

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

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

Und lg ist der Logarithmus zur Basis 2.

$$n=12: \textcolor[rgb]{1,0,0}{L(12,2)=} 1 + 2*n - 2^{1+\lfloor lg(12) \rfloor}=1+24-2^{1+\lfloor 3.5849625 \rfloor}=25-2^{1+3}=25-2^4=25-16=\textcolor[rgb]{1,0,0}{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 = E - 5
E = A + 5$$
$$A = E - 5$$ 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 = E - 5 + 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 + 7 - 12*\lfloor{\frac{E+7}{13}}\rfloor$$

Entsprechend für E: $$E = A + 5 - 12*\lfloor{\frac{A+5}{13}}\rfloor$$

$$\lfloor \rfloor$$ bedeuten, runde ab auf die nächste Ganzzahl.  $$\lfloor \frac{8}{13}\rfloor = 0$$  und $$\lfloor \frac{13}{13}\rfloor = 1$$ bzw. $$\lfloor \frac{14}{13}\rfloor = 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 = E-5+n-n*\lfloor{\frac{E-5+n}{n+1}}\rfloor$$

bzw. $$E = A+5-n*\lfloor{\frac{A+5}{n+1}}\rfloor$$

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) = 1\\ T(n, k) = [T(n-1, k)+k] \bmod n$$

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

Wobei $$\bmod$$ 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)=1\\
T(2,8)=[T(1,8)+8]\bmod 2 =(1+8)\bmod 2=1\\
T(3,8)=[T(2,8)+8]\bmod 3 =(1+8)\bmod 3=3\\
T(4,8)=[T(3,8)+8]\bmod 4 =(3+8)\bmod 4=3\\
T(5,8)=[T(4,8)+8]\bmod 5 =(3+8)\bmod 5=1\\
T(6,8)=[T(5,8)+8]\bmod 6 =(1+8)\bmod 6=3\\
T(7,8)=[T(6,8)+8]\bmod 7 =(3+8)\bmod 7=4\\
T(8,8)=[T(7,8)+8]\bmod 8 =(4+8)\bmod 8=4\\
T(9,8)=[T(8,8)+8]\bmod 9 =(4+8)\bmod 9=3\\
T(10,8)=[T(9,8)+8]\bmod 10 =(3+8)\bmod 10=1\\
T(11,8)=[T(10,8)+8]\bmod 11 =(1+8)\bmod 11=9\\
T(12,8)=[T(11,8)+8]\bmod 12 =(9+8)\bmod 12=5\\$$

T(12,8)=5.

Nun können wir unsere Formeln allgemein schreiben:

$$A=E-T(n,k)+n-n*\lfloor{\frac{E-T(n,k)+n}{n+1}}\rfloor$$

$$E = A+T(n,k)-n*\lfloor{\frac{A+T(n,k)}{n+1}}\rfloor$$

Viele Grüße

S. aus H.

28.04.2014
27.04.2014

1 Benutzer online