Wie viele Kombinationen gibt es bei einem 5 stelligen Fahrradschloss?

09.01.2019, 15:58

Beautydonut

Wie viele Kombinationen gibt es bei einem 5 stelligen Fahrradschloss?

Meine Frage:
Wie bestimmt man die Anzahl an Kombinationen bei einen 5 stelligen fahrradschloss

Meine Ideen:
10 000 kombinationen

09.01.2019, 20:41

Dopap

Auf diesen Beitrag antworten »

Das Fachwort ist Variationen mit Wiederholungen/Zurücklegen

$\begin{eqnarray*} V=10^5=100~000 \end{eqnarray*}$ falls alle Ziffern möglich sind.

10.01.2019, 22:10

Pippen

Auf diesen Beitrag antworten »

Mich würde folgendes interessieren: Wenn wir annähmen, wir probierten zufällig Kominbationen aus, ab welcher Anzahl an Versuchen wäre die Wahrscheinlichkeit für den Treffer größer oder gleich 50%. Was rechnet man da wie?

10.01.2019, 22:29

tbcosinus

Auf diesen Beitrag antworten »

RE: Wie viele Kombinationen gibt es bei einem 5 stelligen Fahrradschloss?

Zitat:

Original von Beautydonut
Meine Frage:
Wie bestimmt man die Anzahl an Kombinationen bei einen 5 stelligen fahrradschloss

Meine Ideen:
10 000 kombinationen

Die Anzahl der Kombinationen ist gleich die Anzahl der Symbole pro Stelle hoch Anzahl der Stellen. Bietet das Fahrradschloss bei jeder Stelle die möglichen Ziffern 0-9 hat man also 10^5 Möglichkeiten.

11.01.2019, 00:36

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen
Mich würde folgendes interessieren: Wenn wir annähmen, wir probierten zufällig Kominbationen aus, ab welcher Anzahl an Versuchen wäre die Wahrscheinlichkeit für den Treffer größer oder gleich 50%. Was rechnet man da wie?

$\begin{eqnarray*} 1-\left(1-\frac{1}{10^5}\right)^n >\frac 12\Rightarrow n=69315 \end{eqnarray*}$

11.01.2019, 07:33

HAL 9000

Auf diesen Beitrag antworten »

@Dopap

Das wäre "vergessliches" Probieren.

"Systematisches" Durchprobieren (d.h. keine Variation wird mehr als einmal probiert) ergibt, dass man in $\begin{eqnarray*} k \end{eqnarray*}$ Versuchen Wahrscheinlichkeit $\begin{eqnarray*} \frac{k}{n} \end{eqnarray*}$ hat, eine unbekannte Variation zu erwischen.

Demzufolge benötigt man für genau 50% Wahrscheinlichkeit auch genau 50000 Versuche.

11.01.2019, 08:09

Dopap

Auf diesen Beitrag antworten »

ja, schon klar, nur

Zitat:

Original von Pippen
[...] Wenn wir annähmen, wir probierten zufällig Kominbationen aus, [...]

11.01.2019, 08:32

tbcosinus

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
ja, schon klar, nur

Zitat:

Original von Pippen
[...] Wenn wir annähmen, wir probierten zufällig Kominbationen aus, [...]

Heißt also hier wird sich NICHT gemerkt was man schon vorher durchprobiert hat? Dann hat man doch bei jeder neuen Ziehung wieder 10^5 Möglichkeiten und somit bei jedem Probieren eine Wahrscheinlichkeit von 10^-5

11.01.2019, 08:59

HAL 9000

Auf diesen Beitrag antworten »

@Dopap

Ich könnte jetzt einwenden, dass "zufällig" viel bedeuten kann: Es könnte z.B. auch sein, dass man zufällig eine Permutation der 100000 möglichen Variationen auswürfelt und die dann nacheinander durchgeht. Augenzwinkern

Aber du hast Recht, i.a. meint man damit schon das, was du gedacht hast. Ich kenne eine solche Problemstellung übrigens in dem Kontext "Pförtner, der den richtigen Schlüssel in seinem Schlüsselbund sucht", einmal in der Normalvariante (jeder Schlüssel wird nur einmal probiert) und in der besoffenen Variante ("zufälliges" Probieren).

11.01.2019, 10:18

Dopap

Auf diesen Beitrag antworten »

die Frage ist doch wie bei Vielem, wieviel Mathematik und wieviel "Sachaufgabe" steckt darin?

Praktisch würde ich erst mit 12345 starten und weiter mit 31415/27182 - falls Mathematikerfahrrad - und in Folge systematisch und ohne Aufschrieb "durchdrehen". Augenzwinkern

11.01.2019, 10:30

HAL 9000

Auf diesen Beitrag antworten »

Basierend auf dem Goldenen Schnitt schlage ich vor, in Versuch $\begin{eqnarray*} k \end{eqnarray*}$ die Variation $\begin{eqnarray*} v_k = 38197k \bmod 100000 \end{eqnarray*}$ zu nehmen. Big Laugh

38197
76394
14591
52788
90985
29182
...

Sieht auf den ersten Blick "zufällig" aus, ist es aber natürlich nicht, und es gibt keine Wiederholung, solange nicht alle Variationen "durch" sind. Augenzwinkern

11.01.2019, 20:32

Pippen

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap

Zitat:

$\begin{eqnarray*} 1-\left(1-\frac{1}{10^5}\right)^n >\frac 12\Rightarrow n=69315 \end{eqnarray*}$

Aha. Die Formel verstehe ich sogar: Wir gehen also von der Wahrscheinlichkeit aus, nicht die richtige Kombination zu erwischen (1 - (1/10^5) und wg. Unabhängigkeit der Ereignisse kann pro Versuch damit multipliziert werden und dann schauen wir einfach, wann diese "Wahrscheinlichkeit der Nieten" die 50%-Marke unterschreitet, genau dann wäre die Gegenwahrscheinlichkeit, also die richtige Kombi zu treffen, auch 50%.

Wie sähe die aus, wenn wir systematisch zufällig probieren, d.h. keine doppelten Proben? Wenn ich es richtig verstehe, dann gilt immer noch Dopap's Weg, aber er wäre blind für die Zusatzinfo, dass doppelte Proben ausgeschlossen sind, so dass das Ergebnis verfälscht sein könnte. Wie würde stattdessen der Lösungweg aussehen? Hal's kurze Bemerkung verstehe ich nicht ganz: k-Versuche und k/n?!? verwirrt

11.01.2019, 20:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen
Hal's kurze Bemerkung verstehe ich nicht ganz: k-Versuche und k/n?!? verwirrt

Das ganze ist natürlich im vorliegenden Fall mit n=100000 gemeint. Und einfach mal alles lesen, dann kapiert man es auch.

11.01.2019, 22:27

Pippen

Auf diesen Beitrag antworten »

Ich versuchs mal: Nehmen wir mal nur ein Schloss mit 2 Stellen, als 100 Kombinationen, das Prinzip bleibt ja gleich.

1) Zunächst wahlloses Rumprobieren, also mit evtl. Wiederholungen. Hier nimmt man die Dopap-Formel und kommt darauf, dass 69maliges Probieren eine Wahrscheinlichkeit von ganz wenig über 50% für das Knacken des Schlosses ergibt.

2) Jetzt Rumprobieren unter Ausschluss von Wiederholungen.

Im ersten Versuch habe ich eine Nietenwahrscheinlichkeit von 99/100.
Im zweiten Versuch habe ich nur noch eine Nietenwahrscheinlichkeit von 98/99. (erste Niete wird aufgeschrieben und fliegt damit raus, wird nicht mehr beachtet)
Im dritten Verusch habe ich nur noch eine Nietenwahrscheinlichkeit von 97/98. (zweite Niete fliegt raus)
...
Im 99. Versuch habe ich eine Nietenwahrscheinlichkeit von 1/2, also auch 1/2 Erfolgswahrscheinlichkeit. Nach diesem Modell muss ich also 99mal rumprobieren, um das Schloss mit 50% Wahrscheinlichkeit zu knacken, wenn ich Wdh. ausschließe.

Danach wäre Methode 1) klar vorzuziehen, allerdings scheint mir 2) falsch oder was Anderes zu sein als Hal meinte. Wo läuft da was schief?

12.01.2019, 00:16

klauss

Auf diesen Beitrag antworten »

Ich versuche mal die bisherigen Erkenntnisse zusammenzufassen bzw. zu ergänzen (2 Stellen):

1) Wahlloses Probieren

Ab 69 Versuchen ist die Wahrscheinlichkeit für das Knacken des Schlosses größer als 50 %.

2) Probieren ohne Wiederholung, ansonsten ohne Präferenzen

a) Wahrscheinlichkeit, genau beim k-ten Versuch das Schloß zu knacken.
Sei k = 50.

$\begin{align*} P(X=k)=\frac{99}{100} \cdot \frac{98}{99} \cdot \frac{97}{98} \cdot ...\cdot \frac{52}{53}\cdot \frac{51}{52}\cdot \frac{1}{51} = \frac{1}{100} ! \end{align*}$

Man prüfe selbst nach, dass dieses Ergebnis für alle k von 1 bis 100 gleich ist.
Der Erwartungswert für die Anzahl der Versuche bis zum Knacken des Schlosses müßte demnach 50,5 sein.

b) Wahrscheinlichkeit, spätestens beim k-ten Versuch das Schloß zu knacken.
Sei k = 50.

$\begin{align*} P(X\leq k)=\frac{1}{100} +\frac{99}{100}\cdot \frac{1}{99} +\frac{99}{100} \cdot \frac{98}{99}\cdot \frac{1}{98} +\frac{99}{100} \cdot \frac{98}{99}\cdot \frac{97}{98}\cdot ...\cdot \frac{52}{53}\cdot \frac{51}{52} \cdot \frac{1}{51} =\frac{1}{100} +\frac{1}{100} +...=\frac{50}{100}=\frac{1}{2} \end{align*}$

Aha. Die Wahrscheinlichkeit, spätestens beim 100. Versuch das Schloß zu knacken, muß ja schließlich 1 sein.

Epilog:

Zitat:

Original von Pippen
Im 99. Versuch habe ich eine Nietenwahrscheinlichkeit von 1/2, also auch 1/2 Erfolgswahrscheinlichkeit.

Bedingte Wahrscheinlichkeit unter der Voraussetzung, dass die ersten 98 Versuche Nieten waren.

Kann man das alles so stehenlassen?

Muß die Annahme

Zitat:

Original von Pippen
Danach wäre Methode 1) klar vorzuziehen

aufrechterhalten oder verworfen werden?

12.01.2019, 00:22

tbcosinus

Auf diesen Beitrag antworten »

Zitat:

Original von klauss
1) Wahlloses Probieren

Ab 69 Versuchen ist die Wahrscheinlichkeit für das Knacken des Schlosses größer als 50 %.

Hier zu hab ich mal eine Frage: wenn ich wahllos herumprobiere, hab ich dann nicht immer wieder bei jedem neuen Versuch eine Wahrscheinlichkeit von 1/100 die richtige Zahl von 0 bis 99 zu treffen?

12.01.2019, 00:38

klauss

Auf diesen Beitrag antworten »

Zitat:

Original von tbcosinus
bei jedem neuen Versuch eine Wahrscheinlichkeit von 1/100

Richtig, wir ziehen ja "mit Zurücklegen". Diese Erkenntnis ist aber auch in Dopaps Formel schon enthalten.

12.01.2019, 00:55

tbcosinus

Auf diesen Beitrag antworten »

Aber wieso soll ich dann beim 69. Versuch dann auf einmal eine Wahrscheinlichkeit von 0,5 haben? verwirrt

Egal wie viele Versuche ich habe, die Wahrscheinlich bleibt doch immer 1/100 wenn ich zufällig immer aus 100 neu ziehe - "der Zufall hat kein Gedächtnis" pflegte mein Mathelehrer stets zu sagen Lehrer

12.01.2019, 01:46

klauss

Auf diesen Beitrag antworten »

Auch hier: 1/100 ist die bedingte Wahrscheinlichkeit, genau beim 69. (oder k-ten) Versuch die richtige Kombination zu treffen. Aber die Gesamtwahrscheinlichkeit, 69 mal hintereinander eine Niete zu ziehen, ist kleiner als 0,5.

12.01.2019, 01:52

tbcosinus

Auf diesen Beitrag antworten »

Ah danke, so hab ich das noch garnicht betrachtet. Es ist also ein Treffer beim 69. (wahllosen zufälligen) Versuch wahrscheinlicher, als eine Niete. Freude

12.01.2019, 01:54

Dopap

Auf diesen Beitrag antworten »

"meine" Formel besagt:

bei 69 Zufallsversuchen an einem Schloss mit 2 Rädchen habe ich das Schloss mit p=0.5 mindestens einmal geknackt.

Ereignisse immer genau definieren!

12.01.2019, 02:00

tbcosinus

Auf diesen Beitrag antworten »

Richtig. Man kann ja schon mindestens 1x bei den vorherigen 68 Versuchen zufällig die richtige Kombination erwischt haben.

12.01.2019, 02:31

mYthos

Auf diesen Beitrag antworten »

Die nächsten Beiträge betrafen ein neues Thema.
Deswegen wurde der Thread geteilt.

mY+

12.01.2019, 03:02

Pippen

Auf diesen Beitrag antworten »

Ich vereinfach noch weiter: Wir nehmen den Traum jedes Fahrraddiebes an, nämlich ein einstelliges Fahrradschloss, also nur 10 Kombinationen.

1) Probieren mit Wiederholung

Dopap's Formel sagt uns, dass wir nach 7 Versuchen mit über 50%iger Wahrscheinlichkeit mindestens einmal das Schloss geknackt hätten.

2) Probieren ohne Wiederholung

Da rechne ich mit Dopap's Formel, nur dass die Anzahl der Möglichkeiten mit der Anzahl der Versuche runtergeht, weil ja Wdh. ausgeschlossen sein sollen: Die Wahrscheinlichkeit für Nieten liegt bei 5 Versuchen bei 9/10 * 8/9 * 7/8 * 6/7 * 5/6 = 1/2, also die Gegenwahrscheinlichkeit (Knacken des Schlosses) = 1/2. Wir brauchen also hier nur 5 Versuche bis zur 50%-Wahrscheinlichkeit mindestens einmal das Schloss zu knacken.

Ich denke, das habe ich jetzt konzeptionell verstanden. Das Problem bei 2) ist nun die Formel zum Ausrechnen, wenn's um zB 100.000 Kombinationen geht, da kann ich nicht mehr so rechnen wie bei 2). Wie lautet diese Formel? Da gibt's doch bestimmt irgendeinen Shortcutbinomialhypergeometrischendingsbumsweg.

p.s. Man merkt auf jeden Fall nebenbei, dass Passwörter ziemlich lang sein müssen, damit sie nicht durch Bots geknackt werden können. Eine 5-stellige Zahl wäre ziemlich leicht zu knacken, selbst eine 10-stellige Zahl wohl kein Problem, erst ab einer 20-stelligen Zahl dürfte ein Hacker mit Bothilfe an seine Grenzen kommen.

12.01.2019, 03:27

tbcosinus

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen
2) Probieren ohne Wiederholung

Da rechne ich mit Dopap's Formel, nur dass die Anzahl der Möglichkeiten mit der Anzahl der Versuche runtergeht, weil ja Wdh. ausgeschlossen sein sollen: Die Wahrscheinlichkeit für Nieten liegt bei 5 Versuchen bei 9/10 * 8/9 * 7/8 * 6/7 * 5/6 = 1/2, also die Gegenwahrscheinlichkeit (Knacken des Schlosses) = 1/2. Wir brauchen also hier nur 5 Versuche bis zur 50%-Wahrscheinlichkeit mindestens einmal das Schloss zu knacken.

Ich denke, das habe ich jetzt konzeptionell verstanden. Das Problem bei 2) ist nun die Formel zum Ausrechnen, wenn's um zB 100.000 Kombinationen geht, da kann ich nicht mehr so rechnen wie bei 2). Wie lautet diese Formel? Da gibt's doch bestimmt irgendeinen Shortcutbinomialhypergeometrischendingsbumsweg.

Du hast also:

$\begin{eqnarray*} P_5 = \frac{9}{10}*\frac{8}{9}*\frac{7}{8}*\frac{6}{7}*\frac{5}{6} = \frac{\frac{9!}{4!}}{\frac{10!}{5!}} \end{eqnarray*}$

Das sieht mir stark nach dem hier verallgemeiert nach n aus:

$\begin{eqnarray*} P_n = \frac{\frac{(n-1)!}{(0,5n-1)!}}{\frac{n!}{(0,5n)!}} \end{eqnarray*}$

edit: Klammer korrigiert

12.01.2019, 04:09

klauss

Auf diesen Beitrag antworten »

Zitat:

Original von tbcosinus
Das sieht mir stark nach dem hier verallgemeiert nach n aus:
$\begin{eqnarray*} P_n = \frac{\frac{(n-1)!}{(0,5n-1)!}}{\frac{n!}{(0,5n)!}} \end{eqnarray*}$

So wirds nicht gehen, zumal was soll unter anderen Bedingungen bei ungeradem n passieren?

Die Wahrscheinlichkeit, bei k Versuchen mindestens 1 Treffer zu erzielen, sehe ich bei
$\begin{align*} 1-\frac{(n-1)!}{(n-k-1)!} \cdot \frac{(n-k)!}{n!}=1-\frac{n-k}{n}=1-\left(1-\frac{k}{n} \right)=\frac{k}{n} \end{align*}$
mit dem Spezialfall
$\begin{align*} k=\frac{n}{2} \end{align*}$

12.01.2019, 05:09

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen

2) Probieren ohne Wiederholung
Die Wahrscheinlichkeit für Nieten liegt bei 5 Versuchen bei 9/10 * 8/9 * 7/8 * 6/7 * 5/6 = 1/2, also die Gegenwahrscheinlichkeit (Knacken des Schlosses) = 1/2. Wir brauchen also hier nur 5 Versuche bis zur 50%-Wahrscheinlichkeit mindestens einmal das Schloss zu knacken.

nicht mindestens sondern genau einmal.

der Preis bei gedächtnislosen Versuchen ist die höhere Anzahl der Versuche. Zum Ausgleich gibt's dafür die Möglichkeit von Mehrfachtreffer.
bei systematischen Versuchen ist die Anzahl geringer, nur ist der Preis dann eben nur genau ein Treffer

Bem: für einen Fahrraddieb ist selbstredend die Möglichkeit von Mehrfachtreffern ziemlicher Unfug. Augenzwinkern

12.01.2019, 13:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von klauss
Die Wahrscheinlichkeit, bei k Versuchen mindestens 1 Treffer zu erzielen, sehe ich bei [...] $\begin{align*} \frac{k}{n} \end{align*}$

Sag ich doch seit gestern, und man kann es noch einfacher begründen: Mit $\begin{eqnarray*} k \end{eqnarray*}$ Versuchen, in denen keine Variation wiederholt probiert wird, hat man genau $\begin{eqnarray*} k \end{eqnarray*}$ Variationen von $\begin{eqnarray*} n \end{eqnarray*}$ abgegrast. Da jede der $\begin{eqnarray*} n \end{eqnarray*}$ Variationen mit gleicher Wahrscheinlichkeit die gesuchte sein kann, hat man mit Wahrscheinlichkeit $\begin{eqnarray*} \frac{k}{n} \end{eqnarray*}$ damit die gesuchte bis dahin gefunden - man muss nicht immer so kompliziert denken. Augenzwinkern

12.01.2019, 14:12

Dopap

Auf diesen Beitrag antworten »

auch hier stört mich bei Klauss das Wort mindestens

12.01.2019, 14:19

HAL 9000

Auf diesen Beitrag antworten »

Es ist nicht falsch, auch wenn unter diesen Bedingungen "mindestens" eben immer "genau" ist.

12.01.2019, 16:26

Dopap

Auf diesen Beitrag antworten »

zwei Fragen zu:

Zitat:

Original von HAL 9000
Basierend auf dem Goldenen Schnitt schlage ich vor, in Versuch $\begin{eqnarray*} k \end{eqnarray*}$ die Variation $\begin{eqnarray*} v_k = 38197k \bmod 100000 \end{eqnarray*}$ zu nehmen.

wie begründet man diese Sache mit dem goldenen Schnitt ? Warum 38197?
diese Funktion $\begin{eqnarray*} f: [0,1,2,\dots,99999] \to [0,1,2,\dots,99999] \,\, \text{mit}\,\, x\mapsto 38197\cdot x \,\,mod\, 10^5 \end{eqnarray*}$ ist bijektiv.
Lässt sich die Umkehrfunktion ebenso leicht angeben?

12.01.2019, 16:40

HAL 9000

Auf diesen Beitrag antworten »

Das war ein Witz mit dem Goldenen Schnitt... Man kann auch einfach folgende Strategie nehmen:

Man würfelt die erste Kombination aus, und testet dann diese und die 99999 Folgekombinationen durch (auf 99999 folgt natürlich per Wraparound 00000).

Zitat:

Original von Dopap
diese Funktion $\begin{eqnarray*} f: [0,1,2,\dots,99999] \to [0,1,2,\dots,99999] \,\, \text{mit}\,\, x\mapsto 38197\cdot x \,\,mod\, 10^5 \end{eqnarray*}$ ist bijektiv.
Lässt sich die Umkehrfunktion ebenso leicht angeben?

$\begin{eqnarray*} f^{-1}(k) = 53533\cdot k\bmod 10^5 \end{eqnarray*}$

12.01.2019, 18:13

tbcosinus

Auf diesen Beitrag antworten »

Zitat:

Original von DopapBem: für einen Fahrraddieb ist selbstredend die Möglichkeit von Mehrfachtreffern ziemlicher Unfug. Augenzwinkern

Deswegen ist dieser Fall mit wahllosem Herumprobieren auch total absurd. Wer eine Art BruteForce Script so zusammentippern täte und sich die bereits versuchten Kombis nicht merkt und nochmal quasi per Zufall durchprobiert hat das Thema verfehlt. Big Laugh

Neue Frage »

Antworten »

Wie viele Kombinationen gibt es bei einem 5 stelligen Fahrradschloss?

Verwandte Themen