infostudium.de

von **padde** » 20.02.07 14:42

Hallo,

ich hab momentan ein kleines Problem mit einer Aufgabe. Hier erstmal meine Lösung:

Gesucht ist die Anzahl n aller nat. Zahlen < 1001, die weder durch 8, noch durch 14, noch durch 17 teilbar sind.

$X:$ Menge aller nat. Zahlen < 1001, die durch 8, 14 oder 17 teilbar sind.
$M_{i}:$ Menge aller nat. Zahlen < 1001, die durch i teilbar sind.

Es gilt dann:

$M_{8} = \lfloor\frac{1000}{8}\rfloor = 125$

$M_{14} = \lfloor\frac{1000}{14}\rfloor = 58$

$M_{17} = \lfloor\frac{1000}{17}\rfloor = 71$

$M_{8} \cap M_{14} = \lfloor\frac{1000}{8*14}\rfloor = 8$

$M_{8} \cap M_{17} = \lfloor\frac{1000}{8*17}\rfloor = 7$

$M_{14} \cap M_{17} = \lfloor\frac{1000}{14*17}\rfloor = 4$

$M_{8} \cap M_{14} \cap M_{17} = \lfloor\frac{1000}{8*14*17}\rfloor = 0$

Dann folgt doch nach Inklusion Exklusion für $X$

$|X| = |M_{8}| + |M_{14}| + |M_{17}| - (|M_{8} \cap M_{14}| + |M_{8} \cap M_{17}| + |M_{14} \cap M_{17}| - |M_{8} \cap M_{14} \cap M_{17}|) = 125+71+58-(8+7+4-0) = 235$

Und dann gilt für die gesuchte Anzahl von Zahlen:

$n = 1000-235 = 765$

Das ist eine Aufgabe vom Multiple Choice Blatt 4 und laut Lösung kommt 773 heraus. Meine Frage: Wo liegt in meiner Lösung der Fehler und wie kommt man auf die richtige Lösung?

Danke schonmal

padde

von **CrazyPumuckl** » 20.02.07 14:45

Du musst beachten dass 14 und 8 die Zahl 2 als ggT haben

von **padde** » 20.02.07 15:30

Ah, jetzt versteh ichs.

Aber gehts nicht eher ums kgV anstatt um den ggT?

padde

von **CrazyPumuckl** » 20.02.07 15:31

unser KGÜ-Leiter hat da ggT drangeschrieben, kann aber auch gut sein dass es kgV sein muss - auf jeden fall weißt du, was zu tun ist

von **HappyCosinus** » 20.02.07 15:48

ja, geht wohl eher um den kgv ^^
also bei 8 und 14
8 = 2*2*2
14 = 2*7
kgv = 2^3*7^1 = 56 und damit dann dividieren

von kb » 20.02.07 16:05

und du solltest bei der Klausur auf die Schreibweise achten =]

padde hat geschrieben:Hallo,
$M_{8} = \lfloor\frac{1000}{8}\rfloor = 125$
....

wäre falsch, richtig wäre
$|M_{8}| = \lfloor\frac{1000}{8}\rfloor = 125$

von **padde** » 20.02.07 16:47

kb hat geschrieben:und du solltest bei der Klausur auf die Schreibweise achten =]
padde hat geschrieben:Hallo,
$M_{8} = \lfloor\frac{1000}{8}\rfloor = 125$
....

wäre falsch, richtig wäre
$|M_{8}| = \lfloor\frac{1000}{8}\rfloor = 125$

Schon klar, das hab ich nur vergessen.

Trotzdem danke für den Hinweis..

padde

von **CrazyPumuckl** » 20.02.07 16:48

ok,ok ^^

ich wusste garnicht mehr wie man das kgV berechnet *schäm*, deshalb hab ich das immer so gemacht: $8\cdot14\cdot\frac{1}{ggT(8,14)} = 8\cdot\14\cdot\frac{1}{2} = 56$ . Ist doch dasselbe, oder ist das hier nur Zufall?

von kb » 20.02.07 16:58

ist das gleiche
ggT(a,b) = g
a = g * r_1
b = g* r_2
kgV(a,b) = r_1 * r_2 * g = a * b : g

von **Quinie** » 21.02.07 13:13

Also irgendwie blicke ich da trotzdem nicht durch, mir ist das unlogisch
Klar 2 ist kgV, aber was tut das zur Sache?
Wenn ich 1000 zahlen habe und die nciht durch 14,8,17 teilbar sein darf
Dann muss ich doch alle zahlen abziehen die durch 14, 17 und 8 teilbar sind und alle die ich doppelt habe wieder drauf addieren
Also 1000-125-71-58+8+7+4
damit komme ich auf die umstrittenen 765
Wo ist jetzt mein denkfehler

von **bugs** » 21.02.07 13:45

naja, aber du musst ja für die inklusion-exklusion irgendwann die schnittmenge der zahlen bilden, die durch 17 und 14, 17 und 8, 14 und 8 dabei rechnest du ja immer den kgV von den beiden Zahlen aus (17*14, 17*8, aber nicht 14*8, da die beiden ja den gemeinsamen Teiler 2 haben, also komm dabei dann kgV(14,8) = 56 raus)
Da Du die Anzahl der Elemente in der Menge (1000) durch diesen kgV teilen muss gibt es wesentlich mehr Elemente in der Schnittmenge von "teilbar durch 14" und "teilbar durch 8", als wenn Du durch 14*8 teilen würdest.
Also musst du auch wieder mehr hinzuaddieren, die Du vorher ja zuviel abgezogen hast ...

anderes beispiel:

wieviele Zahlen gibt es in [100], die durch 3 UND 6 teilbar sind ...
durch 3 teilbar: 100/3 abgerundet = 33
durch 6 teilbar: 100/6 abgerundet = 16
also wären das dann zunächst 33 + 16 Zahlen ...
da aber kgv(3,6) = 6, sind die 16 Zahlen, die durch 6 teilbar sind auch alle durch 3 teilbar (also schon in den 33 enthalten), also sind es im Endeffekt nur 33 Zahlen, die durch 3 und 6 teilbar sind

von kb » 21.02.07 14:20

bugs hat geschrieben:anderes beispiel:

wieviele Zahlen gibt es in [100], die durch 3 UND 6 teilbar sind ...
durch 3 teilbar: 100/3 abgerundet = 33
durch 6 teilbar: 100/6 abgerundet = 16
also wären das dann zunächst 33 + 16 Zahlen ...
da aber kgv(3,6) = 6, sind die 16 Zahlen, die durch 6 teilbar sind auch alle durch 3 teilbar (also schon in den 33 enthalten), also sind es im Endeffekt nur 33 Zahlen, die durch 3 und 6 teilbar sind

Hast du vorhin so schön erklärt, aber hier falsch gemacht ^^ Da kgV(3,6)=6 sind es genau 100/6 = 16 Zahlen, die durch 3 UND 6 teilbar sind, und nicht 33

von **philipp** » 21.02.07 14:30

$8=2\cdot 2 \cdot 2$
$14=2\cdot 7$
$17=17$

$kgV(8,14)=8\cdot 7 = 56$
$kgV(14,17)=14\cdot 17 = 238$
$kgV(17,8)=17\cdot 8 = 136$
$kgV(8,14,17)=8\cdot 7 \cdot 17= 952$

$\lfloor\frac{1000}{8}\rfloor=125$

$\lfloor\frac{1000}{14}\rfloor=71$

$\lfloor\frac{1000}{17}\rfloor=58$

$\lfloor\frac{1000}{56}\rfloor=4$

$\lfloor\frac{1000}{238}\rfloor=7$

$\lfloor\frac{1000}{136}\rfloor=17$

$\lfloor\frac{1000}{952}\rfloor=1$

$\Rightarrow A = 1000 - (125+71+58\ -\ (4+7+17)\ +\ 1) = 773$

von **bugs** » 21.02.07 17:03

öhm ja ... stimmt, kleiner Denkfehler ...
hatte vielleicht 3 ODER 6 im Kopf, dann müsste man aber auch nicht den kgV nehmen, sondern den ggT oder?

von **Fighter_MV** » 21.02.07 17:20

Auch eine Frage von mir zu dem Thema

Aufgabenstellung:

Bild

Jetzt hab ich ja

|M| = 200
|M(rot)| = 60
|M(flosse)| = 30
|M(klein)| = 40

|M(rot und klein)| = 20
|M(flosse und klein)| = 6

|M (rot und Flosse und klein)| = 1

Daraus folgt per Inklusion-Exklusion

|M (fisch gesund)| = 200-(60+30+40-(20+6)+1)

Und da kommt bei mir 95 raus und nicht wie in der angegebenen Lösung 96 -.-

Wo liegt der Fehler?[/code]

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] Inklusion/Exklusion Problem

Inklusion/Exklusion Problem

Re: Inklusion/Exklusion Problem

Re: Inklusion/Exklusion Problem