Mathematische Probleme

I

~ihja

0
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.
 
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 ...
nehmen wir erstmal die gesammte menge aller passworte die mit den 95 zeichen zu bilden sind ...

das sind 95^5 = 7.737.809.375 ... mehr unterscheidbare passworte mit 5 stellen und diesem charset kann es nicht geben

hiervon ziehen wir nun alle passworte ab, die keine sonderzeichen enthalten ... das sind (95 - 33)^5 = 916.132.832

bleiben in unserer menge 7.737.809.375 - 916.132.832 = 6.821.676.543

nun müssen noch alle passworte weg, die keine kleinbuchstaben enthalten

das sind (95 - 26)^5 = 1.564.031.349

darin enthalten sind aber passworte die wir bereits entfernt haben ... namentlich alle die nur aus großbuchtaben und ziffern bestehen ... das wiederum sind 36^5 = 60.466.176 ... damit wir die also nicht 2 mal entfernen müssen wir sie einmal hinzu addieren ...
6.821.676.543 - 1.564.031.349 + 60.466.176 = 5.318.111.370
 
Zuletzt bearbeitet:
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.
 
Zuletzt bearbeitet:
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)
 
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.
 
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 :D.

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 ;-)
 
Zuletzt bearbeitet:
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| = ....
 
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!!
 
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:)
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben