TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 200

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von der Lerngruppe vom 28.12.2005

• 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\ast 5}=66$

$|A\cap B|=\frac{1000}{\underset{3gek.!}{\underbrace{9\ast 5}}}=22$

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

$|A\cap B\cap C|=\frac{1000}{\underset{3gek.!}{\underbrace{9\ast 5\ast 11}}}=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

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

Die Zahlen die durch $3$ teilbar sind: Jede Zahl $k\cdot 3$ für alle $k\in \{1,2,\mathrm{...},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}{ccccc}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✓$

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.