Difference between revisions of "TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 193"

From VoWi
Jump to navigation Jump to search
(Schwachsinn löschen.)
Line 39: Line 39:
 
   40 Zahlen.
 
   40 Zahlen.
 
Also obige Lösung stimmt, nun gilt es nur noch zu verstehen warum *g*
 
Also obige Lösung stimmt, nun gilt es nur noch zu verstehen warum *g*
 
 
Edit: Dieses Programm gibt alle Zahlen aus die nicht durch 9 und nicht durch 11 teilbar sind und es kommt auf 40 Zahlen, aber die Angabe "weder
 
durch 9 noch durch 11" ist ja ein Exklusives ODER also müssen die beiden Zahlen 495 und 990 die alle vier Zahlen als Teiler haben dazugezählt werden was es dann auf 42 Zahlen kommen lässt.
 
Hier das abgeänderte kleine Programm
 
 
public static void main(String[] args) {
 
int blubb[] = new int[43];
 
int counter=0;
 
for (int i=1; i<=1000; i++){
 
if (i%3 == 0 && i%5 == 0 && ((i%9 != 0 && i%11 != 0) || (i%9 == 0 && i%11 == 0))){
 
counter++;
 
blubb[counter] = i;
 
System.out.println(blubb[counter] + " " +counter);
 
 
}
 
 
 
}
 
System.out.println(counter + " Zahlen. ");
 
}
 
}
 
Also entweder ist beim ersten Lösungsvorschlag etwas falsch da er trotz der beiden Zahlen  495 und 990 die er dazuzählt nur auf 40 kommt oder das Programm ist falsch.
 
  
 
= Anmerkungen =
 
= Anmerkungen =

Revision as of 17:50, 11 December 2016

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

  • 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

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, ..., 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.