Rechenaufgaben

[giffi marauder]

Auf dem Planeten Kappa haben Wissenschaftler kürzlich den Radius ihres Planeten als genau 1000 km bestimmt. Die fünf größten Städte auf Kappa sollen in den nächsten Jahren durch direkte Eisenbahnlinien verbunden werden; in jedem Jahr soll die Strecke zwischen einem Paar von Städten fertig werden. Die Finanzmittel im ersten Jahr reichen allerdings nur für 1571 km an Eisenbahnschienen. Zeige, dass man damit trotzdem den Plan im ersten Jahr verwirklichen kann!

Spoiler

1571km ist knapp mehr als ein Viertel des Umfangs des Planeten (2r*pi/4=1570,79).
Man kann also von einer Stadt, die wir mal einfach am Nordpol plazieren, bis knapp über den Äquator bauen.
Bezeichnen wir diese Fläche als Kuppel.
Die anderen 4 Städte befinden sich also ausserhalb dieser Kuppel auf der Südhalbkugel.
Um die noch freie Fläche zu maximieren, müssen wie die gemeinsame Fläche ebenfalls maximieren.
Wir plazieren Stadt Nr. 2 also ausserhalb der Kuppel von Stadt 1 knapp südlich des Äquators.
Wäre Stadt 2 weiter südlich würde die gemeinsame Fläche kleiner und die Fläche der beiden Kuppeln zusammen umso größer.
Wär Stadt 2 gar am Südpol, wäre gar kein Platz mehr für die anderen 3 Städte.

Die beiden Kuppel "erreichen" nun 3/4 der gesamten Oberfläche.
Stadt 3 plazieren wir nach den gleichen Überlegungen in einen der beiden Schnittpunkte der Kuppeln von 1 und 2.
Bleibt noch 1/8 der Oberfläche frei wobei jeder Punkt dieser freien Fläche innerhalb von 1571km liegt.
Egal wo wir nun Stadt 4 da drin hinsetzten bleibt für Stadt 5 kein freier Platz mehr
und muss sich deshalb innerhalb der Baudistanz zu einer der vier Städte befinden.

[kad]

Auf dem Planeten Kappa haben Wissenschaftler kürzlich den Radius ihres Planeten als genau 1000 km bestimmt. Die fünf größten Städte auf Kappa sollen in den nächsten Jahren durch direkte Eisenbahnlinien verbunden werden; in jedem Jahr soll die Strecke zwischen einem Paar von Städten fertig werden. Die Finanzmittel im ersten Jahr reichen allerdings nur für 1571 km an Eisenbahnschienen. Zeige, dass man damit trotzdem den Plan im ersten Jahr verwirklichen kann!

Spoiler

1571km ist knapp mehr als ein Viertel des Umfangs des Planeten (2r*pi/4=1570,79).
Man kann also von einer Stadt, die wir mal einfach am Nordpol plazieren, bis knapp über den Äquator bauen.
Bezeichnen wir diese Fläche als Kuppel.
Die anderen 4 Städte befinden sich also ausserhalb dieser Kuppel auf der Südhalbkugel.
Um die noch freie Fläche zu maximieren, müssen wie die gemeinsame Fläche ebenfalls maximieren.
Wir plazieren Stadt Nr. 2 also ausserhalb der Kuppel von Stadt 1 knapp südlich des Äquators.
Wäre Stadt 2 weiter südlich würde die gemeinsame Fläche kleiner und die Fläche der beiden Kuppeln zusammen umso größer.
Wär Stadt 2 gar am Südpol, wäre gar kein Platz mehr für die anderen 3 Städte.

Die beiden Kuppel "erreichen" nun 3/4 der gesamten Oberfläche.
Stadt 3 plazieren wir nach den gleichen Überlegungen in einen der beiden Schnittpunkte der Kuppeln von 1 und 2.
Bleibt noch 1/8 der Oberfläche frei wobei jeder Punkt dieser freien Fläche innerhalb von 1571km liegt.
Egal wo wir nun Stadt 4 da drin hinsetzten bleibt für Stadt 5 kein freier Platz mehr
und muss sich deshalb innerhalb der Baudistanz zu einer der vier Städte befinden.

Spoiler

Schon fast etwas unheimlich, wie du Rätsel nach Rätsel löst!
Ich kann nur gratulieren.

[kad]

Die Punkte 1, 2, ..., 1000 auf der Zahlenlinie werden zufällig gepaart, um die Endpunkte von 500 Intervallen zu bilden. Wie hoch ist die Wahrscheinlichkeit, dass sich unter diesen Intervallen eines befindet, das alle anderen schneidet?

[giffi marauder]

Spoiler

Mmh.

Dass bei Unteilbarkeit die Summe bzw. Aufteilung am Ende n*2x (2x,2x,2x...) sein muss ist klar.

Das war mir nicht ganz so klar. Auch weil die Gesamtsumme Sugus ja zunimmt (oder evt gleich bleibt)

Spoiler

Gilt eh nicht immer, sondern nur bei ungerader Anzahl von Kindern.
Damit im letzten Schritt die n Zahlen ungerade sind, müssen sie aus einer Addition einer geraden mit einer ungeraden Zahl entstehen.
Die Hälfte der Vogängerzahlen müssen sich deshalb in der Parität immer abwechseln (2g1,2u1,2g2,2u2....)
Bei ungeradem n ist die Parität der Hälfte des 1. und lezten Gliedes aber gleich woraus jedenfalls eine gerade Zahl resulterit.
-> entweder sind alle Zahlen gerade oder wir sind noch nicht fertig.

Bei gerader Anzahl an Kindern ist dies nicht der Fall.
Da sind sowohl gerade als auch ungerade Lösungen möglich.
4,2,4,2
3,3,3,3

8,4,8,4
6,6,6,6

[giffi marauder]

Die Punkte 1, 2, ..., 1000 auf der Zahlenlinie werden zufällig gepaart, um die Endpunkte von 500 Intervallen zu bilden. Wie hoch ist die Wahrscheinlichkeit, dass sich unter diesen Intervallen eines befindet, das alle anderen schneidet?

Spoiler

Puh.
Nur mal zum Aufwärmen, schaun wir mal wie viele Möglichkeiten P(n) ist da so gibt.
Der erste Punkt kann mit n-1 Punkten kombiniert werden, bleiben n-2 über
die nächst Zahl kann mit n-3 Punkten kombiniert werden, bleiben n-4 über
...
Wir haben also P(n)=(n-1)*(n-3)*...*1 Möglichkeiten Paare zu bilden.
Das sind in kompakter Form (schwubdiwup) sei n=2h
-> P(n)=n!/(h!*2^h) Möglichkeiten.
bzw. per Rekursion P(n+2)=P(n)*(n+1)
was wiederum der obigen Form P(n)= (n-1)*(n-3)*...*7.5.3.1 entspricht.

P(2)= 1
P(4)= 1*(4-1)=3
P(6)= 3*5=15
P(8)=15*7=105
...
Bei n=1000 sind das dann 1000!/(500!*2^500).
Wie gesagt, nur mal zum Aufwärmen.

Das scheint mir zu viel um damit tatsächlich zu rechnen.

Für kleine n (2,4) läßt sich schnell rausfinden, dass die gesuchte Wahrscheinlichkeit jeweils 2/3 ist.
Die Frage die sich nun stellt ist, ob dies womöglich unabhängig von n ist.
Könnten wir das zeigen sind wir auch schon fertig.
Ich denke die Rekursion ist dier Schlüssel dazu.

tbc.

[kad]

Neun 1 x 1 Zellen eines 10 x 10 Quadrats sind infiziert. Innerhalb einer Zeiteinheit werden die Zellen mit mindestens zwei infizierten Nachbarn (mit einer gemeinsamen Seite) infiziert. Kann sich die Infektion auf das gesamte Quadrat ausbreiten?

Spoiler

Nein.

Ok. Fürs Wochenende

Eine Infektion breitet sich unter den n³ Einheitswürfeln eines n x n x n Würfels auf folgende Weise aus: Wenn ein Einheitswürfel drei oder mehr infizierte Nachbarn hat, wird er selbst infiziert. (Nachbarn sind nur orthogonal, daher hat jeder kleine Würfel höchstens sechs Nachbarn.)


Zeige, dass du den gesamten großen Würfel infizieren kannst, beginnend mit nur n² kranken Einheitswürfeln.

[kad]

Die Punkte 1, 2, ..., 1000 auf der Zahlenlinie werden zufällig gepaart, um die Endpunkte von 500 Intervallen zu bilden. Wie hoch ist die Wahrscheinlichkeit, dass sich unter diesen Intervallen eines befindet, das alle anderen schneidet?

Spoiler

Puh.
Nur mal zum Aufwärmen, schaun wir mal wie viele Möglichkeiten P(n) ist da so gibt.
Der erste Punkt kann mit n-1 Punkten kombiniert werden, bleiben n-2 über
die nächst Zahl kann mit n-3 Punkten kombiniert werden, bleiben n-4 über
...
Wir haben also P(n)=(n-1)*(n-3)*...*1 Möglichkeiten Paare zu bilden.
Das sind in kompakter Form (schwubdiwup) sei n=2h
-> P(n)=n!/(h!*2^h) Möglichkeiten.
bzw. per Rekursion P(n+2)=P(n)*(n+1)
was wiederum der obigen Form P(n)= (n-1)*(n-3)*...*7.5.3.1 entspricht.

P(2)= 1
P(4)= 1*(4-1)=3
P(6)= 3*5=15
P(8)=15*7=105
...
Bei n=1000 sind das dann 1000!/(500!*2^500).
Wie gesagt, nur mal zum Aufwärmen.

Das scheint mir zu viel um damit tatsächlich zu rechnen.

Für kleine n (2,4) läßt sich schnell rausfinden, dass die gesuchte Wahrscheinlichkeit jeweils 2/3 ist.
Die Frage die sich nun stellt ist, ob dies womöglich unabhängig von n ist.
Könnten wir das zeigen sind wir auch schon fertig.
Ich denke die Rekursion ist dier Schlüssel dazu.

tbc.

Spoiler

Du bist auf der richtigen Fährte. Rekursion hilft, aber auch eine geeignete Beschriftung der Intervalle.

[kad]

Finde alle 3-stelligen Zahlen m, welche durch 11 teilbar sind mit der Eigenschaft, dass m/11 gleich der Summe der Quadrate der Ziffern von m ist.

[giffi marauder]

Neun 1 x 1 Zellen eines 10 x 10 Quadrats sind infiziert. Innerhalb einer Zeiteinheit werden die Zellen mit mindestens zwei infizierten Nachbarn (mit einer gemeinsamen Seite) infiziert. Kann sich die Infektion auf das gesamte Quadrat ausbreiten?

Spoiler

Nein.

Ok. Fürs Wochenende

Eine Infektion breitet sich unter den n³ Einheitswürfeln eines n x n x n Würfels auf folgende Weise aus: Wenn ein Einheitswürfel drei oder mehr infizierte Nachbarn hat, wird er selbst infiziert. (Nachbarn sind nur orthogonal, daher hat jeder kleine Würfel höchstens sechs Nachbarn.)


Zeige, dass du den gesamten großen Würfel infizieren kannst, beginnend mit nur n² kranken Einheitswürfeln.

Spoiler

Wie wir am Beispiel des Quadrates gezeigt haben, reicht ein Diagonale das gesamte Quadradt zu befüllen.
Nun brauchen wir aber 3 Nachbarn.
Wir beginnen also mit einer Diagonale auf der untersten Ebene.
Die Felder der beiden Nebendiaglonalen haben nun schon mal zwei Nachbarn,
also plazieren genau wir darüber auf Ebene 2 wiederum infizierte Zellen
Damit infizieren sich die Nebendiagonalen auf Ebene 1.
Auf Ebene 3 plazieren wir nun ebenfalls Infizierte auf den äußeren Nebendiagonalen.
Damit infizieren wird die darunterliegenden der Ebene 2 und in weiterer Folge der Ebene 1.
Haben wir die lezten beiden Ecken auf Ebene n Infiziert haben wir n^2 Infektionen "verteilt".
Bei jeder Infektion werden die direkt darunterliegenden Zellen mit infiziert.

Am Beispiel von n=5 haben wir dann von oben betrachet folgendes Muster,
wobei die Zahl die Ebene der Plazierung angibt:
54321
43212
32123
21234
12345

Da nun Ebene 1 voll ist, füllt sich auch die Ebene 2.
Ist diese vollständig infiziert, dann Ebene 3
...
Sh.t, Ebene 5 funktioniert so nicht.
Wär ja zu schön, wenns so einfach wäre.

[kad]

… und falls ein Kind eine ungerade Anzahl Sugus hat, bekommt es ein zusätzliches geschenkt

Das ist nett, aber wohl wenig hilfreich.

Spoiler

Ok, fangen an.
Wir haben n Kinder.
Kn+1 rechts von Kn

Was passiert mit den a Sugus von Kind 1?
Runde 0: K1:a
Runde 1: K1:a/2, K2:a/2
Runde 2: K1:a/4, K2:2a/4, K3: a/4

Ok, Binomialkoeffizienten (links wird der rechte wert dazugezählt)
Damit halbieren sich die Anteile je Runde zu 1/2^n, die Gesamtzahl der Anteile verdoppeln sich hingegen zu 2^n.
Problem ist nur, dass diese Gesamtzahl nicht durch beleibige Zahlen teilbar ist.

Hier die zyklische Varienate (links wird der rechte wert dazugezählt) am Beispiel von drei Kindern
100 (1a)
110 (2a/2)
121 (4a/4)
233 (8a/8)
556 (16a/16)
11,10,11 (32a/32)
22,21,21 (64a/64)
43,43,42 (128a/128)

Also egal, wie viele Runden ich da mach, die Sugus von A verteilen sich im Allgemeinen nie gleichmäßig auf alle Kinder.


tbc.

Aber vielleicht hab ich ja die Aufgabe nicht richtig verstanden.
Einzige Bedingung ist doch, dass am Anfang die Anzahl der Sugus je Kind gerade ist.
Da damit aber auch die Summe aller Sugus gerade ist, können schon mal beispielsweise drei Kinder am Ende nicht gleich viele haben.

weil ich das in der ursprünglichen Fragestellung nicht hatte: folgendes gehört wirklich zur Aufgabe

und falls ein Kind eine ungerade Anzahl Sugus hat, bekommt es ein zusätzliches geschenkt

Nach jeder Runde haben also alle Kinder eine gerade Anzahl Sugus.

ah, das war kein Scherz.

Spoiler

ok, nächster Versuch.
Offensichtlich werden hier fortlaufend Mittelwerte gebildet.
K1'=(K1+Kn)/2
K2'=(K2+K1)/2
..
Kn'=(Kn+Kn-1)/2

K1''=(K1+Kn)/2+(Kn+Kn-1)/2=(K1+2Kn+Kn-1)/4
und so fort.

Dass diese Mittelwert gegen den Wert (K1+..Kn)/n konvergieren,
wenn Unteilbarkeit keine Rolle spielt (also Sugo statt Sugu) ist ziemlich klar.

Dass bei Unteilbarkeit die Summe bzw. Aufteilung am Ende n*2x (2x,2x,2x...) sein muss ist klar.
Wie groß die Endsumme bzw. die Anteile sein werden, ist aber gar nicht so offensichtlich
und ist mitnichten immer die nächst größer Zahl mit dieser Eigenschaft, wie unten am Beispiel von
10 (18 statt 12)
oder 22 (30 statt 24)
zu sehen ist.

Einige Beispiele mit 3 Kindern.
2,0,0
1,1,0->2,2,0
2,2,1->2,2,2 (6)

4,0,0
2,2,0
2,2,1->2,2,2 (6)

6,0,0
3,3,0->4,4,0
2,4,2
2,3,3->2,4,4
3,3,4->4,4,4 (12)

8,0,0
4,4,0
2,4,2
2,3,3->2,4,4
3,3,4->4,4,4 (12)

10,0,0
5,5,0 ->6,6,0
3,6,3->4,6,4
4,5,5->4,6,6
5,5,6->6,6,6 (18)

12,0,0
6,6,0
3,6,3->4,6,4
4,5,5->4,6,6
5,5,6->6,6,6 (18)

8,2,2
5,5,2 ->6,6,2
4,6,4
4,5,5->4,6,6
5,5,6->6,6,6 (18)

14,0,0
7,7,0 ->8,8,0
4,8,4
4,6,6
5,5,6->6,6,6 (18)

16,0,0
8,8,0
4,8,4
4,6,6
5,5,6->6,6,6 (18)

18,0,0
9,9,0->10,10,0
5,10,5->6,10,6
6,8,8
7,7,8->8,8,8 (24)

20,0,0
10,10,0
5,10,5->6,10,6
6,8,8
7,7,8->8,8,8 (24)

22,0,0
11,11,0->12,12,0
6,12,6
6,9,9->6,10,10
8,8,10
9,8,9->10,8,10
10,9,9->10,10,10 (30)

20,2,0
10,11,1->10,12,2
6,11,7->6,12,8
7,9,7->8,10,8
8,9,9->8,10,10
9,9,10->10,10,10 (30)

Lustiges Spiel mit einigen unerwarteten Kuriositäten

tbc.

Eine mögliche Lösung, die ich im Internet gefunden habe:

Spoiler

Wir bezeichnen mit 2mi die Anzahl Bonbons, die das Kind mit den wenigsten Bonbons vor dem i-ten Schritt hat und analog dazu 2Mi die Anzahl Bonbons, die das Kind mit den, meisten Bonbons vor dem i-ten Schritt hat. Offensichtlich gilt 2mi ≤ 2Mi für jedes i ∈ N. Falls irgendwann Gleichheit gilt, haben alle Kinder gleich viele Bonbons und wir sind fertig.

Lemma: Es gilt 2mi+1 ≥ 2mi und 2Mi+1 ≤ 2Mi.

Beweis: Im i-ten Schritt erhält jedes Kind mindestens mi und höchstens Mi Bonbons von seinem linken Nachbar und behält selbst mindestens mi und höchstens Mi Bonbons. Das allfällige Zusatzbonbon ändert dabei fürs Maximum nichts, weil 2Mi gerade ist.

Wegen Mi≥ mi für jedes i ∈ N und unserem Lemma müssen die beiden Folgen ab irgendeinem Zeitpunkt einen konstanten Wert annehmen. Seien M und m diese Werte. Falls M = m gilt, sind wir fertig. Sei nun M > m. In jedem Schritt betrachten wir die Anzahl trauriger Kinder, die genau 2m Bonbons besitzen. Den Rest nennen wir glücklich. Da nach Annahme nicht alle Kinder traurig sind, gibt es ein trauriges Kind, dessen linker Nachbar mehr als 2m Bonbons besitzt. Dieses Kind ist nach dem nächsten Zug sicher glücklich, da es selbst m Bonbons behält und von seinem Nachbarn mehr als m Bonbons bekommt. Zudem kann ein glückliches Kind niemals traurig werden, weil es selbst mehr als m Bonbons behält und von seinem linken Nachbarn mindestens m Bonbons erhält. Somit verringert sich die Anzahl trauriger Kinder um mindestens eins. Das bedeutet aber, dass irgendwann alle Kinder glücklich sind und die minimale Anzahl Bonbons pro Kind grösser geworden ist. Dies ist ein Widerspruch zu m konstant! Also muss M = m gelten.

[kad]

Finde alle 3-stelligen Zahlen m, welche durch 11 teilbar sind mit der Eigenschaft, dass m/11 gleich der Summe der Quadrate der Ziffern von m ist.

[giffi marauder]

Finde alle 3-stelligen Zahlen m, welche durch 11 teilbar sind mit der Eigenschaft, dass m/11 gleich der Summe der Quadrate der Ziffern von m ist.

Die zwei Zahlen finden ist ja jetzt nicht das Problem.
Ich grüble noch nach an Anleitung sich die Suche sparen zu können.

Spoiler

Sei die 2stellige gesuchte Zahl = xy bzw. x*10+y
das 11-fache davon ist dann abc = 100x+10(x+y)+y
Da abc dreistellig ist, gilt 10<=xy<=90

Da x+y auch >= 10 sein kann führen wir einen überlauf h (0 oder 1) ein
damit ist
a=x+h
b=x+y-10h
c=y
Weiters ist gefordert, das die Summe der Quadrate von a,b,c =xy sind
-> (x+h)^2+(x+y-10h)^2+y^2=10x+y

Fall 1
h=0
x^2+x^2+2xy+y^2+y^2=10x+y
2x^2+2xy+2y^2=10x+y
Also kommen für y nur gerade Zahlen in Frage.
2x^2+2xy+2y^2-10x-y=0
0: 2x^2-10x=0 -> x^2-5x=0 -> x(x-5)=0 -> x=0 oder x=5 -> 50
2: 2x^2+4x+8-10x-2=0->2x^2-6x+6=0->x^2-3x+3=0 -> keine reelle Lösung
4: 2x^2+8x+32-10x-4=0 -> 2x^2-2x+28=0 -> x^2-x+14=0 -> keine reelle Lösung
6: 2x^2+12x+72-10x-6=0 x^2+x+64=0 -> keine reelle Lösung
8: -> keine reelle Lösung

h=1 (x+y>10)
-> (x+1)^2+(x+y-10)^2+y^2-10x-y=0
-> 2x^2+2xy-28x-21y+y^2+101=0


tbc.

[kad]

Finde alle 3-stelligen Zahlen m, welche durch 11 teilbar sind mit der Eigenschaft, dass m/11 gleich der Summe der Quadrate der Ziffern von m ist.

Die zwei Zahlen finden ist ja jetzt nicht das Problem.
Ich grüble noch nach an Anleitung sich die Suche sparen zu können.

Ja, so eine Anleitung gibt es. Und sogar die gute alte 11er Probe findet als Teilschritt Verwendung.

[kad]

Finde alle 3-stelligen Zahlen m, welche durch 11 teilbar sind mit der Eigenschaft, dass m/11 gleich der Summe der Quadrate der Ziffern von m ist.

Die zwei Zahlen finden ist ja jetzt nicht das Problem.
Ich grüble noch nach an Anleitung sich die Suche sparen zu können.

Ja, so eine Anleitung gibt es. Und sogar die gute alte 11er Probe findet als Teilschritt Verwendung.

Eine Lösung

Spoiler

Sei N = 100a + 10b+c mit Ziffern a, b und c. Es gilt 100a + 10b + c = 11m und m=a^2+b^2+c^2. Also 100a+10b+c = 11a^2 +11b^2 +11c^2. Wenn eine Zahl durch 11 teilbar ist, dann ist die Summe der Ziffern an den ungeraden Stellen weniger der Summe der Ziffern an den geraden Stellen durch 11 teilbar (Elferprobe). Somit entweder (1) b = a + c oder (2) b = a + c - 11.
Mit dieser Fallunterscheidung rechnet man weiter und erhält bei (1) den Wert 550 und bei (2) den Wert 803.

[kad]

Fünf Schüler, A, B, C, D, E, nahmen an einem Wettbewerb teil. Eine Vorhersage war, dass die Teilnehmer in der Reihenfolge ABCDE ins Ziel kommen würden. Diese Vorhersage war sehr schlecht. Tatsächlich erreichte keiner der Teilnehmer die vorhergesagte Position, und keine zwei Teilnehmer, von denen vorhergesagt wurde, dass sie nacheinander ins Ziel kommen, taten dies tatsächlich. Eine zweite Vorhersage besagte, dass die Teilnehmer in der Reihenfolge DAECB ins Ziel kommen würden. Diese Vorhersage war besser. Genau zwei der Teilnehmer erreichten die vorhergesagten Plätze, und zwei disjunkte Schülerpaare, von denen vorhergesagt wurde, dass sie nacheinander ins Ziel kommen, taten dies tatsächlich. Bestimme die Reihenfolge, in der die Teilnehmer ins Ziel kamen.