Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Ganz Simples Rätsel
38 views
Skip to first unread message
Tom Bola
Feb 20, 2023, 5:57:48 PM2/20/23
to
Man hat zwei Eimer zu je 3 Litern und 5 Litern.
Man befülle den grossen Eimer mit 4 Litern.
Welche Lösungen sind bekannt?
Man befülle den grossen Eimer mit 4 Litern.
Welche Lösungen sind bekannt?
Fritz Feldhase
Feb 20, 2023, 6:40:40 PM2/20/23
to
Hicks.
Stephan Gerlach
Feb 20, 2023, 8:43:26 PM2/20/23
to
Fritz Feldhase schrieb:
>> Welche Lösungen sind bekannt?
>
> Ziemlich trivial. Fülle den 3 Liter Eimer vollständig mit Bier. (Er enthält dann also 3 Litern Bier.)
> Dann befülle den 5 Liter Eimer mit dem Inhalt des 3 Liter Eimers. (Im 5 Litern Eimer sind nun also 3 Liter Bier.)
> Nun befülle den 3 Liter Eimer wieder vollständig mit Bier.
> Gieße dann soviel aus dem 3 Liter Eimer in den 5 Liter Eimer, bis der voll ist.
> (Es werden also 2 Liter Bier umgegossen.) Danach befindet sich noch ein Liter Bier im 3 Liter Eimer.
> Nun trinke den 5 Liter Eimer vollständig aus, so dass dieser leer ist.
> Danach gieße den einen Liter Bier aus dem 3 Liter Eimer in den (nun leeren) 5 Liter Eimer.
> (In diesem befindet sich nun also ein Liter Bier.)
> Befülle nun den 3 Liter Eimer ein weiteres Mal vollständig mit Bier.
> Danach gieße den Inhalt des 3 Liter Eimers (also 3 Liter Bier) in den 5 Liter Eimer.
> Dieser enthält nun 4 Liter Bier.
>
> Hicks.
Das ist die Variante, mit dem 3-Liter-Eimer anzufangen.
Ich kürze die 2. Variante "mit dem 5-Liter-Eimer anfangen" etwas ab und
bezeichne die Füllstände nach dem nächsten Schritt jeweils mit E3 für
den 3-Liter-Eimer bzw. E5 für den 5-Liter-Eimer
Anfangszustand: E3=0, E5=0
5-Liter-Eimer füllen ==> E3=0, E5=5
5-Liter-Eimer in 3-Liter-Eimer umfüllen ==> E3=3, E5=2
3-Liter-Eimer leeren ==> E3=0, E5=2
5-Liter-Eimer in 3-Liter-Eimer umfüllen ==> E3=2, E5=0
5-Liter-Eimer füllen ==> E3=2, E5=5
5-Liter-Eimer in 3-Liter-Eimer umfüllen ==> E3=3, E5=4.
Im Ergebnis enhält ebenfalls der 5-Liter-Eimer 4 Liter Bier.
Ich frage mich gerade, ob man derartige Aufgaben irgendwie "automatisch"
lösen kann, z.B. mit Hilfe eines geeigneten Diagramms.
Sowas hatte ich mal beim Wolf-Ziege-Grünkohl-Problem gesehen, wodurch
die Lösung sofort offensichtlich wurde.
Im Prinzip gibt es beim "Eimer-Problem" für den 3-Liter-Eimer nur die
"Zustände"
E3=0, E3=1, E3=2, E3=3
und für den 5-Liter-Eimer
E5=0, E5=1, E5=2, E5=3, E5=4, E5=5.
Außerdem gibt es die "Aktionen"
3-Liter-Eimer füllen
3-Liter-Eimer leeren
5-Liter-Eimer füllen
5-Liter-Eimer leeren
3-Liter-Eimer in 5-Liter-Eimer umfüllen
5-Liter-Eimer in 3-Liter-Eimer umfüllen.
--
> Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
> On Monday, February 20, 2023 at 11:57:48 PM UTC+1, Tom Bola wrote:
>
>> Man hat zwei Eimer zu je 3 Litern und 5 Litern.
>> Man befülle den grossen Eimer mit 4 Litern.
Das ist eine bekannte "Uralt-Aufgabe".
>
>> Man hat zwei Eimer zu je 3 Litern und 5 Litern.
>> Man befülle den grossen Eimer mit 4 Litern.
>> Welche Lösungen sind bekannt?
>
> Ziemlich trivial. Fülle den 3 Liter Eimer vollständig mit Bier. (Er enthält dann also 3 Litern Bier.)
> Dann befülle den 5 Liter Eimer mit dem Inhalt des 3 Liter Eimers. (Im 5 Litern Eimer sind nun also 3 Liter Bier.)
> Nun befülle den 3 Liter Eimer wieder vollständig mit Bier.
> Gieße dann soviel aus dem 3 Liter Eimer in den 5 Liter Eimer, bis der voll ist.
> (Es werden also 2 Liter Bier umgegossen.) Danach befindet sich noch ein Liter Bier im 3 Liter Eimer.
> Nun trinke den 5 Liter Eimer vollständig aus, so dass dieser leer ist.
> Danach gieße den einen Liter Bier aus dem 3 Liter Eimer in den (nun leeren) 5 Liter Eimer.
> (In diesem befindet sich nun also ein Liter Bier.)
> Befülle nun den 3 Liter Eimer ein weiteres Mal vollständig mit Bier.
> Danach gieße den Inhalt des 3 Liter Eimers (also 3 Liter Bier) in den 5 Liter Eimer.
> Dieser enthält nun 4 Liter Bier.
>
> Hicks.
Ich kürze die 2. Variante "mit dem 5-Liter-Eimer anfangen" etwas ab und
bezeichne die Füllstände nach dem nächsten Schritt jeweils mit E3 für
den 3-Liter-Eimer bzw. E5 für den 5-Liter-Eimer
Anfangszustand: E3=0, E5=0
5-Liter-Eimer füllen ==> E3=0, E5=5
5-Liter-Eimer in 3-Liter-Eimer umfüllen ==> E3=3, E5=2
3-Liter-Eimer leeren ==> E3=0, E5=2
5-Liter-Eimer in 3-Liter-Eimer umfüllen ==> E3=2, E5=0
5-Liter-Eimer füllen ==> E3=2, E5=5
5-Liter-Eimer in 3-Liter-Eimer umfüllen ==> E3=3, E5=4.
Im Ergebnis enhält ebenfalls der 5-Liter-Eimer 4 Liter Bier.
Ich frage mich gerade, ob man derartige Aufgaben irgendwie "automatisch"
lösen kann, z.B. mit Hilfe eines geeigneten Diagramms.
Sowas hatte ich mal beim Wolf-Ziege-Grünkohl-Problem gesehen, wodurch
die Lösung sofort offensichtlich wurde.
Im Prinzip gibt es beim "Eimer-Problem" für den 3-Liter-Eimer nur die
"Zustände"
E3=0, E3=1, E3=2, E3=3
und für den 5-Liter-Eimer
E5=0, E5=1, E5=2, E5=3, E5=4, E5=5.
Außerdem gibt es die "Aktionen"
3-Liter-Eimer füllen
3-Liter-Eimer leeren
5-Liter-Eimer füllen
5-Liter-Eimer leeren
3-Liter-Eimer in 5-Liter-Eimer umfüllen
5-Liter-Eimer in 3-Liter-Eimer umfüllen.
--
> Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Ralf Goertz
Feb 21, 2023, 3:03:13 AM2/21/23
to
Am Tue, 21 Feb 2023 03:04:09 +0100
schrieb Stephan Gerlach <mam9...@t-online.de>:
> Fritz Feldhase schrieb:
> > On Monday, February 20, 2023 at 11:57:48 PM UTC+1, Tom Bola wrote:
> >
> >> Man hat zwei Eimer zu je 3 Litern und 5 Litern.
> >> Man befülle den grossen Eimer mit 4 Litern.
>
> Das ist eine bekannte "Uralt-Aufgabe".
… die schon Bruce Willis und Samuel L. Jackson im dritten Teil der „Die
Hard“ Reihe gelöst haben.
schrieb Stephan Gerlach <mam9...@t-online.de>:
> Fritz Feldhase schrieb:
> > On Monday, February 20, 2023 at 11:57:48 PM UTC+1, Tom Bola wrote:
> >
> >> Man hat zwei Eimer zu je 3 Litern und 5 Litern.
> >> Man befülle den grossen Eimer mit 4 Litern.
>
> Das ist eine bekannte "Uralt-Aufgabe".
Hard“ Reihe gelöst haben.
Martin Vaeth
Feb 21, 2023, 11:32:39 AM2/21/23
to
Stephan Gerlach <mam9...@t-online.de> schrieb:
Die Füllstände (im 1. Problem) sind die Knoten, und wenn es
zwischen zwei Knoten einen Übergang durch
Umschütten/Befüllen/Leeren gibt, machst Du einen Pfeil
zwischen den Knoten.
Jetzt musst Du nur noch einen (kürzesten) Weg vom
gewünschten Start- zum Zielknoten suchen, am besten mit
https://de.wikipedia.org/wiki/Breitensuche
(was im Prinzip
https://de.wikipedia.org/wiki/Dijkstra-Algorithmus
mit Gewichtsfunktion 1 ist, aber leichter zu
implementieren).
Natürlich wirst Du i.a. nicht den gesamten Graph
abspeichern, sondern ihn während der Wegsuche
berechnen.
>
> Ich frage mich gerade, ob man derartige Aufgaben irgendwie "automatisch"
> lösen kann, z.B. mit Hilfe eines geeigneten Diagramms.
>
> Sowas hatte ich mal beim Wolf-Ziege-Grünkohl-Problem gesehen
Ja. Das sind Standard-Probleme der Graphentheorie:
> Ich frage mich gerade, ob man derartige Aufgaben irgendwie "automatisch"
> lösen kann, z.B. mit Hilfe eines geeigneten Diagramms.
>
> Sowas hatte ich mal beim Wolf-Ziege-Grünkohl-Problem gesehen
Die Füllstände (im 1. Problem) sind die Knoten, und wenn es
zwischen zwei Knoten einen Übergang durch
Umschütten/Befüllen/Leeren gibt, machst Du einen Pfeil
zwischen den Knoten.
Jetzt musst Du nur noch einen (kürzesten) Weg vom
gewünschten Start- zum Zielknoten suchen, am besten mit
https://de.wikipedia.org/wiki/Breitensuche
(was im Prinzip
https://de.wikipedia.org/wiki/Dijkstra-Algorithmus
mit Gewichtsfunktion 1 ist, aber leichter zu
implementieren).
Natürlich wirst Du i.a. nicht den gesamten Graph
abspeichern, sondern ihn während der Wegsuche
berechnen.
Marc Olschok
Feb 21, 2023, 12:05:59 PM2/21/23
to
schon im Buch von König zur Graphentheorie von 1935 in VIII.3 (mit
entsprechendem Digraphen auf Seite 110).
v.G.
--
M.O.
Stephan Gerlach
Feb 22, 2023, 4:46:22 PM2/22/23
to
Ralf Goertz schrieb:
Das ist mir neu.
Gibt es weitere bekannte Mathematik-Rätsel o.ä. in (bekannten)
Filmen/Serien?
Gibt es weitere bekannte Mathematik-Rätsel o.ä. in (bekannten)
Filmen/Serien?
Stephan Gerlach
Feb 24, 2023, 8:54:09 PM2/24/23
to
Martin Vaeth schrieb:
graphentheoretischen ist, sieht im übrigen wie folgt aus:
Jedes der 3 Objekte Grünkohl, Ziege, Wolf kann einen der 2 Zustände 0
(auf "dieser" Seite des Flusses) oder 1 (auf der anderen Seite des
Flusses) annehmen.
Man einen beliebigen "Gesamt-Zustand" durch einen Punkt im R^3
beschreiben, wobei o.B.d.A
w = Wolf
k = Grünkohl
z = Ziege
gesetzt werden kann.
Dann bedeutet z.B. (w;k;z) = (0;1;0), daß sich Wolf w und Ziege z auf
dieser Seite des Flusses befinden, während der Grünkohl k auf der
anderen Seite ist.
Die Menge aller möglichen Zustände wird nun durch die Eckpunkte eines
Würfels im R^3 beschrieben:
(0;0;0), (0;0;1), (0;1;0), (0;1;1),
(1;0;0), (1;0;1), (1;1;0), (1;1;1).
Das Ziel ist es nun einfach, entlang der Kanten des Würfels einen Weg
von (0;0;0) (alle 3 Objekte auf dieser Seite des Flusses) zu (1;1;1)
(alle 3 Objekte auf der anderen Seite des Flusses) zu finden.
Dabei dürfen genau 4 Kanten *nicht* benutzt werden, weil ansonsten
[Ziege und Grünkohl] oder [Wolf und Ziege] auf einer Seite des Flusses
allein zurückgelassen werden (Skizze zeichnen, dann sieht man das).
Z.B. die Kante (0;0;0)-->(1;0;0) ist unerwünscht, da sonst Ziege und
Grünkohl allein auf dieser Seite des Flusses zurückgelassen werden.
Aus der Skizze (des Würfels) "sieht" man dann sehr schnell die möglichen
beiden Wege.
> Ja. Das sind Standard-Probleme der Graphentheorie:
> Die Füllstände (im 1. Problem) sind die Knoten, und wenn es
> zwischen zwei Knoten einen Übergang durch
> Umschütten/Befüllen/Leeren gibt, machst Du einen Pfeil
> zwischen den Knoten.
Nur um sicher zu gehen: Welche Füllstände genau sind die Knoten?
Die Füllstände des 5-Liter-Eimers (in dem ja letztenendes die 4 Liter
Wasser sein müssen), oder die Füllstands-Kombinationen des 3-Liter- und
5-Liter-Eimers?
In der 1. Variante gäbe es nur die Knoten 0, 1, 2, 3, 4, 5.
In der 2. Variante gäbe es die Knoten
(0;0), (0;1), (0;2), (0;3),
(1;0), (1;1), (1;2), (1;3),
(2;0), (2;1), (2;2), (2;3),
(3;0), (3;1), (3;2), (3;3),
(4;0), (4;1), (4;2), (4;3),
(5;0), (5;1), (5;2), (5;3)
Mehr Sinn ergibt für mich die 2. Variante.
Das Ganze kann (glaube ich) ähnlich gelöst werden wie das
Wolf-Ziege-Grünkohl-Problem.
Jede Füllstands-Kombination entspricht einem Punkt in einem
2-dimensionalen Koordinatensystem mit
x = Füllstand des 5-Liter-Eimers
y = Füllstand des 3-Liter-Eimers.
_ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
Nun besteht das Problem "nur" darin, einen geeigneten Weg (Polygonzug)
innerhalb des "Rechtecks" mit den Eckpunkten (0;0), (5;0), (0;3), (5;3)
vom Punkt (0;0) zu einem der Punkte (4;0) oder (4;3) zu finden, unter
bestimmten Nebenbedingungen für die möglichen Wege dorthin. "Erlaubt"
sind folgende Wege:
- horizontale Strecken bis ganz nach rechts an den Rand (entspricht
5-Liter-Eimer auffüllen)
- horizontale Strecken bis ganz nach links an den Rand (entspricht
5-Liter-Eimer leeren)
- vertikale Strecken bis ganz nach oben an den Rand (entspricht
3-Liter-Eimer auffüllen)
- vertikale Strecken bis ganz nach unten an den Rand (entspricht
3-Liter-Eimer leeren)
- diagonale Strecken im im 45°-Winkel von links/oben nach rechts/unten
von "Rand bis Rand" (entspricht 3-Liter-Eimer in 5-Liter-Eimer umfüllen)
- diagonale Strecken im im 45°-Winkel von rechts/unten nach links/oben
von "Rand bis Rand" (entspricht 5-Liter-Eimer in 3-Liter-Eimer umfüllen).
Also kurz gesagt: "Erlaubt" sind vertikale, horizontale oder schräge
(45° von links/oben nach rechts/unten oder umgekehrt) Strecken von einem
Rand bis zu einem (anderen) Rand des Rechtecks.
Nach ein wenig Zeichnen "sieht" man auch hier schnell die beiden
möglichen Lösungen.
> Stephan Gerlach <mam9...@t-online.de> schrieb:
>> Ich frage mich gerade, ob man derartige Aufgaben irgendwie "automatisch"
>> lösen kann, z.B. mit Hilfe eines geeigneten Diagramms.
>>
>> Sowas hatte ich mal beim Wolf-Ziege-Grünkohl-Problem gesehen
Dessen (geometrische) Lösung, die wohl sehr ähnlich einer
>> Ich frage mich gerade, ob man derartige Aufgaben irgendwie "automatisch"
>> lösen kann, z.B. mit Hilfe eines geeigneten Diagramms.
>>
>> Sowas hatte ich mal beim Wolf-Ziege-Grünkohl-Problem gesehen
graphentheoretischen ist, sieht im übrigen wie folgt aus:
Jedes der 3 Objekte Grünkohl, Ziege, Wolf kann einen der 2 Zustände 0
(auf "dieser" Seite des Flusses) oder 1 (auf der anderen Seite des
Flusses) annehmen.
Man einen beliebigen "Gesamt-Zustand" durch einen Punkt im R^3
beschreiben, wobei o.B.d.A
w = Wolf
k = Grünkohl
z = Ziege
gesetzt werden kann.
Dann bedeutet z.B. (w;k;z) = (0;1;0), daß sich Wolf w und Ziege z auf
dieser Seite des Flusses befinden, während der Grünkohl k auf der
anderen Seite ist.
Die Menge aller möglichen Zustände wird nun durch die Eckpunkte eines
Würfels im R^3 beschrieben:
(0;0;0), (0;0;1), (0;1;0), (0;1;1),
(1;0;0), (1;0;1), (1;1;0), (1;1;1).
Das Ziel ist es nun einfach, entlang der Kanten des Würfels einen Weg
von (0;0;0) (alle 3 Objekte auf dieser Seite des Flusses) zu (1;1;1)
(alle 3 Objekte auf der anderen Seite des Flusses) zu finden.
Dabei dürfen genau 4 Kanten *nicht* benutzt werden, weil ansonsten
[Ziege und Grünkohl] oder [Wolf und Ziege] auf einer Seite des Flusses
allein zurückgelassen werden (Skizze zeichnen, dann sieht man das).
Z.B. die Kante (0;0;0)-->(1;0;0) ist unerwünscht, da sonst Ziege und
Grünkohl allein auf dieser Seite des Flusses zurückgelassen werden.
Aus der Skizze (des Würfels) "sieht" man dann sehr schnell die möglichen
beiden Wege.
> Ja. Das sind Standard-Probleme der Graphentheorie:
> Die Füllstände (im 1. Problem) sind die Knoten, und wenn es
> zwischen zwei Knoten einen Übergang durch
> Umschütten/Befüllen/Leeren gibt, machst Du einen Pfeil
> zwischen den Knoten.
Die Füllstände des 5-Liter-Eimers (in dem ja letztenendes die 4 Liter
Wasser sein müssen), oder die Füllstands-Kombinationen des 3-Liter- und
5-Liter-Eimers?
In der 1. Variante gäbe es nur die Knoten 0, 1, 2, 3, 4, 5.
In der 2. Variante gäbe es die Knoten
(0;0), (0;1), (0;2), (0;3),
(1;0), (1;1), (1;2), (1;3),
(2;0), (2;1), (2;2), (2;3),
(3;0), (3;1), (3;2), (3;3),
(4;0), (4;1), (4;2), (4;3),
(5;0), (5;1), (5;2), (5;3)
Mehr Sinn ergibt für mich die 2. Variante.
Das Ganze kann (glaube ich) ähnlich gelöst werden wie das
Wolf-Ziege-Grünkohl-Problem.
Jede Füllstands-Kombination entspricht einem Punkt in einem
2-dimensionalen Koordinatensystem mit
x = Füllstand des 5-Liter-Eimers
y = Füllstand des 3-Liter-Eimers.
_ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
Nun besteht das Problem "nur" darin, einen geeigneten Weg (Polygonzug)
innerhalb des "Rechtecks" mit den Eckpunkten (0;0), (5;0), (0;3), (5;3)
vom Punkt (0;0) zu einem der Punkte (4;0) oder (4;3) zu finden, unter
bestimmten Nebenbedingungen für die möglichen Wege dorthin. "Erlaubt"
sind folgende Wege:
- horizontale Strecken bis ganz nach rechts an den Rand (entspricht
5-Liter-Eimer auffüllen)
- horizontale Strecken bis ganz nach links an den Rand (entspricht
5-Liter-Eimer leeren)
- vertikale Strecken bis ganz nach oben an den Rand (entspricht
3-Liter-Eimer auffüllen)
- vertikale Strecken bis ganz nach unten an den Rand (entspricht
3-Liter-Eimer leeren)
- diagonale Strecken im im 45°-Winkel von links/oben nach rechts/unten
von "Rand bis Rand" (entspricht 3-Liter-Eimer in 5-Liter-Eimer umfüllen)
- diagonale Strecken im im 45°-Winkel von rechts/unten nach links/oben
von "Rand bis Rand" (entspricht 5-Liter-Eimer in 3-Liter-Eimer umfüllen).
Also kurz gesagt: "Erlaubt" sind vertikale, horizontale oder schräge
(45° von links/oben nach rechts/unten oder umgekehrt) Strecken von einem
Rand bis zu einem (anderen) Rand des Rechtecks.
Nach ein wenig Zeichnen "sieht" man auch hier schnell die beiden
möglichen Lösungen.
Martin Vaeth
Feb 25, 2023, 12:59:28 AM2/25/23
to
Stephan Gerlach <mam9...@t-online.de> schrieb:
nicht in dem Graphen der zulässigen Zustände.
>> Die Füllstände (im 1. Problem) sind die Knoten, und wenn es
>> zwischen zwei Knoten einen Übergang durch
>> Umschütten/Befüllen/Leeren gibt, machst Du einen Pfeil
>> zwischen den Knoten.
>
> Nur um sicher zu gehen: Welche Füllstände genau sind die Knoten?
> Die Füllstände des 5-Liter-Eimers (in dem ja letztenendes die 4 Liter
> Wasser sein müssen), oder die Füllstands-Kombinationen des 3-Liter- und
> 5-Liter-Eimer?
Letzteres: Es soll ja der gesamte Zustand durch einen Knoten
repräsentiert werden und nicht nur eine Teilinformation.
>
> Das Ziel ist es nun einfach, entlang der Kanten des Würfels einen Weg
> von (0;0;0) (alle 3 Objekte auf dieser Seite des Flusses) zu (1;1;1)
> (alle 3 Objekte auf der anderen Seite des Flusses) zu finden.
>
> Dabei dürfen genau 4 Kanten *nicht* benutzt werden, weil ansonsten
> [Ziege und Grünkohl] oder [Wolf und Ziege] auf einer Seite des Flusses
> allein zurückgelassen werden
Einfacher: Die entsprechenden Knoten (und natürlich Kanten) sind
> Das Ziel ist es nun einfach, entlang der Kanten des Würfels einen Weg
> von (0;0;0) (alle 3 Objekte auf dieser Seite des Flusses) zu (1;1;1)
> (alle 3 Objekte auf der anderen Seite des Flusses) zu finden.
>
> Dabei dürfen genau 4 Kanten *nicht* benutzt werden, weil ansonsten
> [Ziege und Grünkohl] oder [Wolf und Ziege] auf einer Seite des Flusses
> allein zurückgelassen werden
nicht in dem Graphen der zulässigen Zustände.
>> Die Füllstände (im 1. Problem) sind die Knoten, und wenn es
>> zwischen zwei Knoten einen Übergang durch
>> Umschütten/Befüllen/Leeren gibt, machst Du einen Pfeil
>> zwischen den Knoten.
>
> Nur um sicher zu gehen: Welche Füllstände genau sind die Knoten?
> Die Füllstände des 5-Liter-Eimers (in dem ja letztenendes die 4 Liter
> Wasser sein müssen), oder die Füllstands-Kombinationen des 3-Liter- und
Letzteres: Es soll ja der gesamte Zustand durch einen Knoten
repräsentiert werden und nicht nur eine Teilinformation.
0 new messages