Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Anzahl der Entsperrmuster bei Android

Anzahl der Entsperrmuster bei Android

Schüler Gymnasium, 12. Klassenstufe

Tags: Fakultät

meuchelmuesli aktiv_icon

22:51 Uhr, 05.06.2012

Hallöchen erstmal,

ich hab schon ein paar mal Forumseinträge benutzt, um in Mathe weiter zu kommen und hab jetzt selber mal eine Frage. Die hat allerdings nicht direkt was mit der Schule zu tun, außer dass sie mit in der Freistunde kam ;-)

Also, bei den Androidhandys kann man ja ein Entsperrmuster aktivieren, um sein Handy zu aktivieren. Dazu hat man dann ja 9 Punkte von denen man beliebig viele miteinander verbinden kann, allerdings jeden nur einmal benutzen darf. Ich hab mich jetzt gefragt, wie viele Kombinationen es gibt.

Ich hab etwas überlegt, und bin darauf gekommen, das es wohl

9! + 9 \cdot (8! + 7! + 6! + 5! + 4! + 3! + 2! + 1!) = 778977

Möglichkeiten sind.

Erst dachte ich, dass ich einfach alle Fakultäten von

9!

bis

1!

addieren muss, aber das wäre bei einem Punkt auch nur eine Möglichkeit, aber ich kann ja jeden Punkt auswählen, daher das mal 9.
Bei

n

Punkten dann also:

n! + n \cdot [(n - 1)! + (n - 2)! + ... + 1!)

Aber ich kann es leider nicht beweisen, meine Frage wäre deswegen also nun:
Stimmen die Überlegungen, und wenn ja, wie kann man das beweisen?

=)

Danke schon mal im Voraus und schöne Grüße,
meuchelmuesli

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

kalli

00:14 Uhr, 06.06.2012

Hallo,
ich würde sagen, dass es

(\begin{matrix} 9 \\ 9 \end{matrix}) \cdot 9!

Möglichkeiten gibt, wenn man alle Punkte benutzen muss. Dazu kommen

(\begin{matrix} 9 \\ 8 \end{matrix}) \cdot 8!

Möglichkeiten, wenn man nur 8 Punkte verwendet. Anschließend gibt es

(\begin{matrix} 9 \\ 7 \end{matrix}) \cdot 7!

Möglichkeiten, wenn man 7 Punkte benutzt, usw.

Diese Zahlen müssen, wie Du richtig erkannt hast addiert werden.

meuchelmuesli aktiv_icon

15:19 Uhr, 06.06.2012

Danke erstmal, aber das verstehe ich gerade noch nicht ganz. Du multiplizierst einen Vektor mit der Fakultät. (Oder verstehe ich das gerade falsch?) Da kommt doch ein anderer Vektor raus, aber kein Skalar...

Zudem müssten doch zumindest, wenn ich alle 9 Punkte verbinden muss die Anzahl der Möglichkeiten schlicht

9!

sein, da brauche ich also keinen Vorfaktor, weder Vektor noch Skalar.

Sorry, falls ich mich irre, ist mir gerade noch nicht ganz klar, wie du das meinst ;-)

Schöne grüße :-D)

vulpi aktiv_icon

16:18 Uhr, 06.06.2012

Hallo !
kallis Vorfaktoren sind keine Vektoren, sondern sog. Binominalkoeffizienten, mit
denen die Kombinationen ohne Wiederholung ohne Berücksichtigung der Reihenfolge berechnet werden.
Also Beispiel:
Wieviele verschieden 3er Teams kann man aus

10

Leuten bilden?
Das sind dann "10 über 3"

= (\begin{matrix} 10 \\ 3 \end{matrix}) = \frac{10!}{7! \cdot 3!}

Anmerkung zum Handy-Problem:

Ich mein aber, dass man da nicht JEDE Kombination verwenden kann.
Denn man zeichnet doch Verbindungen OHNE Absetzten, sobald man absetzt, ist die
Eingabe doch beendet, oder ?
(Ich hab' das Teil schon ewig abgeschaltet, darum meine Ungewissheit)

Also ein Zug wie

1,9,5

ist ohne Absetzten ja gar nicht möglich.
gruß

Alex-LRT aktiv_icon

22:34 Uhr, 28.07.2012

Hallo,

wenn wir sagen, dass die Mindestlänge 1 Punkt ist und die Maximallänge 9 Punkte sind, gibt es

986409

Möglichkeiten.

Doch wie können wir nun die "ungültigen" Muster herausfiltern?
Es ist zum Beispiel nicht erlaubt von Punkt 1 (links oben) gleich zum Punkt 9 (rechts unten zu verbinden), wenn nicht davor Punkt 5 (mitte mitte) berührt wurde.

Hat jemand eine Idee?

Grüße,
Alex

MurksVomOrk aktiv_icon

16:41 Uhr, 26.08.2014

Hatte mir die gleiche Frage gestellt.
Greifen wir mal vorweg:
Einige Muster wurden dabei noch nicht beachtet, denn es ist möglich, dass man Muster wie

2 - 3 (- 2) - 1

eingibt. (Feld sei zeilenweise wie folgt nummeriert:

1 - 2 - 3, 4 - 5 - 6

und

7 - 8 - 9)

. Dafür werde ich wohl ein wenig mehr als

~ 5

Minuten investieren müssen, da das Programm sonst sehr lange brauchen könnte - wobei ich da schon eine Idee in Richtung verkettete Listen hab. :-)

Es sind mindestens

10305

mögliche Muster bei Feldgröße

3 x 3

und der Beschränkung, dass man nur zu einem Nachbarn weiter kann.
Und nein, ich hab es nicht von Hand berechnet. Wer es versuchen will, der kann das Muster unten gerne weiterführen.

Da ich nichts gefunden hab und "nachträgliches Filtern" eine unschöne Sache ist, hab ich dann so angefangen:

Ich hab mir zu den Feldern die Anzahl der Nachbarn eingetragen.
Ecken haben jeweils 3 Nachbarn, Kanten 5 und die Mitte hat 8.
Die Ecken/Kanten können jeweils für die ersten Schritte im Muster gleich behandelt werden.
Es gibt 4 Ecken (E),

4

Kanten

(K)

und eine Mitte

(M)

.
Die Gesamtzahl

G

kann also durch

G = 4 \cdot E + 4 \cdot K + M + 0

berechnet werden. Dabei ist

E

die Anzahl der Muster, wenn man bereits eine Ecke gewählt hat.

K

entsprechend für die Kanten.

M

für die Mitte. Da das leere Muster "kein Muster" ist, wird hier nichts weiter addiert.

Man kann es weiterführen - noch ist es leicht:

E = 2 \cdot K_{E} + M_{E} + 1

K_{E} =

die Anzahl der Wege, wenn man nach ner Ecke mit ner Kante weitermacht

M_{E} = ...,

wenn man mit der Mitte weitermacht

+ 1 =

man hört an dieser Stelle auf das Muster zu zeichnen, eine Ecke ist alleine auch ein Muster

- -

wird später

\cdot 4

genommen, da oben

4 \cdot E

gerechnet wird!

K = 2 \cdot K_{K} + 2 \cdot E_{K} + M_{K} + 1

M = 4 \cdot K_{M} + 4 \cdot E_{M} + 1

(Variablen analog)

Mit Schritt 3 wird das ganze leider nicht mehr so leicht überschaubar, denn man könnte jetzt auf Felder geraten, die man bereits besucht hat und darf das dann nicht als Muster werten - die Anzahl der Nachbarn verändert sich also durch die gemachten "Züge". Das will man nicht per Hand machen.

Python raus,

~ 20

Zeilen Code geschrieben, nachoptimiert

(~ 30

Zeilen):
450ms

- \to 10305

mögliche Muster
die erste Optimierung von oben gemacht

(G = 4 \cdot E + 4 \cdot K + M) :

139ms

- \to

gleiches Ergebnis

Feldgröße

4 x 4

mit angepasster 1. Optimierungsstufe

(G = 4 \cdot E + 4 \cdot K + 4 \cdot M)

100235ms (also knapp 2 Minuten)

- \to 9.069.196

mögliche Muster
(ohne Optimierung wahrscheinlich also knapp 6 Minuten)

Die Sicherheit verglichen mit einem "normalen" Zahlenschloss (Ziffern

0 - 9

je Stelle) steigt also von 4 Stellen auf fast 7 Stellen - wobei die Hauptprobleme in Sachen Sicherheit eher das Geschmiere auf dem Bildschirm und die Sicherheitslücken in Software/Hardware sind.

(getestet auf nem Atom, Linux, Python

3.4.1, . .

.
mit ner neueren CPU,

C

oder Assembler und vor allem Codeoptimierung kann man das sicher noch beschleunigen, falls man größere Felder oder mehr Dimensionen nutzt (statt

3 x 3 z . B

7 x 7

oder

3 x 3 x 3 -

wobei das mit der Eingabe schwer wird)!
Ich hab jedes Feld gleich behandelt

- \to

man könnte auch für jedes Feld eine eigene optimierte Funktion schreiben...)

MurksVomOrk aktiv_icon

01:30 Uhr, 27.08.2014

So, Programm erweitert, hab es wieder auf dem Atom in der Ecke durchlaufen lassen...
für den Fall, dass man über die bereits benutzte Punkte auf dem Screen wischt um zu anderen Punkten zu kommen, ergibt sich die Zahl der möglichen Muster zu:

392.849

also fliegen ca.

60 %

der knapp 1 Millionen möglichen Muster (im Fall, dass jeder Punkt von jedem Punkt erreichbar ist) raus...

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1181669

1009418

	Status: nicht eingeloggt	Noch nicht registriert?