Rechenaufgaben

[giffi marauder]

10 Seiten Notizen mit gefühlt 20 Variablen, hunderten Formeln und zig Weg-Zeit-Diagrammen schmeiss ich dann mal weg.

Immerhin hast du die Lösung!
In einem anderen Thread führe ich unendliche Listen mit Filmtiteln, Hausarbeiten, Verwendungszwecke von Bollerwagen, Raumschiffen, Dreicksverhältnissen

und habe den Zusammenhang noch nicht gefunden….

Der Zusammenhang ist:

Spoiler

Vatertag

[kad]

Einhundert Punkte liegen auf einem Kreis. Ruth und Paul verbinden abwechselnd Punktepaare durch eine Linie, bis jeder Punkt mindestens eine Verbindung hat. Der Letzte, der spielt, gewinnt; welcher Spieler hat eine Gewinnstrategie?

Spoiler

Ich gehe davon aus, dass sich die Linien kreuzen dürfen.

Offensichtlich verliert dann, wer einen oder zwei Punkte ohne Verbindung übrig läßt,
da diese von anderen Spieler im nächsten Zug verbunden und das Spiel beendet werden kann.

Aus der Formulierung "jeder Punkt mindestens eine Verbindung", schließe ich,
dass die Punkte mehrfach verbunden werden können.
Gilt das auch für ein schon verbundens Paar oder müssen jeweils "neue" Paare oder gar mindestes ein "leerer" Punkt verbunden werden?

Ohne irgendwelche Einschränkungen, würden die Spieler somit ad infinitum immer wieder andere bereits verbundene Punkte verbinden.

Nehmen wir hingegen an, es muss mindestes ein unverbundener Punkt verwendet werden,
dann kann Spieler 2 das Geschehen kontrollieren.

Betrachten wir die Anzahl der restlichen unverbunden Punkte nach einem Zug aus Sicht dessen der gerade dran ist.
Rest nach dem Zug:
1: schlecht (der andere gewinnt)
2: schlecht (der andere gewinnt)
3: gut (der andere kann nur 1 oder 2 überlassen und verliert)
4: schlecht (der andere kann 3 überlassen und gewinnt)
5: schlecht (der andere kann 3 überlassen und gewinnt)
6: gut
7: schlecht
8: schlecht
...

Spieler 2 ist hierbei im Vorteil, weil er kontrollieren kann, dass seine Reste immer vielfache von 3 sind.
Spieler 1 hingegen muss mit anfangs gleich mal 2 Punkte verbinden und kann deshalb nicht auf 99 oder 96 reduzieren.

Spieler 1 verbindet 2 Punkte (-> 98)
Spieler 2 verbindet 2 Punkte (-> 96)
Spieler 1 verbindet 1 oder 2 neue Punkte (->95 oder 94)
Spieler 2 verbindet 2 oder 1 neue Punkte (->93)
Spieler 1 verbindet 1 oder 2 neue Punkte (->92 oder 91)
Spieler 2 verbindet 2 oder 1 neue Punkte (->90)
....
Spieler 2 verbindet 2 oder 1 neue Punkte (->3)
Spieler 1 verbindet 1 oder 2 neue Punkte (->1,2)
Spieler 2 verbindet 2 oder 1 neue Punkte (->0)

Sehr gut.
Eine ähnliche Überlegung

Spoiler

Wie du sagst, derjenige, welcher den 98. Punkt verbindet, verliert.
Es gibt (97 tief 2) Züge, die man machen kann, bevor der 98. Punkt verbunden werden muss.
(97 tief 2) ist eine gerade Zahl, also kann der 2. Spieler das Geschehen kontrollieren.

[kad]

Spoiler

10 Seiten Notizen mit gefühlt 20 Variablen, hunderten Formeln und zig Weg-Zeit-Diagrammen schmeiss ich dann mal weg.

Immerhin hast du die Lösung!
In einem anderen Thread führe ich unendliche Listen mit Filmtiteln, Hausarbeiten, Verwendungszwecke von Bollerwagen, Raumschiffen, Dreicksverhältnissen

und habe den Zusammenhang noch nicht gefunden….

Der Zusammenhang ist:

Spoiler

Vatertag

Spoiler

Danke. Hatte ich schon angeschaut. Beim galaktischen Expeditionskorps (Kommando Vatertag) sind nur kleine Raumschiffe mit dabei, kein „ ganz fetter Pott"

[kad]

Zwei Läufer starten gemeinsam auf einer Kreisbahn und laufen mit unterschiedlichen konstanten Geschwindigkeiten. Laufen sie in entgegengesetzte Richtungen, treffen sie sich nach einer Minute; laufen sie in die gleiche Richtung, treffen sie sich nach einer Stunde.

Wie ist das Verhältnis ihrer Geschwindigkeiten?

[giffi marauder]

Zwei Läufer starten gemeinsam auf einer Kreisbahn und laufen mit unterschiedlichen konstanten Geschwindigkeiten. Laufen sie in entgegengesetzte Richtungen, treffen sie sich nach einer Minute; laufen sie in die gleiche Richtung, treffen sie sich nach einer Stunde.

Wie ist das Verhältnis ihrer Geschwindigkeiten?

Spoiler

Ich mach mal eine Schätzung.
Wenn beide vom gleichen Punkt starten und Läufer1 mit v1 hinter Läufer 2 mit v2 (>v1) herläuft,
muss Läufer 2 in 60 Minuten einen Vorspung von genau einer Umrundung der Kreisbahn herauslaufen,
damit er Läufer 1 einholt.
Hat Läufer 1 in 60 Minuten die Kreisbahn n mal umrundet, dann Läufer 2 n+1 mal.
Da der in gleicher Zeit zurückgelegte Weg proportional zur jeweiligen Geschwindigkeit ist,
ist das Verhältnis der Geschwindigkeiten v2/v1= (n+1)/n

Nun wissen wir weiters, dass, wen die beiden auf einander zulaufen, sie sich nach 1 Minute Treffen.
Daraus folgt, dass beide dabei ca. die Hälfte der Kreisbahn umlaufen und somit in 60 Minuten ca. 30 Runden schaffen.
Einer ein bisschen weniger, einer ein bisschen mehr.
Das Verhältnis der Gewschwindigkeiten wäre damit ca. 30,5/29,5=1,03

Edit:
Der mathematischen Ansatz sieht so aus:
U= Umfang der Kreisbahn
Da sich beide bei Gegenläufigkeit nach 1 Minute treffen, ist die Summe der Geschwindigkeiten v1+v2=1U/1min (1)
(Läufer 1 läuft einen Teil des Umfanges, Läufer 2 den anderen, zusammen laufen sie genau 1U)

Bei Nach- bzw. Vorläufigkeit ist die Differenzgeschwindigkeit v2-v1=1U/60min (2)
(Läufer 2 liegt beim Start nicht nur gleichauf, sondern gleichzeitig eine Runde "hinter" Läufer 1 und diese eine Runde muss er in 60 Minuten aufholen).

Addiert man diese beiden Gleichungen, erhält man:
v2=30,5U/60min
Setzt man dies in (1) ein, folgt
v1=(60U-30,5U)/60 min= 29,5U/60min
->
Das Verhältnis der Geschwindigkeiten ist damit nicht nur ca. sondern exakt 30,5/29,5=1,03

[kad]

Zwei Läufer starten gemeinsam auf einer Kreisbahn und laufen mit unterschiedlichen konstanten Geschwindigkeiten. Laufen sie in entgegengesetzte Richtungen, treffen sie sich nach einer Minute; laufen sie in die gleiche Richtung, treffen sie sich nach einer Stunde.

Wie ist das Verhältnis ihrer Geschwindigkeiten?

Spoiler

Ich mach mal eine Schätzung.
Wenn beide vom gleichen Punkt starten und Läufer1 mit v1 hinter Läufer 2 mit v2 (>v1) herläuft,
muss Läufer 2 in 60 Minuten einen Vorspung von genau einer Umrundung der Kreisbahn herauslaufen,
damit er Läufer 1 einholt.
Hat Läufer 1 in 60 Minuten die Kreisbahn n mal umrundet, dann Läufer 2 n+1 mal.
Da der in gleicher Zeit zurückgelegte Weg proportional zur jeweiligen Geschwindigkeit ist,
ist das Verhältnis der Geschwindigkeiten v2/v1= (n+1)/n

Nun wissen wir weiters, dass, wen die beiden auf einander zulaufen, sie sich nach 1 Minute Treffen.
Daraus folgt, dass beide dabei ca. die Hälfte der Kreisbahn umlaufen und somit in 60 Minuten ca. 30 Runden schaffen.
Einer ein bisschen weniger, einer ein bisschen mehr.
Das Verhältnis der Gewschwindigkeiten wäre damit ca. 30,5/29,5=1,03

Edit:
Der mathematischen Ansatz sieht so aus:
U= Umfang der Kreisbahn
Da sich beide bei Gegenläufigkeit nach 1 Minute treffen, ist die Summe der Geschwindigkeiten v1+v2=1U/1min (1)
(Läufer 1 läuft einen Teil des Umfanges, Läufer 2 den anderen, zusammen laufen sie genau 1U)

Bei Nach- bzw. Vorläufigkeit ist die Differenzgeschwindigkeit v2-v1=1U/60min (2)
(Läufer 2 liegt beim Start nicht nur gleichauf, sondern gleichzeitig eine Runde "hinter" Läufer 1 und diese eine Runde muss er in 60 Minuten aufholen).

Addiert man diese beiden Gleichungen, erhält man:
v2=30,5U/60min
Setzt man dies in (1) ein, folgt
v1=(60U-30,5U)/60 min= 29,5U/60min
->
Das Verhältnis der Geschwindigkeiten ist damit nicht nur ca. sondern exakt 30,5/29,5=1,03

Stimmt!
Ähnlich

Spoiler

(v1 + v2)U/(v1 − v2)U= 60 und somit v1/v2 = 61/59

[kad]

Beat besitzt nur 500 €, auf einem Bankkonto.
Er braucht unbedingt Bargeld.

Seine einzige Option ist ein kaputter Geldautomat, der nur Abhebungen von genau 300 € und Einzahlungen von genau 198 € erlaubt.

Wie viel Bargeld kann Beat maximal abheben?

[kad]

Zum Zeitpunkt t = 0 wird ein Roboter an einem unbekannten Gitterpunkt im dreidimensionalen Raum platziert. Jede Minute bewegt sich der Roboter eine feste, unbekannte Distanz in eine feste, unbekannte Richtung zu einem neuen Gitterpunkt. Jede Minute kann ein beliebiger einzelner Punkt im Raum untersucht werden. Entwickle einen Algorithmus, der den Roboter garantiert in endlicher Zeit findet

Lösung

Spoiler

Es gibt nur abzählbar viele ganzzahlige Vektoren (a, b, c, x, y, z), die jeweils eine Startposition (a, b, c) und eine Verschiebung (x, y, z) kodieren.
Liste sie als v1, v2, … usw und untersuche zum Zeitpunkt t den Punkt (a, b, c) + t(x, y, z), wo
(a, b, c, x, y, z) = vt ist.

[giffi marauder]

Zum Zeitpunkt t = 0 wird ein Roboter an einem unbekannten Gitterpunkt im dreidimensionalen Raum platziert. Jede Minute bewegt sich der Roboter eine feste, unbekannte Distanz in eine feste, unbekannte Richtung zu einem neuen Gitterpunkt. Jede Minute kann ein beliebiger einzelner Punkt im Raum untersucht werden. Entwickle einen Algorithmus, der den Roboter garantiert in endlicher Zeit findet

Lösung

Spoiler

Es gibt nur abzählbar viele ganzzahlige Vektoren (a, b, c, x, y, z), die jeweils eine Startposition (a, b, c) und eine Verschiebung (x, y, z) kodieren.
Liste sie als v1, v2, … usw und untersuche zum Zeitpunkt t den Punkt (a, b, c) + t(x, y, z), wo
(a, b, c, x, y, z) = vt ist.

Spoiler

Ja, die Idee hatte ich auch.
Am Beispiel einer Dimension (der Roboter bewegt sich auf er x-Achse vorwärts).
Wir haben hier ein Tuppel x (Startpunkt) und dx (den Bewegungsvektor).
Diese beiden können wir zweidimensional darstellen mit x=x und dx=y
Zu jedem Zeitpunkt (t) kann ich ein beliebiges x(t) Untersuchen und (wenn der Roboter da gerade nicht ist),
alle x,y Kombinationen ausscheiden, für die gilt x+ty=x(t), denn wären diese richtig, müsste der Roboter
ja nun da sein.
Das sind für jeden Test ziemlich viele.
Auf diese Art und Weise könnte ich nach und nach "alle" x,dx überprüfen.

Mein gedankliches Problem dabei ist allerdings,
dass sowohl der Startpunkt des Roboters als auch sein dx ziemlich groß sein könnten
und dieser damit schneller davonzieht als mein systematischer Algorithmus ihn jemals finden könnte.

Da abzählbar finde ich ihn also wohl "irgendwann", aber wieso in "endlicher" Zeit?

Kurioserweise könnte ich zu jedem Zeitpunkt auch immer x=0 überprüfen und auf diese
Weise ebenfalls unendlich viele Möglichkeiten (x=-t*dx) ausschließen.
t=0 -> x=0
t=1 -> x=-x (1/-1),(-1/1), (2/-2),(-2/2) ...
t=2 -> x=-2y (2/-1),(-2/1),(4/-2) ...
Dieser Algorithmus wir ihn aber wohl eher nicht finden.

[giffi marauder]

Beat besitzt nur 500 €, auf einem Bankkonto.
Er braucht unbedingt Bargeld.

Seine einzige Option ist ein kaputter Geldautomat, der nur Abhebungen von genau 300 € und Einzahlungen von genau 198 € erlaubt.

Wie viel Bargeld kann Beat maximal abheben?

Spoiler

498€ ist das Maximum

16 x (-300,+198,-300,+198,+198 = +6) = 16*6=96€
und dann noch (-300,+198,-300=402)
-> 402+96=498

Würde Beat noch einmal 198€ einzahlen wäre der Kontostand gleich hoch,
wie nach der ersten Behebung von 300€.

[kad]

Zum Zeitpunkt t = 0 wird ein Roboter an einem unbekannten Gitterpunkt im dreidimensionalen Raum platziert. Jede Minute bewegt sich der Roboter eine feste, unbekannte Distanz in eine feste, unbekannte Richtung zu einem neuen Gitterpunkt. Jede Minute kann ein beliebiger einzelner Punkt im Raum untersucht werden. Entwickle einen Algorithmus, der den Roboter garantiert in endlicher Zeit findet

Lösung

Spoiler

Es gibt nur abzählbar viele ganzzahlige Vektoren (a, b, c, x, y, z), die jeweils eine Startposition (a, b, c) und eine Verschiebung (x, y, z) kodieren.
Liste sie als v1, v2, … usw und untersuche zum Zeitpunkt t den Punkt (a, b, c) + t(x, y, z), wo
(a, b, c, x, y, z) = vt ist.

Spoiler

Ja, die Idee hatte ich auch.
Am Beispiel einer Dimension (der Roboter bewegt sich auf er x-Achse vorwärts).
Wir haben hier ein Tuppel x (Startpunkt) und dx (den Bewegungsvektor).
Diese beiden können wir zweidimensional darstellen mit x=x und dx=y
Zu jedem Zeitpunkt (t) kann ich ein beliebiges x(t) Untersuchen und (wenn der Roboter da gerade nicht ist),
alle x,y Kombinationen ausscheiden, für die gilt x+ty=x(t), denn wären diese richtig, müsste der Roboter
ja nun da sein.
Das sind für jeden Test ziemlich viele.
Auf diese Art und Weise könnte ich nach und nach "alle" x,dx überprüfen.

Mein gedankliches Problem dabei ist allerdings,
dass sowohl der Startpunkt des Roboters als auch sein dx ziemlich groß sein könnten
und dieser damit schneller davonzieht als mein systematischer Algorithmus ihn jemals finden könnte.

Da abzählbar finde ich ihn also wohl "irgendwann", aber wieso in "endlicher" Zeit?

Kurioserweise könnte ich zu jedem Zeitpunkt auch immer x=0 überprüfen und auf diese
Weise ebenfalls unendlich viele Möglichkeiten (x=-t*dx) ausschließen.
t=0 -> x=0
t=1 -> x=-x (1/-1),(-1/1), (2/-2),(-2/2) ...
t=2 -> x=-2y (2/-1),(-2/1),(4/-2) ...
Dieser Algorithmus wir ihn aber wohl eher nicht finden.

Spoiler

Ich übersetze meinen Algorithmus auf dein Beispiel x, dx.
Wie du betrachte ich die x, y Ebene. Es gibt abzählbar unendlich viele Gitterpunkte.

v1, v2, v3, v4, ….. sei eine Aufzählung (eine bijektive Abbildung von den natürlichen Zahlen N auf die Gitterpunkte in der x, y - Ebene, zb
v1 = (0,0)
v2 = (1,0)
v3 = (0,1)
v4 = (1,1)
v5 = (2,1)
.
.
.
v9987 = (56, 12)
.
.

Nehmen wir an, der Roboter startet auf x=56 mit dx=12

Nach t=9987 Minuten ist v9987 im Fokus und wir proben den Punkt 56 + 9987*12.
Und, welch Wunder - der Roboter befindet sich dort und wird gefunden, in endlicher Zeit.
Jedes x, dx gehört zu einem vt und somit wird der Roboter in endlicher Zeit (t Minuten) gefunden.

[kad]

Beat besitzt nur 500 €, auf einem Bankkonto.
Er braucht unbedingt Bargeld.

Seine einzige Option ist ein kaputter Geldautomat, der nur Abhebungen von genau 300 € und Einzahlungen von genau 198 € erlaubt.

Wie viel Bargeld kann Beat maximal abheben?

Spoiler

498€ ist das Maximum

16 x (-300,+198,-300,+198,+198 = +6) = 16*6=96€
und dann noch (-300,+198,-300=402)
-> 402+96=498

Würde Beat noch einmal 198€ einzahlen wäre der Kontostand gleich hoch,
wie nach der ersten Behebung von 300€.

Zu einfach für dich!

[kad]

Alison, Bonnie und Clyde kandidieren für das Amt des Klassensprechers und erzielen ein Dreier-Gleichstand. Um das zu brechen, bitten sie ihre Mitschüler um die Zweitwahl, aber wieder gibt es ein Dreier-Gleichstand. Das Wahlkomitee ist ratlos, bis Alison vortritt und darauf hinweist, dass sie aufgrund der ungeraden Anzahl der Wähler Zweierentscheidungen treffen können. Sie schlägt daher vor, dass die Schüler zwischen Bonnie und Clyde wählen und der Gewinner dann in einer Stichwahl gegen Alison antreten würde.

Bonnie beschwert sich, dass dies unfair sei, weil Alison dadurch eine bessere Gewinnchance habe als die beiden anderen Kandidaten. Hat Bonnie Recht?

[giffi marauder]

Alison, Bonnie und Clyde kandidieren für das Amt des Klassensprechers und erzielen ein Dreier-Gleichstand. Um das zu brechen, bitten sie ihre Mitschüler um die Zweitwahl, aber wieder gibt es ein Dreier-Gleichstand. Das Wahlkomitee ist ratlos, bis Alison vortritt und darauf hinweist, dass sie aufgrund der ungeraden Anzahl der Wähler Zweierentscheidungen treffen können. Sie schlägt daher vor, dass die Schüler zwischen Bonnie und Clyde wählen und der Gewinner dann in einer Stichwahl gegen Alison antreten würde.

Bonnie beschwert sich, dass dies unfair sei, weil Alison dadurch eine bessere Gewinnchance habe als die beiden anderen Kandidaten. Hat Bonnie Recht?

Spoiler

Nein, das Gegeteil ist der Fall.
Nehmen wir an, Bonnie gewinnt in der ersten Runde gegen Clyde.
Da dies nur mit mehr als der Häfte der Stimmen von A möglich ist,
sind die "Verlierer" daraufhin so sauer, dass sie in der 2. Runde jedenfalls nicht A sondern auch B wählen.

Sollte C in der ersten Runde gewinnen, gilt das ebenfalls für die Wähler von B.

[kad]

Alison, Bonnie und Clyde kandidieren für das Amt des Klassensprechers und erzielen ein Dreier-Gleichstand. Um das zu brechen, bitten sie ihre Mitschüler um die Zweitwahl, aber wieder gibt es ein Dreier-Gleichstand. Das Wahlkomitee ist ratlos, bis Alison vortritt und darauf hinweist, dass sie aufgrund der ungeraden Anzahl der Wähler Zweierentscheidungen treffen können. Sie schlägt daher vor, dass die Schüler zwischen Bonnie und Clyde wählen und der Gewinner dann in einer Stichwahl gegen Alison antreten würde.

Bonnie beschwert sich, dass dies unfair sei, weil Alison dadurch eine bessere Gewinnchance habe als die beiden anderen Kandidaten. Hat Bonnie Recht?

Spoiler

Nein, das Gegeteil ist der Fall.
Nehmen wir an, Bonnie gewinnt in der ersten Runde gegen Clyde.
Da dies nur mit mehr als der Häfte der Stimmen von A möglich ist,
sind die "Verlierer" daraufhin so sauer, dass sie in der 2. Runde jedenfalls nicht A sondern auch B wählen.

Sollte C in der ersten Runde gewinnen, gilt das ebenfalls für die Wähler von B.

Ok. Nehmen wir an, dass die Mitschüler ihre Meinungen nicht ändern.