Schubfachprinzip - Anzahl Zahlen teilbar durch n Zahlen

07.04.2017, 15:29

MioMioMathe_

Schubfachprinzip - Anzahl Zahlen teilbar durch n Zahlen

Meine Frage:
Folgende Aufgabe, die ich zu Eigenkontrolle versuche zu lösen:

A = {1, ... ,1000} -> Wie viele Zahlen sind durch 2,3 oder 5 teilbar? (Exclusives ODER)

Meine Ideen:
Zur Lösung habe ich eine Formel des Schubfachprinzips verwendet.

1. Meine Mengen definiert:

A ={1, ..., 1000}

B = {b Element A mit der Eigenschaft: 2 Teiler von b}
Mächtigkeit von B = 1000/2 = 500

C = {c Element A mit der Eigenschaft: 3 Teiler von c}
Mächtigkeit von C = 1000/3 = 333

D = {d Element A mit der Eigenschaft: 5 Teiler von d}
Mächtigkeit von D = 1000/5 = 200

2. Mächtigkeit von -> B vereinigt C vereinigt D ermittelt:

= |B| + |C| + |D| - | B geschnitten C | - | B geschnitten D | - | C geschnitten D | + |B geschnitten C geschnitten D|

= 466

Ist das Vorgehen bzw. die Lösung korrekt?

Vielen Dank im voraus! smile

07.04.2017, 17:36

Mathema

Auf diesen Beitrag antworten »

Hallo MioMioMathe_,

Zitat:

Ist [...] die Lösung korrekt?

kannst du dir diese Frage nicht selbst beantworten? Du schreibst es sind 500 Zahlen schon durch 2 teilbar. Laut deiner Antwort sollen nun 466 Zahlen durch 2, 3 oder 5 teilbar sein. Wie soll das funktionieren?

Welche Mächtigkeit haben denn deine Schnittmengen? Da muss ja der Fehler liegen.

07.04.2017, 18:20

Huggy

Auf diesen Beitrag antworten »

RE: Schubfachprinzip - Anzahl Zahlen teilbar durch n Zahlen

Zitat:

Original von MioMioMathe_
= |B| + |C| + |D| - | B geschnitten C | - | B geschnitten D | - | C geschnitten D | + |B geschnitten C geschnitten D|

Das wäre richtig für das nicht ausschließende Oder. Und das hast du auch nicht gerechnet, denn dann müsste das Ergebnis größer 500 sein.

Bei dem ausschließenden Oder sollte sich ergeben:

$\begin{eqnarray*} =|B|+|C|+|D|-2(|B \cap C| +|B \cap D|+ |C \cap D|)+3|B \cap C \cap D| \end{eqnarray*}$

Zitat:

= 466

Ich komme auf 468

07.04.2017, 18:30

Mathema

Auf diesen Beitrag antworten »

Danke Huggy - die Klammer hatte ich tatsächlich überlesen. Dann komme ich auch auf dein Ergebnis. Vorher hatte ich nur die 734 für das nicht ausschließende Oder berechnet. Dir ein schönes Wochenende!

Wink

08.04.2017, 13:43

MioMioMathe

Auf diesen Beitrag antworten »

RE: Schubfachprinzip - Anzahl Zahlen teilbar durch n Zahlen
@Huggy

Vielen Dank! smile

Wenn ich das nach deiner Formel berechne komme ich auch auf 468!

Nur wie kommt man darauf die Schnittmengen einmal mit 2 und mit 3 zu multiplizieren? verwirrt

08.04.2017, 14:52

Huggy

Auf diesen Beitrag antworten »

RE: Schubfachprinzip - Anzahl Zahlen teilbar durch n Zahlen
Man kann darauf sicher mit verschiedenen Methoden kommen. Meine Lieblingsmethode ist der GMV = Gesunder Menschenverstand.

Beginnen wir mit den durch 2 teilbaren Zahlen. Deren Anzahl ist $\begin{eqnarray*} |B| \end{eqnarray*}$ . Die dürfen wir aber nicht alle mitzählen wegen des ausschließenden Oder. Man muss die Zahlen abziehen, die auch noch durch 3 teilbar sind und die, die auch noch durch 5 teilbar sind. Deren Anzahl ist $\begin{eqnarray*} |B \cap C| \end{eqnarray*}$ bzw. $\begin{eqnarray*} |B \cap D| \end{eqnarray*}$ . In $\begin{eqnarray*} |B \cap C| \end{eqnarray*}$ und $\begin{eqnarray*} |B \cap D| \end{eqnarray*}$ sind auch alle Zahlen enthalten. die durch 2, 3 und 5 teilbar sind. Deren Anzahl ist $\begin{eqnarray*} |B \cap C \cap D| \end{eqnarray*}$ . Diese Zahlen haben wir also zweimal abgezogen. Um zum richtigen Ergebnis zu kommen, müssen wir sie wieder einmal addieren. Damit erhält man folgendes Teilresultat

$\begin{eqnarray*} |E_2|=|B|-|B \cap C|-|B\cap D| + |B \cap C \cap D| \end{eqnarray*}$

für die Zahl der durch 2, aber nicht durch 3 und nicht durch 5 teilbaren Zahlen. Analog erhält man

$\begin{eqnarray*} |E_3|=|C|-|B \cap C|-|C\cap D| + |B \cap C \cap D| \end{eqnarray*}$

für die durch 3, aber nicht durch 2 oder 5 teilbaren Zahlen und

$\begin{eqnarray*} |E_5|=|D|-|B \cap D|-|C\cap D| + |B \cap C \cap D| \end{eqnarray*}$

für die durch 5, aber nicht durch 2 oder 3 teilbaren Zahlen. Das Gesamtergebnis ist

$\begin{eqnarray*} |E| = |E_2|+|E_3|+|E_5| \end{eqnarray*}$

Das führt zu meiner Formel.

Der GMV ist ein mächtiges, aber keineswegs unfehlbares Werkzeug. Denkfehler macht jeder mal. Es empfiehlt sich also, eine mit seiner Hilfe abgeleitete Formel auf anderem Weg zu prüfen. In diesem Fall kann man einfach ein Programm durch Abzählen $\begin{eqnarray*} |E| \end{eqnarray*}$ bestimmen lassen. Das ist zwar kein Beweis, dass die Formel allgemein stimmt, erhöht aber signifikant das Vertrauen, keinen Denkfehler gemacht zu haben.

10.04.2017, 21:04

MioMioMathe

Auf diesen Beitrag antworten »

RE: Schubfachprinzip - Anzahl Zahlen teilbar durch n Zahlen
@Huggy

Das ging ja wieder richtig fix mit der Antwort - danke danke! smile

GMV ist ne gute Methode, gefällt mir Big Laugh

Super erklärt, jetzt hats klick gemacht! Bin begeistert, nochmals vielen Dank für die ausführliche Erklärung! smile

11.04.2017, 17:09

HAL 9000

Auf diesen Beitrag antworten »

Für Interessierte:

Das von Huggy geschilderte Prinzip kann man problemslos auf $\begin{align*} n \end{align*}$ Mengen verallgemeinern, sozusagen zu einer "Exklusiv-Oder-Siebformel": Es ist $\begin{align*} \left| A_i \setminus \bigcup_{\substack{j=1\\j\neq i}}^n A_j \right| = \left|A_i\right| - \left| \bigcup_{\substack{j=1\\j\neq i}}^n (A_i\cap A_j) \right| = \sum_{J\subset \{1,\ldots,n\}\setminus \{i\}} (-1)^{|J|} \cdot \left| A_i\cap \bigcap_{j\in J} A_j \right| \end{align*}$ gemäß normaler Siebformel. Dies nun über alle $\begin{align*} i \end{align*}$ summiert ergibt

$\begin{align*} \left| \bigcup_{i=1}^n \left[ A_i \setminus \bigcup_{\substack{j=1\\j\neq i}}^n A_j \right] \right| = \sum_{i=1}^n \sum_{J\subset \{1,\ldots,n\}\setminus \{i\}} (-1)^{|J|} \cdot \left| A_i\cap \bigcap_{j\in J} A_j \right| \stackrel{!}{=} \sum_{I\subset \{1,\ldots,n\}} (-1)^{|I|-1}{\color{red}\cdot |I|}\cdot \left| \bigcap_{j\in I} A_j \right| \end{align*}$ .

Über den letzten Schritt $\begin{align*} \stackrel{!}{=} \end{align*}$ muss man sicher ein wenig nachdenken, ohne dass es aber größeres Kopfzerbrechen bereiten sollte. Augenzwinkern

Neue Frage »

Antworten »

Schubfachprinzip - Anzahl Zahlen teilbar durch n Zahlen

Verwandte Themen