\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fswiss\fprq2 Arial;}{\f4\fmodern\fprq1 Courier New;}{\f5\fswiss\fprq2\fcharset1 Arial;}{\f6\froman\fcharset1 Times New Roman;}{\f7\fswiss\fprq2 Helvetica;}} {\colortbl\red0\green0\blue0;\red255\green0\blue0;\red0\green0\blue255;\red0\green128\blue0;\red255\green255\blue255;\red0\green0\blue128;} \deflang1031\pard\ri4\plain\f4\fs20\cf0\b ________________________________________________________________________________ \par \par \plain\f4\fs20\cf0 Inhalt....: Das Geburtstagsproblem \par Kategorie.: Arbeitsblatt \par Mathematik: Stochastik, Kryptographie \par MuPAD.....: 3.0.0 \par Datum.....: 2003-06-23 \par Autoren...: Julia Faflek \par Funktionen: !, plot, plot::Polygon2d \par \plain\f4\fs20\cf0\b ________________________________________________________________________________ \par \plain\f3\fs36\cf0\b \par \plain\f3\fs40\cf0\b Das Geburtstagsproblem oder wie viele \par Personen lade ich zu meiner Party ein?\plain\f3\fs36\cf0\b \par \plain\f3\fs22\cf0 \par \plain\f3\fs24\cf3 Das Geburtstagsproblem ist ein klassisches Beispiel aus der Stochastik und Wahrschein- \par lichkeitsrechnung, welches auch in der Kryptographie Anwendung findet. \par \plain\f3\fs28\cf0 \par Zu meinem n\'e4chsten Geburtstag m\'f6chte ich eine gro\'dfe Party machen. Dazu \par \'fcberlege ich mir, wie viele Freunde ich einladen soll. Denn an diesem Tag soll \par mit einer Wahrscheinlichkeit gr\'f6\'dfer als 1/2 mind. einer der Anwesenden auch \par Geburtstag haben. \par \par Wir betrachten die Gegenwahrscheinlichkeit: Aus einer Gruppe von \plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 Personen \par hat niemand an meinem Tag Geburtstag. Die Anzahl m\'f6glicher Ereignisse ist \par die Anzahl m\'f6glicher Geburtstage f\'fcr \plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 Personen: \par \pard\li4000\ri4\plain\f4\fs22\cf2 {\pict\wmetafile8\picw1244\pich883\picscalex99\picscaley99\picwgoal712\pichgoal505 010009000003DA02000006001C0000000000050000000B0200000000050000000C027303DC0403 0000001E00050000000C027B03E804050000000B0200000000030000001E00050000000C027E03 F604050000000B0200000000050000000B0200000000030000001E00050000000C028703030505 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C0292031105050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C029C031F05050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C02A6032E05050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C02B0033C05050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C02BC034C05050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C02C6035A0505000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C02C7035C05050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00030000001E00050000000C0224020A03050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B020000000008000000FA020000000000000000000004 0000002D0100001C000000FB0238FF00000000000090010000000107000000417269616C000000 20100A4538E91200D89FF177E19FF1772020F37717106688040000002D01010005000000020101 000000050000000102FFFFFF00050000002E011800000005000000090200000000040000000801 00001C000000FB02E8FE00000000000090010000000107000000417269616C0000000A100A8638 E91200D89FF177E19FF1772020F37717106688040000002D0102000B00000026060F000C004D61 74685479706500007F001C000000FB023AFF00000000000090010100000107000000417269616C 00000019100A5338E91200D89FF177E19FF1772020F37717106688040000002D01030004000000 2D0102000700000021050100330085016400070000002105010036008501000107000000210501 00350085019C01040000002D01030007000000210501006E00E300380208000000FA0200000000 000000000000040000002D0104001C000000FB021000070000000000BC02000000000102022253 797374656D00001A100A5138E91200D89FF177E19FF1772020F37717106688040000002D010500 040000002701FFFF04000000F001000004000000F001010004000000F001020004000000F00103 00040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF030000000000 }\plain\f4\fs22\cf2 \par \pard\ri4\plain\f3\fs28\cf0 F\'fcr die Anzahl g\'fcnstiger Ereignisse ergibt sich mittels Kombinatorik: \par \pard\li4000\ri4\plain\f4\fs22\cf2 {\pict\wmetafile8\picw1256\pich891\picscalex98\picscaley99\picwgoal720\pichgoal506 0100090000039702000006001C0000000000050000000B0200000000050000000C027B03E80403 0000001E00050000000C027E03F604050000000B0200000000030000001E00050000000C028703 0305050000000B0200000000050000000B0200000000030000001E00050000000C029203110505 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C029C031F05050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02A6032E05050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C02B0033C05050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C02BC034C05050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C02C6035A05050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C02C7035C0505000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00030000001E00050000000C0224020A03050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C00 0000FB0238FF00000000000090010000000107000000417269616C00000017100A8938E91200D8 9FF177E19FF1772020F3771A106653040000002D01010005000000020101000000050000000102 FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02E8 FE00000000000090010000000107000000417269616C00000019100A5438E91200D89FF177E19F F1772020F3771A106653040000002D0102000B00000026060F000C004D6174685479706500007F 001C000000FB023AFF00000000000090010100000107000000417269616C0000000A100A8738E9 1200D89FF177E19FF1772020F3771A106653040000002D010300040000002D0102000700000021 05010033008501640007000000210501003600850100010700000021050100340085019C010400 00002D01030007000000210501006E00E300380208000000FA0200000000000000000000040000 002D0104001C000000FB021000070000000000BC02000000000102022253797374656D00002010 0A4638E91200D89FF177E19FF1772020F3771A106653040000002D010500040000002701FFFF04 000000F001000004000000F001010004000000F001020004000000F0010300040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f4\fs22\cf2 \par \pard\ri4\plain\f3\fs28\cf0 Damit ergibt sich f\'fcr die gesuchte Wahrscheinlichkeit: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf1 {\pntext\f1\'b7\tab}p1 := n -> 1 - (364^n)/(365^n) \par \pard\ri4\plain\f5\fs28\cf0 Zun\'e4chst stellen wir diese Wahrscheinlichkeit f\'fcr bis zu 365 Personen grafisch \par dar. \par \plain\f6\fs22\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf1 {\pntext\f1\'b7\tab}Punkte1 := [0 $ 365]: \par \pard\li600\ri1\fi-300\plain\f4\fs28\cf1 for i from 1 to 365 do \par Punkte1[i] := [i, p1(i)] \par end_for: \par plot(plot::Polygon2d(Punkte1)); \par \pard\ri4\plain\f3\fs28\cf0 (Die Punkte liegen so nahe beieinander, dass der obige Polygonzug wie \par \plain\f3\fs28\cf4 -\plain\f3\fs28\cf0 ein gew\'f6hnlicher, von MuPAD dargestellter, Funktionsgraph aussieht.) \par \par Nun suchen wir das minimale \plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 , f\'fcr das die Wahrscheinlichkeit gr\'f6\'dfer als 1/2 \par ist. Anhand der Grafik k\'f6nnen wir dieses \plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 f\'fcr den Bereich 240 bis 260 ein- \par schr\'e4nken:\plain\f4\fs22\cf2 \par \plain\f3\fs22\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf1 {\pntext\f1\'b7\tab}for j from 240 to 260 do \par \pard\li600\ri1\fi-300\plain\f4\fs28\cf1 print("Bei ".j. " Personen betr\'e4gt die Wahrscheinlichkeit " \par .expr2text(float(p1(j)))) \par end_for: \par \pard\ri4\plain\f3\fs28\cf0 Dieser Ausgabe entnehmen wir, dass bei 253 Personen die Wahrscheinlich- \par keit bereits h\'f6her als 1/2 liegt. Die gesuchte Anzahl der Personen ist also 253. \par Demnach muss ich zu meiner Geburtstagsparty 252 Personen (253-ich) einla- \par den, wenn ich mit einer Wahrscheinlichkeit gr\'f6\'dfer als 1/2 nicht die einzige Per- \par son sein m\'f6chte, die an diesem Tag Geburtstag hat. \par \par Verallgemeinern wir die Situation etwas. Ich befinde mich auf einer Einweihungs- \par party. Wie viele Personen m\'fcssen anwesend sein, damit mit einer Wahrschein- \par lichkeit gr\'f6\'dfer als 1/2 mind. 2 Personen an dem selben Tag Geburtstag haben? \par Der Unterschied zu dem vorherigen Beispiel besteht darin, dass jetzt nicht nach \par einem bestimmten Tag gefragt wird, sondern nach einem beliebigen. Schauen \par wir uns auch hier zun\'e4chst die Gegenwahrscheinlichkeit an: Die Anzahl m\'f6glicher \par Ereignisse bleibt gleich, nur die Anzahl g\'fcnstiger Ereignisse \'e4ndert sich zu \par \pard\li4000\ri4\plain\f3\fs28\cf0 {\pict\wmetafile8\picw2558\pich1379\picscalex99\picscaley99\picwgoal1454\pichgoal786 0100090000034E04000008001C0000000000050000000B0200000000050000000C026305FE0903 0000001E00050000000C026B05060A050000000B0200000000030000001E00050000000C027205 190A050000000B0200000000050000000B0200000000030000001E00050000000C027C05220A05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C028305350A050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C028C053E0A050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C029305510A050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C029C055A0A050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C02A3056D0A050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C02AC05770A05000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C02BB05930A050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02BC05940A050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00030000001E00050000000C024003FF0505 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF0000000000 0090010000000107000000417269616C0000001B100A5438E91200D89FF177E19FF1772020F377 1F1066B3040000002D01010005000000020101000000050000000102FFFFFF00050000002E0118 0000000500000009020000000004000000080100001C000000FB02E8FE00000000000090010000 000107000000417269616C0000001D100A6F38E91200D89FF177E19FF1772020F3771F1066B304 0000002D0102000B00000026060F000C004D6174685479706500000B011C000000FB02E8FE0000 000000009001000000020700000053796D626F6C000020100A4D38E91200D89FF177E19FF17720 20F3771F1066B3040000002D010300040000002D0102001C000000FB02E8FE0000000000009001 0100000107000000417269616C0000001E100A1F38E91200D89FF177E19FF1772020F3771F1066 B3040000002D010400040000002D0103001C000000FB02E8FE0000000000009001000000020700 00005346204D617468204578740038E91200D89FF177E19FF1772020F3771F1066B3040000002D 010500040000002D010200040000002D010500040000002D010200040000002D01030004000000 2D010200070000002105010033006201D2010700000021050100360062016E0207000000210501 00350062010A03040000002D010300070000002105010021006201D003040000002D0105000400 00002D010200040000002D010500040000002D010200040000002D010500040000002D01020004 0000002D010500040000002D010200040000002D010500040000002D010200040000002D010500 040000002D010200040000002D01050007000000210501002800A4028400040000002D01020007 000000210501003300A402F10007000000210501003600A4028D0107000000210501003500A402 2902040000002D01030007000000210501002D00A4020B03040000002D01040007000000210501 006E00A402EB03040000002D010500040000002D010200040000002D010500040000002D010200 040000002D01050007000000210501002900A4028704040000002D010300070000002105010021 00A4021E05040000002D0105000700000021050100C500860164000700000021050100C5008601 0C010700000021050100C5008601B4010700000021050100C50086015C020700000021050100C5 00860104030700000021050100C5008601AC030700000021050100C50086015404070000002105 0100C5008601F30408000000FA0200000000000000000000040000002D0106001C000000FB0210 00070000000000BC02000000000102022253797374656D00001C100A1638E91200D89FF177E19F F1772020F3771F1066B3040000002D010700040000002701FFFF04000000F001000004000000F0 01010004000000F001020004000000F001030004000000F001040004000000F001050004000000 2701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000 002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400 00002701FFFF040000002701FFFF030000000000 }\plain\f3\fs28\cf0 \par \pard\ri4\plain\f3\fs28\cf0 Damit ergibt sich f\'fcr die gesuchte Wahrscheinlichkeit: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf1 {\pntext\f1\'b7\tab}p2 := n -> 1 - (365!/(365-n)!)/(365^n) \par \pard\ri4\plain\f3\fs28\cf0 Auch hier visualisieren wir das Verhalten: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf1 {\pntext\f1\'b7\tab}Punkte2 := [0 $ 365]: \par \pard\li600\ri1\fi-300\plain\f4\fs28\cf1 for i from 1 to 365 do \par Punkte2[i] := [i, p2(i)] \par end_for: \par plot(plot::Polygon2d(Punkte2)); \par \pard\ri4\plain\f3\fs28\cf0 Schauen wir uns das Ganze mal im Zusammenhang an: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf1 {\pntext\f1\'b7\tab}pl1 := plot::Polygon2d(Punkte1, Color = RGB::Blue): \par \pard\li600\ri1\fi-300\plain\f4\fs28\cf1 pl2 := plot::Polygon2d(Punkte2, Color = RGB::Green): \par plot(pl1, pl2) \par \pard\ri4\plain\f3\fs28\cf0 Erstaunlich wie sehr sich diese beiden Wahrscheinlichkeiten unterscheiden! \par Nun suchen wir das minimale \plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 , f\'fcr das die Wahrscheinlichkeit gr\'f6\'dfer als 1/2 \par ist. Anhand der Grafik k\'f6nnen wir dieses \plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 f\'fcr den Bereich von 10 bis 30 ein- \par schr\'e4nken:\plain\f4\fs22\cf2 \par \plain\f3\fs22\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf1 {\pntext\f1\'b7\tab}for j from 10 to 30 do \par \pard\li600\ri1\fi-300\plain\f4\fs28\cf1 print("Bei ".j. " Personen betr\'e4gt die Wahrscheinlichkeit " \par .expr2text(float(p2(j)))) \par end_for: \par \pard\ri4\plain\f3\fs28\cf0 Wir sehen also, dass mind. 23 Personen auf der Party anwesend sein m\'fcssen, \par damit mit einer Wahrscheinlichkeit gr\'f6\'dfer als 1/2 mind. 2 Personen an dem \par gleichen Tag Geburtstag haben. \par \par Anwendung findet dieses Problem auch in der Kryptographie. Dort betrachtet \par man eine Funktion und untersucht, ob zwei verschiedene Urbilder den gleichen \par Funktionswert liefern. Man sucht so genannte Kollisionen z.B. bei Pollard's-Rho- \par Methode zum Faktorisieren ganzer Zahlen. Wobei die in der Kryptographie oft \par benutzten Hashfunktionen kollisionsfrei sein sollen. \par \plain\f4\fs20\cf2 \par \plain\f4\fs20\cf0\b ___________________________________________________________________________________ \par \plain\f4\fs22\cf2 \par \plain\f3\fs22\cf2\b \'dcbungen: \par \plain\f3\fs20\cf2\b 1. \plain\f3\fs20\cf2 Machen Sie sich mit den Funktionen\plain\f3\fs20\cf5 \plain\f4\fs20\cf1 ! \plain\f3\fs20\cf2 und\plain\f4\fs20\cf1 fact \plain\f3\fs20\cf2 vertraut. \par \plain\f3\fs20\cf2\b 2.\plain\f3\fs20\cf2 Besuchen Sie die Hilfeseite zu ?plot::Polygon2d.\plain\f3\fs20\cf5 \par \plain\f4\fs20\cf0\b ___________________________________________________________________________________ \par \plain\f3\fs22\cf0 \par \plain\f3\fs22\cf3\b Anmerkungen:\plain\f3\fs22\cf3 \par \plain\f3\fs20\cf3\b 1. \plain\f3\fs20\cf3 Unter \plain\f3\fs20\cf1 www.schule.mupad.de/material/\plain\f3\fs20\cf3 finden Sie weitere interessante Notebooks. \par \par \plain\f3\fs20\cf3\b 2.\plain\f3\fs20\cf3 Weitere Anregungen finden Sie in der Buchreihe \plain\f3\fs20\cf1 Mathematik 1 x anders\plain\f3\fs20\cf3 . In dieser Reihe wird eine Vielzahl \par \plain\f3\fs20\cf4 ss\plain\f3\fs20\cf3 unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die B\'fccher k\'f6nnen unter \par \plain\f3\fs20\cf4 ss\plain\f7\fs20\cf2 www.schule.mupad.de/literatur\plain\f3\fs20\cf3 kostenfrei kopiert werden.\plain\f3\fs20\cf1 \par \plain\f4\fs20\cf0\b ___________________________________________________________________________________ \par \par \par }