Kombinatorik Frage(Entsperrmuster)?
Wie viele mögliche Kombinationen gibt es für ein normales 3x3 Entsperrmusterfeld?
Auch ein einzelner Punkt stellt in diesem Szenario eine mögliche Kombination da.
4 Antworten
Wieso 3x3x3? Ich sehe nur 3x3. Wieviele Punkte darf man ansteuern und darf man einen Punkt mehrmals anfahren?
Und wieviele Punkte darf man ansteuern? Also wenn es 9 Punkte sind und man k davon ansteuern darf, wobei alle verschieden sein müssen, dann sind das Variationen ohne Wiederholungen, also 9!/(9-k)!. Man kann es auch berechnen als 9·8· ... · (10-k). Begründung: Zuerst hast du die freie Wahl aus neun Punkten, dann noch aus acht, dann noch aus sieben usw.
Ich denke du meinst 3×3 statt 3x3x3.
======
Mit genau einem Punkt:
9
Mit genau zwei Punkten:
9 * 8 = 72
... und so weiter ...
Mit genau neun Punkten:
9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362880
======
Summiert man das auf erhält man:
9 + 9 * 8 + ... + 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 986409
======
Ergebnis:
986409
Wie kommst du auf 986409? Nach deinem Rechenverfahren würde ich auf 146966400 kommen
Ich habe meinen PC rechnen lassen ...
9+9*8+9*8*7+9*8*7*6+9*8*7*6*5+9*8*7*6*5*4+9*8*7*6*5*4*3+9*8*7*6*5*4*3*2+9*8*7*6*5*4*3*2*1
Ergebnis:
986409
Bzw. habe ich eigentlich meinen PC das so rechnen lassen ...
sum(9!/k!, k=0..8)
Diese Berechnungen kannst du beispielsweis auch einfach in WolframAlpha reinkopieren und das rechnen lassen.
Doch! Summieren!
Kleines Beispiel, damit es übersichtlicher bleibt. Angenommen man hat 3 Punkte, statt 9. Diese Punkte bezeichne ich mit a, b und c. Dann gibt es die folgenden Kombinationen:
a
b
c
ab
ac
ba
bc
ca
cb
abc
acb
bac
bca
cab
cba
Das sind 3 + 3 * 2 + 3 * 2 * 1 = 3 + 6 + 6 = 15 mögliche Muster.
Bei deiner Berechnungsmethode, Lamanini, würdest du jedoch nur 3 * 2 * 1 = 6 Muster erhalten, was jedoch falsch wäre.
Mh, das klingt logisch. Aber irgendwie kenn ich das auch anders.
Also ich kenne das aus der IT so:
Man berechnet das mit der maximalen Größe, hier 9!
Es gibt zwar mehr Möglichkeiten, aber die machen logischerweise nur ca. 1% der Möglichkeiten aus, und sind daher vernachlässigbar.
Da gibts also nur eine Möglichkeit: Selbst probieren und aufschreiben, wie viele Möglichkeiten es gibt ^^
Man berechnet das mit der maximalen Größe, hier 9!
Es gibt zwar mehr Möglichkeiten, aber die machen logischerweise nur ca. 1% der Möglichkeiten aus, und sind daher vernachlässigbar.
Also, ich habe nicht so viel mit IT zu tun, aber sehr wohl und sehr viel mit Mathematik. Und wenn ich mir deine Aussage so anschaue, die du aus der IT zu kennen scheinst, dann ist diese offensichtlich falsch. Denn die so vernachlässigten Fälle machen in hier betrachteten konkreten Fall etwa 63% der Möglichkeiten aus und sind daher nicht vernachlässigbar.
Hier eine Textdatei, in der alle 986409 Muster aufgeführt sind.
https://www.dropbox.com/s/kk4coms4v9v9ydw/alleMuster.txt?dl=0
(Die einzelnen Punkte wurden mit den Ziffern von 1 bis 9 durchnummeriert.)
Ja, ich sehe. Könnt ihr mir helfen meinen Denkfehler zu finden?
Ich hätte jetzt gesagt: Wenn man z.B. nur alle Möglichkeiten mit 8 Punkten erfüllen würde, hätte man eine Zahl an Möglichkeiten, sagen wir mal z. Um das für 9 Punkte zu berechnen, gibt es 9 Möglichkeiten diesen "an den Anfang" ranzuhängen. Also 9z Möglichkeiten. Das addiert ergibt 10z. Dadurch würde jetzt bei mir die 8 Punkte Lösungen nur 10% ausmachen.
Demnach würden auch die 7 Punkte Lösung nur 10% der 8 Punkte Lösung ausmachen usw.
Wo liegt mein Fehler?
Prinzipiell korrekt - wenn die Muster so frei gezeichnet werden könn(t)en.
Ich denke aber, dass manche Muster nicht möglich sind:
Beispiel (wenn "1" links oben ist und "9" rechts unten):
1-9-3 ist nicht möglich, da 1-9 vom Handy schon als 1-3-9 interpretiert wird.
Vielleicht verstehe ich es aber auch falsch.
Also nach meiner Zählweise ...
1 2 3
4 5 6
7 8 9
... wäre 1-9-5 nicht möglich, da beim Zeichnen von 1-9 bereits die 5 markiert wird und danach nicht mehr markiert werden kann. Das meinst du, oder? Da hast du natürlich recht das habe ich nicht beachtet.
Dann muss ich meine Berechnung dementsprechend anpassen. Ich muss nur nochmal genauer prüfen, ob 1-9 wirklich bereits als 1-5-9 interpretiert wird, oder ob 1-9 und 1-5-9 unterschieden werden. Kann aber sein, dass ich erst heute Abend dazu kommen.
Ich habe jetzt bei den Mustern diejenigen gestrichen, die ein 123, 159, 147, 258, 321, 357, 369, ... enthalten, da diese bereits duch die Muster mit 13, 19, 17, ... abgedeckt sind. Außerdem habe ich diejenigen gestrichen, bei der nach einem 13 noch irgendwann eine 2 kommt bzw. nach einem 19 noch irgendwann eine 5 kommt, etc. Diese Muster sind nich möglich, da nach Zeichnen von 13 die 5 markiert wird, wenn diese nicht schon zuvor markiert gewesen ist, und die 5 daher danach nicht mehr zur Verfügung steht.
Nach Streichen der entsprechenden gleichwertigen bzw. nicht möglichen Muster, erhalte ich noch 497519 gültige Muster. Diese 497519 Muster sind hier in einer Textdatei zu finden:
https://www.dropbox.com/s/c5bxtff3npgdjlb/muster_neu.txt?dl=0
Bzw. da mein Smartphone nur Muster mit mindestens 4 markierten Punkten zulässt, habe ich hier auch nochmal eine entsprechende Textdatei mit mindestens 4 markierten Punkten erstellt:
https://www.dropbox.com/s/jl8kanpjk6e069d/muster_neu4.txt?dl=0
Das sind dann nur 497134 Muster. Wobei ja in der Fragestellung steht, dass sogar einpunktige Muster zugelassen sind, weshalb die Lösung dann nicht 497134 ist, sondern eher 497519.
[Die Anzahlen habe ich nicht von Hand mit irgendeiner Formel berechnet. Das wäre mir zu anstrengend gewesen. Ich habe einfach ein kleines Python-Programm geschrieben, welches mir alle Möglichkeiten in eine Textdatei schreibt, und dann habe ich nachgeschaut, wie viele Muster in der Textdatei stehen.]
Laut diesen Video ist das Ergebnis falsch. https://www.youtube.com/watch?v=D9dXrKUCfO0
Neun Punkte. Nach einer Benutzung eines Punktes kann dieser nicht nochmal benutzt werden. Also 9*8*7*6*5*4*3*2*1 = 9! Möglichkeiten.Das sind 362.880 Möglichkeiten.
Hast du auch bedacht, dass ich vom ersten Punkt nur 3 Punkte erreichen kann, ohne das ich 3 Punkte selektiert habe?
Πx für 1 bis 9 = 362880
Es gibt also 362880 Möglichkeiten für ein Entsperrmuster mit 3x3x3 (wenn ich es richtig verstanden habe)
Erstmal ist es kein 3x3x3 Muster, sondern ein 3x3 Muster (sind ja nur 9 Kästchen und nicht 27).
Dann muss es für jedes Kästchen eine mind. eine Möglichkeit geben. Also alle Zahlen miteinander Multiplizieren und du kommst auf das Ergebnis. Könntest theoretisch anstatt Πx für 1 bis 9 1*2*3*4*5*6*7*8*9 schreiben
Mit genau einem Punkt:
9
Mit genau zwei Punkten:
9 * 8 = 72
... und so weiter ...
Mit genau neun Punkten:
9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362880
======
Summiert man das auf erhält man:
9 + 9 * 8 + ... + 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 986409
======
Ergebnis:
986409
Danke sagenDanke sagen
0 Kommentare
Antwort hilfreich?Hilfreich?
Denke mal, wie im normalen Handyentsperrmuster, darf man jeden Punkt nur ein mal benutzen. Sonst gäbe es ja unendlich Möglichkeiten (wenn die Anzahl, die man diese Kästchen ansteuern kann, unendlich ist) ^^