TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 193

Aus VoWi
Zur Navigation springen Zur Suche springen

Wie viele natürliche Zahlen n mit 1 \leq n \leq 10^3 gibt es, die durch 3 und 5, aber weder durch 9 und 11 teilbar sind.

Lösungsvorschlag von der Lerngruppe vom 28.12.2005[Bearbeiten]

  • A: Menge aller Zahlen, die durch 3 und 5 teilbar sind (entspr. durch 15 teilbar)
  • B: Menge aller Zahlen, die durch 9 teilbar sind
  • C: Menge aller Zahlen, die durch 11 teilbar sind

Wir wollen alle Elemente von A aber ohne B und C haben =>

 |A| - |A \cap B| - |A \cap C| +  |A \cap B \cap C|

|A| = \frac{1000}{3*5} = 66

|A \cap B| = \frac{1000}{\underbrace{9*5}_{3 gek.!}} = 22

|A \cap C| = \frac{1000}{3*5*11} = 6

|A \cap B \cap C| = \frac{1000}{\underbrace{9*5*11}_{3 gek.!}} = 2

66 - 22 - 6 + 2 = 40

40 Zahlen zwischen 1 und 1000 sind durch 3 und 5, aber nicht durch 9 und 11 teilbar.

Kontrolle mit einfachem Java-Programm von fieselschweif[Bearbeiten]

Beispiele wie diese sind bestens dafür geeignet um seine Java-Kenntnisse mit Mathe zu kombinieren, um beim Ergebnis auf Nummer sicher zu gehen ;-)

  public class B163 {                                                         
      public static void main(String[] args) {
          int counter=0;
          for (int i=1; i<=1000; i++)
              if (i%3 == 0 && i%5 == 0 && i%9 != 0 && i%11 != 0)
                  counter++;
          System.out.println(counter + " Zahlen. ");
      }
  }

Bringt den Output:

  40 Zahlen.

Also obige Lösung stimmt, nun gilt es nur noch zu verstehen warum *g*

Anmerkungen[Bearbeiten]

Die Zahlen die durch 3 teilbar sind: Jede Zahl k \cdot 3 für alle k \in \{1, 2, ..., i\}. Das i ist eine ganze Zahl so daß 3 \cdot i <= 1000 sein muss, aber 3 \cdot (i + 1) > 1000 ist. Das i ist auch die Anzahl der Zahlen die durch 3 teilbar sind. Das geht mit Volksschul-Division (Nicht mit Bruchstrichen):


\begin{array}{lllll}
1&0&0&0& : 3 = 333\\
 &1&0\\
 & &1&0\\
 & & &1&R
\end{array}

3 \cdot 333 = 999 < 1000 \wedge 3 \cdot 334 = 1002 > 1000 \quad \checkmark

Gefragt ist aber eigentlich die Anzahl der Zahlen, die durch 3 und 5 teilbar sind. Das entspricht aber der Anzahl der Zahlen, die durch kgV(3, 5) teilbar sind. Warum das kleinste gemeinsame Vielfache (kgV) sollte jeder verstehen. Übrigens kann man das ausrechnen: kgV(3, 5) = \frac{3 \cdot 5}{ggT(3, 5)} = 15, kgV(9, 15) = 45, kgV(11, 15) = 165, kgV(9, 11, 15) = 495. Das Prinzip ist aber dann das gleiche.

Ansonsten bleibt nur mehr das Inklusions-Exklusions-Prinzip zu verstehen. Das haben wir im Buch und in der Vorlesung auch mit 3 Mengen gemacht, und ist eigentlich auch nicht so verblüffend.