[HaBo]

~ihja

Anzeige

Heyho und guten Abend alle zusammen. Es geht um mathematische Probleme, die ich irgendwie falsch gelöst habe und ich komme einfach nicht darauf warum. Hier mal die Aufgaben und meine Lösungen. Wer Zeit und Muße hat kann ja mal auf Fehlersuche gehen. Bin für jeden Tipp dankbar.

Passwörter werden aus 95 druckbaren ASCII-Zeichen gebildet. Diese bestehen aus 26 Großbuchstaben, 26 Kleinbuchstaben, 10 arabische Ziffern und 33 Sonderzeichen.

1) Wie viele Passwörter der Länge 5, in denen mindestens ein Kleinbuchstabe und ein Sonderzeichen vorkommt, sind möglich?

Meine Lösung:
26(Kleinbuchstaben)x33(Sonderzeichen)x95x95x95 = 735627750
735627750x5(Mögliche Positionen des KB)x4(Mögl. Pos. für Sonderz.) = 14712555000

Richtig wäre aber: 5318111370

2) Wie viele Passwörter der Länge 5, in denen mindestens ein Groß- und Kleinbuchstabe, sowie mindestens eine Ziffer und ein Sonderzeichen vorkommen, sind möglich?

Meine Lösung:
26(GB)x26(KB)x10(Ziffer)x33(Sonderz.)x95 = 21192600
21192600x5(Pos. GB)x4(Pos. KB)x3(Pos. Ziffer)x2(Pos. Sonderz.) = 2543112000

Richtig wäre: 1271556000 (Hälfte von meinem Ergebnis)


Bei den anderen Beiden habe ich meine Fehler gerade selber gefunden...auch nicht schlecht -.-`

Also danke schon mal und noch nen schönen Abend.

GrafZahl

beidesmal der gleiche "fehler" ...

du zerlegst die menge aller passworte in teilmengen, bestimmst die anzahl der elemente der jeweiligen menge, und addierst diese ...

ansich keine schlechte idee, aber deine teilmengen sind leider nicht disjunkt (es gibt nicht leere schnittmengen)

Bsp:
sagen wir mal wir betrachten nur 2 der teilmengen:

alle passworte der klassen <ksaaa> sowie <askaa>
alle, großbuchstaben, kleinbuchstaben, ziffern, sonderzeichen

wählen wir ferner je einen vertreter der jeweiligen klasse ...

ksaaa => "x.xxx"
askaa => "x.xxx"

da ich 2 mal das gleiche passwort wählen konnte gibt es nun ein problem:

für welche der beiden klassen darf ich dieses passwort nun zählen?

deine berechnung zählt es in beiden fällen, was dann natürlich zu einer viel größeren gesammtanzahl führt ...



allerdings kann man bei dieser formulierung der frage natürlich noch das klugscheiß argument bringen, dass die jeweilige frage diese explizite trennung der klassen nicht vorschreibt, da nicht explizit die einzigartigkeit/unterscheidbarkeit der passworte gefordert wird ... es bleibt daher nur der natur der sache geschuldet, dass diese forderung beim ungang mit passworten implizit gilt...

//nachtrag weil schlaflosigkeit + langeweile ...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

~ihja

Eine wirklich sehr nette Möglichkeit seine Langeweile zu nutzen. Vielen Dank erstmal dafür. Konnte deine Lösung auch gut nachvollziehen.
Habe mich jetzt mit deinem Lösungsweg an Aufgabe 2 gemacht, aber ich komme irgendwie - wahrscheinlich weil es hier einfach zu laut ist - nicht darauf und mein Gehirn blockiert gerade. Melde mich heute Abend mal, ob ich es geschafft habe...

Habe leichte Minderwertigkeitskomplexe weil ich es nicht gebacken kriege:
Analog zu Aufgabe 1:
95^5(alle)-69^5(SZ,Z,KB)-69^5(SZ,Z,GB)-62^5(Z,KB,GB)-85^5(GB,KB,SZ) = -743439280 + ?

Ich kriege nicht raus, was ich alles addieren muss. Auf das richtige Ergebnis komme ich aber einfach nicht. Wäre dankbar für Tipps...
Habe mir auch schon überlegt, ob ich nicht einfach vom meinem vorherigen Ergebnis auf das richtige schließen kann.

Tsjuder

Hier die Lösung falls du es genauer brauchst sag nochmal Bescheid (wenn man die Siebformel kennt kommt man recht einfach drauf)

95^5 - (69^5 +69^5 +85^5 + 62^5 - (43^5 + 59^5 + 36^5 + 59^5 + 36^5 + 52^5) + 33^5 + 10^5 + 26^5 + 26^5)

~ihja

Danke erstmal für die schnelle Antwort. Kann mir zwar mehr oder weniger was dazu denken, aber wäre selber nicht darauf gekommen. Wenn du Zeit hast könntest du es vielleicht noch ein wenig ausführen. Vor allem was es mit der Siebformel auf sich hat bzw. warum dir das so leicht fällt . Wikipedias Summenformel zur Siebformel verstehe ich nicht so ganz.

Tsjuder

Ich bin selbst kein Mathematiker also hoffentlich ist da an der Erklärung jetzt nichts falsch bzw. jemand steinigt mich weil es für einen Mathematiker viel zu ungenau ist .

Erstmal: Du hast immer mindestens 1 Sonderzeichen, mindestens 1 Großbuchstaben usw. Anstatt mit mindestens arbeiten wir jetzt immer mit dem Gegenteil. Das Gegenteil wäre also jetzt genau 0, sprich kein Großbuchstabe usw.
Folgendes musst du jetzt tun: Die Anzahl der Möglichkeiten mit einem Ereigniss addieren, die Anzahl der Möglichkeiten mit 2 Ereignissen abziehen, die Anzahl der Möglichkeiten mit 3 Ereignissen wieder addieren. Also immer im Wechsel wenn "etwas hinzukommt" ...addieren/subtrahieren/addieren/subtrahieren (wird weiter unten nochmal klarer denke ich)

Legende:
G = Großbuchstabe (26)
K = Kleinbuchstabe (26)
Z = Ziffer (10)
S = Sonderzeichen (33)

Wir haben jetzt folgende Ereignisse:
A: Kein G
B: Kein K
C: Kein Z
D: Kein S

Jetzt also ein wenig rechnen: A = (95-26) ^5 = 69^5
B = (95-26)^5 = 69^5 (jetzt etwas fixer)
C = 85^5
D = 62^5
In Summe = 8.481.248.655

Jetzt alles mit 2 Ereignissen (und Verknüpft):

Also A und B heißt dann z.B. kein Großbuchstabe und kein Kleinbuchstabe.

A und B = (95-26-26)^5 = 43^5
A und C = (95-26-10)^5 = 59^5 (den Rest siehst du ausgerechnet ja selbst denke ich)
A und D...
B und C...
B und D...
C und D...
In Summe: 2.077.993.425

Jetzt alles mit 3 Ereignissen (wieder und Verknüpft):
A und B und C heißt dann also kein Großbuchstabe und kein Kleinbuchstabe und kein Sonderzeichen.

A und B und C = (95-26-26-10)^5 = 33^5
A und B und D ...
A und C und D...
B und C und D...
In Summe: 62.998.145

Wie gesagt jetzt addieren/subtrahieren/addieren=
+8.481.248.655 - 2.077.993.425 + 62.998.145 = 6.466.253.375

Da wir überall das "Gegenteil" genommen haben, haben wir jetzt das Komplement von unserem Ergebniss das wir haben wollen daher rechnest du jetzt noch alle Möglichkeiten die es insgesamt gibt minus diesem ausgerechneten Wert :
95^5 - 6.466.253.375 = 1.271.556.000


EDIT: Warum man immer addiert/subtrahiert liegt daran was GrafZahl da schon erklärt hat, wenn man allerdings mehrere Ereignisse hat zieht man durch die zweite Summe wieder zuviel ab, weswegen man durch die 3te Summe wieder was addieren muss.

EDIT 2: Das mit addieren/subtrahieren hat Darkslide unter jetzt ganz gut erklärt ;-)

Darkslide

Beispiel, um dir zu erklären was die Siebformel macht:

Problem: Wie viele Zahlen zwischen 1 und 1000 sind durch 4, 5 oder 6 teilbar?

Sei Ak:={x€{1,1000}| k|x}

A4 = 1000/4 = 250
(250 Zahlen sind in der Menge {1, ..., 1000} sind durch 4 teilbar)
A5 = 1000/5 = 200
A6 = 1000/6 = 166

Wenn du jetzt die Mengen addierst, dann zählst du aber die Zahlen doppelt, die durch 4 und 6; 4 und 5; 5 und 6 teilbar sind.

Demzufolge ziehst du die Schnittmengen wieder ab:

|A4uA5uA6| = |A4|+|A5|+|A6|-|A4^A5| - |A4^A6| - |A5^A6| (^ = Schnittmenge)

Jetzt hast du aber die Zahlen die durch 4, 5, und 6 teilbar sind 3 mal gezählt und dann 3 mal wieder abgezogen. Demzufolge musst du diese Schnittmenge wieder addieren:

|A4uA5uA6| = |A4|+|A5|+|A6|-|A4^A5| - |A4^A6| - |A5^A6| + |A4^A5^A6|

Die Schnittmenge ist dann das kgv der "k" der beiden Mengen, z.B. |A4^A5| = |A20|

Die Siebformel gibt dir also im Prinzip folgendes an:

|M1 u M2 u ... u Mn| = ....

~ihja

Vielen Dank für eure umfangreiche und schnelle Hilfe. Beim ersten lesen kann ich das alles schon ganz gut nachvollziehen. Morgen muss ich mir das dann nochmal genauer angucken und durchrechnen. Glaube aber, dass alle Fragen geklärt sind.
Danke nochmal!!

LaNdRiX

Hey ~ihja,
das mathematische Prinzip hinter der "Siebformel" nennt sich Inklusion und Exklusion.
Falls du doch noch Fragen haben solltest, hier mal der entsprechene Wiki-Artikel.
Viel Erfolg noch

__________________
mfg landrix