Rechenaufgaben

[kad]

Spoiler

Genau. Das war ein wenig brute force. Aber es stimmt. Bravo.

Spoiler

Na ja, vielleicht gehts ja auch noch etwas "mathematischer".

Die Folge der 3'er Reste für 2n über n ist ja durchaus simpel.
Wir nehmen einen Block (A) und ergänzen diesen mit den gleich grossen Blöcken 2A und 3A
wobei wir für 2A die Zahlen von A mit 2 und für 3A die Zahlen von A mit 3 multiplizieren
und wieder mod 3 nehmen.
x1 0->0,1->1,2->2 (bleibt gleich)
x2 1->2, 2->1, 0 -> 0
x3 0,1,2 -> 0
Wir beginnen mit einem Block der Länge 1 und dem Inhalt 1 für n=0
A0 (Länge 1)=[1]
A' (Länge 3) = [1],[2],[0]
A'' (Länge 9) = [1,2,0],[2,1,0],[0,0,0]
A''' (Länge 27) = [1,2,0,2,1,0,0,0,0],[2,1,0,1,2,0,0,0,0],[0,0,0,0,0,0,0,0,0]
....

Aber eigentlich interessiert uns ja gar nicht, ob der Rest nun 1 oder 2 ist,
sondern lediglich, ob dieser 0 ist.
Da bei sich bei einer Multiplikation mit 2 die Teilbarkeit nicht ändern,
reicht auch einfach die Teilbarkeitsinfo 0 (teilbar) oder 1 (nicht teilbar) zu vervielfältigen.

-> A''' (Länge 27) = [1,1,0,1,1,0,0,0,0],[1,1,0,1,1,0,0,0,0],[0,0,0,0,0,0,0,0,0]

Da sich die länge mit jedem Schritt verdreifacht, ist der gesuchte Block mit Länge >= 1000
in 7 Schritten gefunden, da A7 bereits die Länge 3^7 hat.

Nun kann Rest von (2n über n) mod 3 kann an der Stelle n direkt abgelesen werden,
oder aber auch rekuriv bestimmt werden.

Jeder Block der Länge 3^i hat drei Teile:
T1= Die Teilbarkeits-Info des Blockes der Länge 3^(i-1)
T2 = Die Teilbarkeits-Info des Blockes der Länge 3^(i-1)
T3 = Ein Block mit nur 0'en der Länge 3^(i-1)

A7= [A6][A6][0...0] mit jeweils 729 "bit".

Ist n im dritten BLock ist die Teilbarkeit gegeben
ist n im ersten Block, schauen wir uns die Teilbarkeiten in A6 an
ist n im zweiten Block, ziehen wir von n 3^6 ab und schauen uns ebenfalls A6 an

Spätestens bei n=0 sind wir fertig und stelle fest, dass die Teilbarkeit in diesem Fall nicht gegeben ist.

Die Frage ist nun, ob es auch noch eine kompakte Formel f(n) gibt, die das abbildet.

Spoiler

Man kann zeigen

(2n über n) ist genau dann durch 3 teilbar, wenn für wenigstens ein k ≥ 1 die Ungleichung 1/2 ≤ frac(n/3k) < 1 gilt, und dies wiederum ist genau dann der Fall, wenn n in seiner Darstellung im Dreiersystem eine Ziffer 2 enthält.
Es ist nun relativ leicht, die Anzahl dieser n zu bestimmen – wir zählen einfach diejenigen n, die keine 2 in ihrer Dreierdarstellung enthalten, und ziehen die erhaltene Anzahl von 1000 ab. Wie viele n zwischen 1 und 1000 haben nun keine 2 in ihrer Dreierdarstellung?
Wegen 1000 = [1101001] (in Basis 3) gibt es genau die den 105 Binärdarstellungen der Zahlen
von 1 bis 105 = [1101001] (in Basis 2) entsprechenden Dreierdarstellungen von Zahlen n mit
der geforderten Eigenschaft. Für alle anderen 1000 − 105 = 895 Zahlen n zwischen
1 und 1000 ist also 2n über n durch 3 teilbar.

frac(x) bezeichnet den gebrochenen Anteil der nichtnegativen reellen Zahl x, also frac(x) = x−⌊x⌋.

[giffi marauder]

Spoiler

Man kann zeigen

(2n über n) ist genau dann durch 3 teilbar, wenn für wenigstens ein k ≥ 1 die Ungleichung 1/2 ≤ frac(n/3k) < 1 gilt, und dies wiederum ist genau dann der Fall, wenn n in seiner Darstellung im Dreiersystem eine Ziffer 2 enthält.
Es ist nun relativ leicht, die Anzahl dieser n zu bestimmen – wir zählen einfach diejenigen n, die keine 2 in ihrer Dreierdarstellung enthalten, und ziehen die erhaltene Anzahl von 1000 ab. Wie viele n zwischen 1 und 1000 haben nun keine 2 in ihrer Dreierdarstellung?
Wegen 1000 = [1101001] (in Basis 3) gibt es genau die den 105 Binärdarstellungen der Zahlen
von 1 bis 105 = [1101001] (in Basis 2) entsprechenden Dreierdarstellungen von Zahlen n mit
der geforderten Eigenschaft. Für alle anderen 1000 − 105 = 895 Zahlen n zwischen
1 und 1000 ist also 2n über n durch 3 teilbar.

frac(x) bezeichnet den gebrochenen Anteil der nichtnegativen reellen Zahl x, also frac(x) = x−⌊x⌋.

Spoiler

Ich mach mal die Probe auf meine Art:
Länge 3 -> 1 Teilbarkeit
Länge 9-> 2x1+3=5
Länge 27-> 2x5+9=19
Länge 81-> 2x19+27=65
Länge 243 -> 2x65+81=211
Länge 729 -> 2x211+243=665
1000 (729+271) -> 665 Teilbarkeiten (für die ersten 729 Zahlen)
271 (243+28) -> 665+211=876 (für die ersten 729+271=972 Zahlen)
28 (27+1) -> 876+19=895 (für die ersten 972+27=999 Zahlen)
1 -> 895+0=895 (für alle 999+1=1000 Zahlen)
Also ja, 895 stimmt.

[kad]

Spoiler

Man kann zeigen

(2n über n) ist genau dann durch 3 teilbar, wenn für wenigstens ein k ≥ 1 die Ungleichung 1/2 ≤ frac(n/3k) < 1 gilt, und dies wiederum ist genau dann der Fall, wenn n in seiner Darstellung im Dreiersystem eine Ziffer 2 enthält.
Es ist nun relativ leicht, die Anzahl dieser n zu bestimmen – wir zählen einfach diejenigen n, die keine 2 in ihrer Dreierdarstellung enthalten, und ziehen die erhaltene Anzahl von 1000 ab. Wie viele n zwischen 1 und 1000 haben nun keine 2 in ihrer Dreierdarstellung?
Wegen 1000 = [1101001] (in Basis 3) gibt es genau die den 105 Binärdarstellungen der Zahlen
von 1 bis 105 = [1101001] (in Basis 2) entsprechenden Dreierdarstellungen von Zahlen n mit
der geforderten Eigenschaft. Für alle anderen 1000 − 105 = 895 Zahlen n zwischen
1 und 1000 ist also 2n über n durch 3 teilbar.

frac(x) bezeichnet den gebrochenen Anteil der nichtnegativen reellen Zahl x, also frac(x) = x−⌊x⌋.

Spoiler

Ich mach mal die Probe auf meine Art:
Länge 3 -> 1 Teilbarkeit
Länge 9-> 2x1+3=5
Länge 27-> 2x5+9=19
Länge 81-> 2x19+27=65
Länge 243 -> 2x65+81=211
Länge 729 -> 2x211+243=665
1000 (729+271) -> 665 Teilbarkeiten (für die ersten 729 Zahlen)
271 (243+28) -> 665+211=876 (für die ersten 729+271=972 Zahlen)
28 (27+1) -> 876+19=895 (für die ersten 972+27=999 Zahlen)
1 -> 895+0=895 (für alle 999+1=1000 Zahlen)
Also ja, 895 stimmt.

Spoiler

Wunderbar!
Und jetzt zurück zum Kristall

[kad]

Ein zerstreuter Mathematiker hat n Briefe geschrieben, die er zuklebt, bevor er die Adressen auf die Umschläge geschrieben hat. Anschließend schreibt er die Adressen einfach zufällig auf die Umschläge. Wie groß ist die Wahrscheinlichkeit, dass keiner der Briefe richtig adressiert ist?

[giffi marauder]

Ein zerstreuter Mathematiker hat n Briefe geschrieben, die er zuklebt, bevor er die Adressen auf die Umschläge geschrieben hat. Anschließend schreibt er die Adressen einfach zufällig auf die Umschläge. Wie groß ist die Wahrscheinlichkeit, dass keiner der Briefe richtig adressiert ist?

Spoiler

Schaun mer mal für kleine Zahlen.
sei m=f(n) die gesuchte Zahl
n:m
1:0
2:1
3:2
4:3*3
5:4*11

ok, das riecht nach Rekursion.

5: 4*11=4(9+2) = 4*(f(4)+f(3))
4: 3*2=3*(2+1) = 3* (f(3)+f(1))
3: 2= 2(1+0) = 2* (f(2)+f(1))

f(n)=(n-1)*[f(n-1)+f(n-2)]?

Der Multiplikator (n-1) ist noch klar, da für den "ersten" Umschlang (n-1) Adressen in Frage kommen.
bleiben noch (n-1) Umschläge und Adressen über.
Aber warum nicht einfach f(n)=(n-1)*f(n-1)?

Ah, einer alleine kann ja nicht falsch sein.

Schreiben wir das obigen doch mal anders an.
f(n)=(n-1)*f(n-1) + (n-1)*f(n-2)

Hier werden also 2 Fälle unterschieden.

Fall 1:
Die Adresse vom ersten Umschlag befindet sich benau auf dem Umschlag der zur Adresse gehört,
die auf dem ersten Umschlag klebt
Dafür gibts (n-1) Möglichkeiten und ohne diese beiden Adressen reduziert sich das Problem auf (n-1)*f(n-2)
Ok, das erklärt den rechten Term.

Fall 2:
Ist das nicht allerdings nicht der Fall, gibts für die "erste" Adresse dann (n-2) Möglichkeiten.
und für die anderen Adressen noch x Möglichkeiten.

Damit haben wir (n-1)*(n-2)*x = (n-1)*f(n-1)
(n-2)*x = f(n-1)
(n-2)*x = (n-2)*(f(n-2)+f(n-3))
x= f(n-2)+f(n-3)


tbc.

[kad]

Ein zerstreuter Mathematiker hat n Briefe geschrieben, die er zuklebt, bevor er die Adressen auf die Umschläge geschrieben hat. Anschließend schreibt er die Adressen einfach zufällig auf die Umschläge. Wie groß ist die Wahrscheinlichkeit, dass keiner der Briefe richtig adressiert ist?

Spoiler

Schaun mer mal für kleine Zahlen.
sei m=f(n) die gesuchte Zahl
n:m
1:0
2:1
3:2
4:3*3
5:4*11

ok, das riecht nach Rekursion.

5: 4*11=4(9+2) = 4*(f(4)+f(3))
4: 3*2=3*(2+1) = 3* (f(3)+f(1))
3: 2= 2(1+0) = 2* (f(2)+f(1))

f(n)=(n-1)*[f(n-1)+f(n-2)]?

Der Multiplikator (n-1) ist noch klar, da für den "ersten" Umschlang (n-1) Adressen in Frage kommen.
bleiben noch (n-1) Umschläge und Adressen über.
Aber warum nicht einfach f(n)=(n-1)*f(n-1)?

Ah, einer alleine kann ja nicht falsch sein.

Schreiben wir das obigen doch mal anders an.
f(n)=(n-1)*f(n-1) + (n-1)*f(n-2)

Hier werden also 2 Fälle unterschieden.

Fall 1:
Die Adresse vom ersten Umschlag befindet sich benau auf dem Umschlag der zur Adresse gehört,
die auf dem ersten Umschlag klebt
Dafür gibts (n-1) Möglichkeiten und ohne diese beiden Adressen reduziert sich das Problem auf (n-1)*f(n-2)
Ok, das erklärt den rechten Term.

Fall 2:
Ist das nicht allerdings nicht der Fall, gibts für die "erste" Adresse dann (n-2) Möglichkeiten.
und für die anderen Adressen noch x Möglichkeiten.

Damit haben wir (n-1)*(n-2)*x = (n-1)*f(n-1)
(n-2)*x = f(n-1)
(n-2)*x = (n-2)*(f(n-2)+f(n-3))
x= f(n-2)+f(n-3)


tbc.

Spoiler

Ich glaube deine Rekursionsformel stimmt. Nur: mir ist nicht gelungen, sie zu “verstehen”. Noch konnte ich daraus die geschlossene Formel für f(n) ableiten - und ich habe einiges ausprobiert.
Jetzt bin ich auf dein tbc gespannt.

Ich hatte einen anderen Weg gewählt: alle möglichen Adressierungen minus denen, wo mindestens eine Adresse korrekt ist…..

[giffi marauder]

Spoiler

Ich glaube deine Rekursionsformel stimmt. Nur: mir ist nicht gelungen, sie zu “verstehen”. Noch konnte ich daraus die geschlossene Formel für f(n) ableiten - und ich habe einiges ausprobiert.
Jetzt bin ich auf dein tbc gespannt.

Spoiler

Am Freitag am Friedhof kam mir die Erleuchtung.

Wir schreiben eine falsche Adresse auf Umschlag 1.
Dafür gibts (n-1) Möglichkeiten

Dann unterscheiden wir 2 Fälle.

1. Die Adresse vom ersten Umschlag befindet sich genau auf dem Umschlag der zur Adresse gehört,
die auf dem ersten Umschlag steht.
Damit sind zwei Umschläge und zwei Adressen aus dem Spiel und für den Rest gilt f(n-2) (zweiter Summand)

2. Die Adresse vom ersten Umschlag befindet sich nicht auf dem Umschlag der zur Adresse gehört,
die auf dem ersten Umschlag steht.
Meine ursprüngliche Annahme, die erste Adresse könnte nun überall stehen, ist damit aber falsch.
Auch diese Adresse darf genau auf einem Umschlag nicht stehen, sonst hätten wir ja Fall 1.
Damit ist ein Umschlag und eine Adresse aus dem Spiel und wir wir haben noch n-1 Adressen (inkl. der ersten),
die auf alle bis auf genau einem Umschlag stehen dürfen. -> f(n-1) (erster Summand)

f(n)=(n-1)*[f(n-1) + f(n-2)]

Kompakte Formel habe ich auch noch nicht gefunden.

Ich hatte einen anderen Weg gewählt: alle möglichen Adressierungen minus denen, wo mindestens eine Adresse korrekt ist…..

Diesen Versuch habe ich nach zwei Seiten voll gekritzelt mit Wahrscheinlichkeiten und Gegenwahrscheinlichkeiten aufgegeben.

[kad]

Spoiler

Ich glaube deine Rekursionsformel stimmt. Nur: mir ist nicht gelungen, sie zu “verstehen”. Noch konnte ich daraus die geschlossene Formel für f(n) ableiten - und ich habe einiges ausprobiert.
Jetzt bin ich auf dein tbc gespannt.

Spoiler

Am Freitag am Friedhof kam mir die Erleuchtung.

Wir schreiben eine falsche Adresse auf Umschlag 1.
Dafür gibts (n-1) Möglichkeiten

Dann unterscheiden wir 2 Fälle.

1. Die Adresse vom ersten Umschlag befindet sich genau auf dem Umschlag der zur Adresse gehört,
die auf dem ersten Umschlag steht.
Damit sind zwei Umschläge und zwei Adressen aus dem Spiel und für den Rest gilt f(n-2) (zweiter Summand)

2. Die Adresse vom ersten Umschlag befindet sich nicht auf dem Umschlag der zur Adresse gehört,
die auf dem ersten Umschlag steht.
Meine ursprüngliche Annahme, die erste Adresse könnte nun überall stehen, ist damit aber falsch.
Auch diese Adresse darf genau auf einem Umschlag nicht stehen, sonst hätten wir ja Fall 1.
Damit ist ein Umschlag und eine Adresse aus dem Spiel und wir wir haben noch n-1 Adressen (inkl. der ersten),
die auf alle bis auf genau einem Umschlag stehen dürfen. -> f(n-1) (erster Summand)

f(n)=(n-1)*[f(n-1) + f(n-2)]

Kompakte Formel habe ich auch noch nicht gefunden.

Ich hatte einen anderen Weg gewählt: alle möglichen Adressierungen minus denen, wo mindestens eine Adresse korrekt ist…..

Diesen Versuch habe ich nach zwei Seiten voll gekritzelt mit Wahrscheinlichkeiten und Gegenwahrscheinlichkeiten aufgegeben.

Spoiler

Lösung

Spoiler

Um die Lösung zu verstehen ist es hilfreich etwas über das Prinzip von Inklusion und Exklusion zu verstehen.

https://de.wikipedia.org/wiki/Prinzip_v ... _Exklusion

Wir haben die Anzahl der möglichen Adressierungen zu bestimmen, bei denen kein Brief den richtigen Namen trägt. Die Anzahl aller möglichen Adressierungen ist klarerweise n!. Nun bestimmen wir die Anzahl der Adressierungen, bei denen eine gewisse Menge Z ⊆ {1,2,...,n} von Briefen (die Briefe werden der Einfachheit halber mit 1,2,...,n durchnummeriert) die richtige Adresse trägt.
Wenn m = |Z| Briefe richtig adressiert sind, dann bleiben noch n−m Briefe übrig, für die es (n − m)! Möglichkeiten zur Beschriftung gibt. Daher ist die Anzahl der Adressierungen, bei denen eine Menge Z richtig adressiert wird, genau gleich (n − |Z|)!. Es folgt nach Inklusion/Exklusion für die gesuchte Anzahl

n! - Summe{k=1 bis n} Summe{Z⊆{1,...,n}; |Z|=k} ((-1)^(k-1) * (n-k)!)

Da es genau n über k = n!/k!(n-k)! Teilmengen Z der Grösse k gibt, vereinfacht sich dies zu
n! - Summe{k=1 bis n} ((-1)^(k-1) * n!/k!)
=
n! * Summe{k=0 bis n} ((-1)^k * k!)

Die Wahrscheinlichkeit, dass kein Brief richtig adressiert ist, beträgt damit

Summe{k=0 bis n} ((-1)^k * k!) = 1 - 1 + 1/2 - 1/6 + 1/24 …. +- 1/n!

Das strebt gegen 1/e = 0.367879….

[kad]

Gibt es 2 irrationale Zahlen x und y, für die x hoch y rational ist?

[giffi marauder]

Gibt es 2 irrationale Zahlen x und y, für die x hoch y rational ist?

Spoiler

sqrt(2) und sqrt(3) sind irrational.

[sqrt(3) ^ sqrt(2)] ^ sqrt(2) = sqrt(3) ^ (sqrt(2)*sqrt(2))= sqrt(3)^2=3

Entweder ist das Innere von [] schon rational oder falls nicht,
dann jedenfalls das in diesem Fall irrationale Innere von [] ^ sqrt(2)

So oder so, also ja.

[kad]

In einer Schulklasse befinden sich 25 Kinder, 15 Knaben und 10 Mädchen. Die Lehrerin wählt zufällig 2 Kinder aus. Sie bemerkt, dass die Wahrscheinlichkeit dafür, dass eine geschlechtergemischte Zweiergruppe entsteht, gerade 1/2 beträgt.
Mit welchen andern Personenzahlen (Klassengrösse, Anzahl Knaben bzw. Mädchen) wäre die Wahrscheinlichkeit ebenfalls 1/2, beim zufälligen Auswählen von 2 Personen eine geschlechtergemischte Zweiergruppe zu erhalten?

[kad]

Gibt es 2 irrationale Zahlen x und y, für die x hoch y rational ist?

Spoiler

sqrt(2) und sqrt(3) sind irrational.

[sqrt(3) ^ sqrt(2)] ^ sqrt(2) = sqrt(3) ^ (sqrt(2)*sqrt(2))= sqrt(3)^2=3

Entweder ist das Innere von [] schon rational oder falls nicht,
dann jedenfalls das in diesem Fall irrationale Innere von [] ^ sqrt(2)

So oder so, also ja.

Spoiler

So ist es!

[kad]

Eine Ebene schneide einen Kegel in einer Ellipse. Des Weiteren seien k und K diejenigen beiden Kugeln, die den Kegel von innen in einem ganzen Kreis sowie die Ebene berühren. Hierbei berühre k die Ebene in A und K die Ebene in B. Zeige, dass dann A und B die beiden Brennpunkte der Ellipse sind, dass also für jeden Punkt P auf dem Rand der Ellipse die Summe der Abstände AP + BP gleich ist. Drücke diesen Wert auch durch die Radien der beiden Kugeln und den Abstand ihrer Mittelpunkte aus!

[giffi marauder]

In einer Schulklasse befinden sich 25 Kinder, 15 Knaben und 10 Mädchen. Die Lehrerin wählt zufällig 2 Kinder aus. Sie bemerkt, dass die Wahrscheinlichkeit dafür, dass eine geschlechtergemischte Zweiergruppe entsteht, gerade 1/2 beträgt.
Mit welchen andern Personenzahlen (Klassengrösse, Anzahl Knaben bzw. Mädchen) wäre die Wahrscheinlichkeit ebenfalls 1/2, beim zufälligen Auswählen von 2 Personen eine geschlechtergemischte Zweiergruppe zu erhalten?

Spoiler

Betrachten wir die Wahrscheinlichkeiten mal als Flächen von (j+m)^2 bzw. j^2+2jm+m^2
j^2 /(j+m)^2 ist die Wahrscheinlichkeit für 2 Jungen
m^2/(j+m)^2 ist die Wahrscheinlichkeit für 2 Mädchen
2mj/(j+m)^2 ist die Wahrscheinlichkeit für gemischt

In diesem Fall also:
(15+10)^2=625
15^2/625=0,36
10^2/625=0,16
2*15*10=0,48
Also 50% sind das ja nun nicht.

Habe ich das was falsch verstanden?

[kad]

In einer Schulklasse befinden sich 25 Kinder, 15 Knaben und 10 Mädchen. Die Lehrerin wählt zufällig 2 Kinder aus. Sie bemerkt, dass die Wahrscheinlichkeit dafür, dass eine geschlechtergemischte Zweiergruppe entsteht, gerade 1/2 beträgt.
Mit welchen andern Personenzahlen (Klassengrösse, Anzahl Knaben bzw. Mädchen) wäre die Wahrscheinlichkeit ebenfalls 1/2, beim zufälligen Auswählen von 2 Personen eine geschlechtergemischte Zweiergruppe zu erhalten?

Spoiler

Betrachten wir die Wahrscheinlichkeiten mal als Flächen von (j+m)^2 bzw. j^2+2jm+m^2
j^2 /(j+m)^2 ist die Wahrscheinlichkeit für 2 Jungen
m^2/(j+m)^2 ist die Wahrscheinlichkeit für 2 Mädchen
2mj/(j+m)^2 ist die Wahrscheinlichkeit für gemischt

In diesem Fall also:
(15+10)^2=625
15^2/625=0,36
10^2/625=0,16
2*15*10=0,48
Also 50% sind das ja nun nicht.

Habe ich das was falsch verstanden?

Spoiler

Schau es anders an.

Aus 25 Kindern 2 auszulesen ist 25 über 2. das ist 25*24/2=300.
15 Knaben und 10 Mädchen kann man auf 15*10 Arten kombinieren.
150/300=1/2.

Jetzt musst du nur noch den Fehler bei deiner Überlegung finden….