Abzählung in der Kombinatorik

Aufrufe: 651     Aktiv: 10.08.2020 um 14:34
1

Hallo Leute,

ich hab da eine Aufgabe aus einer alten Klausur. Ich hab das letztes Jahr noch gelöst, aber ich weiß nicht mehr wie. Man musste irgendwas mit den Potenzen und einer +1 machen um darauf zu kommen, wenn ich mich nicht irre. aber ich weiß nicht mehr was :/

Wie viele Zahlen 1 \le n \le 10^30 sind weder der Form k^6, noch von der Form k^10, noch von der Form k^15 für k \in N?

 

EDIT:

das ist das Prinzip von Inklusion und Exklusion. So weit bin ich jetzt gekommen. ich habe eine vergleichbare Aufgabe mit Lösung gefunden. Aber ich weiß noch nicht genau warum es so gemacht wird. In der Lösung wird dann theoretisch die 10^30 in dem Fall (das ist die Vereinigung?) auch verrechnet so dass p = 10^30-|A|-|B|-|C|+|A \cap B|+|A \cap C|+|B \cap C|-|A \cap B \cap C|. 10^30 ist dann wohl die Vereinigung der drei Mengen.

Nun kann man theoretisch, da es Teiler sind, die k^i raus teilen.
A(E_6) = 10^(30/6) = 10^5
B(E_10) = 10^(30/10) = 10^3
C(E_15) = 10^(30/15) =  10^2
A \cap B (E_6,E_10) = 10^(1/2)
A \cap C (E_6,E_15) = 10^(1/3)
B \cap C (E_10,E_15) = 10^(1/5)
A \cap B \cap C(E_6,E_10,E_15) = 10^(1/30)

und da wir ja nur ganzzahlige Teiler aus N suchen, werden alle Werte mit der Abrundungsfunktion berechnet. Wie geht es un weiter? Wenn ich die Verinigung suche ist es klar, aber suche ich überhaupt die Vereinigung? Wie man oben sieht, hab ich die Verinigung ja schon und es wird alles nach 0 umgestellt und der Wert der rauskommt, interessiert. wieso? was ist das für ein Wert?

Wie kann ich die Werte handschriftlich berechnen?

Diese Frage melden
gefragt

Student, Punkte: 66

 
Kommentar schreiben
2 Antworten
2

Entschuldige bitte, ich glaube ich habe nicht weit genug gelesen, um dein eigentliches problem zu verstehen.

du scheinst nämlich die schnitte nicht ganz richtig zu berechnen.

Aber klar gibt es sehr große ähnlichkeit zu der teiler aufgabe.

 

Für gegebenes element \(x\) betrachte dessen primfaktorzerlegung.

Damit ein element \(x\) in \( A \cap B \) enthalten ist, muss gelten, dass sich die potenz jedes primfaktors von  \(x\) durch 6 und durch 10 teilen lässt (hier kurz nachdenken, wieso das äquivalent zu der eigentlichen bedeutung von \( A \cap B\) ist) . insgesamt müssen sich die potenzen der primfaktoren also durch 30=kgV(10,6) teilen lassen. das bedeutet aber schon, dass \( x = a^{30} \) mit \( a \in {1, \dots , 10}\) . dementsprechend gilt \( | A \cap B | = 10 \). Mit selber rechnung erhält man, dass alle schnitte gleichmächtig bzw gleich sind. 

Es gilt natürlich genau \( p = | A \cup B \cup C| \). Von anfang an war ja dein ziel, die mächtigkeit einer nicht-disjunkten vereinigung auszurechnen - deswegen die siebformel. 

habt ihr das bei euch einfach p genannt? ansich sollte natürlich aus dem kontext eurer vl schon klar sein, dass damit die vereinigung gemeint ist - ansonst einfach siebformel googlen.

Diese Antwort melden
geantwortet

Student, Punkte: 2.33K

 
WIr haben das Prinzip von I&E eingeführt, aber es nie Siebformel genannt. Habe es gerade gegoogelt, das ist die allgemeine Idee für n Mengen. Check, verstanden. :D

Ok. Die Primfaktorzerlegung der 30 ist ja gerade die 2*3*5, verstehe. Dh. damit nun x durch 6 und 10 teilbar sein kann, muss es auch durch die Primfaktorzerlegung möglich sein hier: 6=2*3 und dadurch die 30 usw. ok habs verstanden. das ist ja mal interessant.

Also suche ich beim Schnitt aller drei das kgV(6,10,15), daran hab ich nicht gedacht. daran erinnere ich mich noch aus letztem Jahr, jetzt wo du es sagst. So macht man es ja auch bei der Teileraufgabe. Das Würde nun bedeuten, dass p=10^30-10^5-10^3-10^2+10+10+10-10 ist, richtig? Kann man das noch weiter zusammenfassen ohne Taschenrechner?   ─   labis.theodoros 10.08.2020 um 12:50
ja genau, angenommen du wärst in einer mathe klausur, könntest du das denke ich mal so stehen lassen (ich würde volle punktzahl geben). ansich ist gibt die potenz bei der 10 ja aber nur die anzahl der 0en an, insofern sollte es auch nicht schwierig sein, dass konkrete ergebnis per hand auszurechnen. würde es aber nicht empfehlen, weil die 10^30 allein ja schon ne zahl mit 30 nullen ist..   ─   b_schaub 10.08.2020 um 13:38
danke schön. wenn das am freitag dran kommt und ich das richtig mache, ist es dir verdankt :)   ─   labis.theodoros 10.08.2020 um 14:34

Kommentar schreiben

2

Dein erster vorschlag kilngt doch schon gar nicht schlecht. ich mach das für ^6 mal als beispiel, den rest kriegst du dann bestimmt selbst hin.

Wir suchen \(n \in \mathbb{N} \) mit \(n^6 \leq 10^{30} ; (n+1)^6 > 10^{30}\).
Dafür rechnen wir \(10^{30} = 10^{5 \cdot 6} = (10^5)^6\).

Heißt also dass jede zahl kleiner gleich \( 10^5\) hoch 6 auch kleiner gleich \(10^{30}\) ist.

hoffe das hilft dir weiter sonst frag nochmal nach :)

Diese Antwort melden
geantwortet

Student, Punkte: 2.33K

 
Danke! Das ist mal ne interessante Art das anzugehen. So kannte ich das noch nicht! Aber deutlich ansehnlicher und verständlicher. Ich verstehe aber nicht, wieso du n+1 machst. Weil Jede Zahl gemeint sein kann? ist aber nur eine Formalie, richtig? Weil wie man der Zeile darunter entnehmen kann, wird das gar nicht weiter berücksichtigt.

Ich habe nun für alle Mengen und Schnittmengen von A,B,C die Werte (7 Stück) ermittelt und es ist schon mal das selbe wie oben, danke dir! dh. ich weiß nun schon mal wie man solch eine Aufgabe angeht.

In der Lösung der ähnlichen Aufgabe wird die Gleichung null gesetzt und ein Wert p berechnet. Diesert Wert ist: p = 10^30 - (A) -(B) -(C) + (A \cap B) +(A \cap C) +(B \cap C) -(A \cap B \cap C). Die berechneten Werte werden eingesetzt und man erhält die Zahl p.

Fragen:
(i) ist 10^30 meine Vereinigung über A,B und C? Alles andere macht ja keinen Sinn.
(ii) Was sagt dieser Wert p aus? Bisher haben wir diverse Aufgaben gehabt, in denen immer nachgedacht werden musste, wie man das Prinzip von I&E anwendet, um enweder meistens die Schnittmenge aller, oder die Vereinigung zu berechnen, mit umstellen etc. Inwiefern unterscheidet sich die Aufgabe hier mit einer AUfgabe in der es zB geht "Wie viele Teiler von 720 sind durch 4,5 oder 10 teilbar?". Wieso ist in der gepostet Aufgabe das "p" interessant (also der Wert wenn alles auf einer Seite steht) und bei der hier mit der 720 die Vereinigung?
(iii) und wie berechne ich p= 10^30-10^5-10^3-10^2+10^(1/2)+10^(1/3)+10^(1/5)-10^(1/30) handschriftlich? Die Addition von Potenzen ist nicht möglich, wenn Basis / Exponent unterschiedlich sind.


Danke für deine Mühe! Ich hab nun einen Weg, wie ich das nun löse. Trotzdem interessiert mich der Hintergrund etwas mehr und ich würde das gerne komplett verstehen :)

Schönen Sonntag Abend.   ─   labis.theodoros 09.08.2020 um 19:07
Weil latex anscheinend nicht in den kommentaren funktionieren will, hab ich das kommentar stattdessen als 2.antwort geschrieben   ─   b_schaub 10.08.2020 um 10:37

Kommentar schreiben