StartseiteCipherbrain

Das Fischteich-Problem

Von / 12. November 2021 / 42 Kommentare
Mehr

Der britische Professor Colin Wright hat mir ein interessantes Rätsel zugeschickt. Kann ein Leser es lösen?

English version (translated with DeepL)

Am Sonntag gibt es wieder einen Online Vortrag bei ICCH. Cipherbrain-Leser Jerry McCarthy wird zum Thema “A Simulator for the Welchman-Turing and US Navy Bombes” referieren. Wer zuschauen will, kann mir gerne eine Mail schicken, dann leite ich den Einwahl-Link weiter. Die Teilnahme ist kostenlos.

Mein letzter Vortrag fand am 3. Oktober statt. Zusammen mit Elonka Dunin trug ich über das Lösen alter Verschlüsselungen mit modernen Methoden vor. Unter anderem ging es um Hill Climbing und Simulated Annealing. Veranstalter war das National Museum of Computing in Bletchley Park. Moderiert wurde die Veranstaltung vom oben erwähnten Jerry McCarthy.

 

Ballistisches Hill Climbing

Unter den Zuschauern bei meinem Vortrag war auch Colin Wright, ein Mathematik-Professor aus Liverpool. Colin hat eine Mathematik des Jonglierens entwickelt, die er in sehr unterhaltsamen Vorträgen vorstellt. Davon hatte ich schon gehört. Auch Kryptografie-Vorträge gehören zu seinem Repertoire. Wie ich inzwischen weiß, wohnt Colin nicht weit vom Otterspool Park entfernt, doch die Bedeutung des dortigen Schilds, über das ich kürzlich gebloggt habe, kennt auch er nicht.

Nach dem Vortrag kam ich mit Colin ins Gespräch. Er fragte mich, ob ich schon einmal von Ballistic Hill Climbing gehört hätte. Dies war nicht der Fall. Er erklärte mir, dass man beim Ballistic Hill Climbing annimmt, dass der Bergsteiger eine gewisse Trägheit hat. Wenn der Bergsteiger einen Gipfel erreicht hat, bleibt er dort nicht einfach stehen, sondern geht noch ein Stück in die entsprechende Richtung weiter, obwohl es wieder abwärts geht. Durch diese Trägheit erreicht man, dass der Bergsteiger auf einem lokalen Maximum (also bei einer Falschen Lösung) nicht notwendigerweise stehen bleibt, sondern die Chance hat, ein anderes Maximum zu erreichen.

Außerdem wies mich Colin darauf hin, dass man Hill Climbing auch umdrehen kann, indem man nicht nach einem Maximum (also einem Gipfel), sondern einem Minimum (also einer Talsohle) sucht. Diese Technik nennt man Valley Descending. Auch das war mir neu.

Sowohl das ballistische Hill Climbing als auch das Valley Descending lassen sich laut Colin für das Lösen von Verschlüsselungen nutzen. Hat ein Leser schon einmal Erfahrungen damit gemacht? Falls ja, würde sich Colin auf über einen Kommentar oder eine Kontaktaufnahme freuen. Vielleicht kommt ein Erfahrungsaustausch zu Stande.

 

Das Fischteich-Problem

Im Nachgang schickte mir Colin ein Rätsel zu:

Gegeben sei ein Fischteich. Dieser habe einen flachen Boden, vertikale Wände und sei mit Wasser gefüllt. Außerdem gebe es drei Würfel aus Beton, die alle gleich groß sind.

Stellt man den ersten Würfel in den Teich, dann steigt das Wasser um weniger als 12 Zentimeter. Beim zweiten Würfel steigt das Wasser um genau 12 Zentimeter. Beim dritten Würfel steigt das Wasser erneut um genau 12 Zentimeter. Die Würfel stehen nebeneinander im Wasser.

Frage: Wie tief unter der Wasserobefläche liegen nun die Oberseiten der Würfel?

Findet ein Leser die Lösung? Es gibt sicherlich verschiedene Methoden dafür. Laut Colin lässt sich eine Kombination aus ballistischem Hill Climbing und Valley Descending (quasi ballistisches Valley Descending) nutzen. Er hat mir dazu folgendes geschrieben:

We let the area of the pond, depth of water, size of cube, etc, all be variables, then starting with some values compute the amounts of water rise, and compare with the amounts stated. Then “jiggle” the variables, and perform valley-descending on the error. We can think of the “jiggle” J as a modification vector added to our state S, and if our error E(S+J) is less than E(J) then we set J’ = J+S and repeat.

But wait! If moving by J was good, why not try moving by kJ, for k some multiple. So we compute E(S+kJ), and we are moving in direction J with some “momentum”.

Then use a shotgun (start at 100 different places) and we find that there are a few local minima, but the solution drops out nicely.

Lässt sich diese Technik auch für das Lösen von Verschlüsselungen nutzen? Colin schreibt:

But there are problems if your K key is “jiggled” by swapping letters, because there’s no concept of “carrying on in the same direction”, so the “ballistic” aspect doesn’t work for that.

Anyway, I was wondering if (a) anyone had heard of this idea (which has even more modifications) and (b) it had some way of being used in the context of ciphers.

Ich würde mich über ein paar entsprechende Kommentare freuen.


Further reading: A DES challenge inspired by a conversation with Whitfield Diffie

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Stichworte: , ,
Mehr

Kommentare (42)

  1. #1 Richard SantaColoma
    https://proto57.wordpress.com/
    12. November 2021

    The first cube must have brought the water up to exactly the top of itself. We know this, because the next two cubes rose the water level an equal amount: 12 cm. Therefore the water must be exactly 24cm above all cubes.

  2. #2 Richard SantaColoma
    https://proto57.wordpress.com/
    12. November 2021

    To clarify why I think this, “The first cube must have brought the water up to exactly the top of itself. We know this, because the next two cubes rose the water level an equal amount: 12 cm.”

    Because since the first cube rose the water less than 12cm, but was the same size as the other two, it cannot have been fully submerged. But it also could not have had any part of it above the water line after sinking, because then the next cube would not raise the full 12cm, needing to continue to account for the amount the first cube was above the water line.

    The only situation left is that the first cube bring the water exactly to the top of itself.

  3. #3 TWO
    13. November 2021

    No blocks are under water

  4. #4 TWO
    13. November 2021

    @
    The Blocks are not equal size.

    Block 3 displaces the same amount of water as block 1 and 2

  5. #5 George Lasry
    13. November 2021

    The main idea is that when there are one or more cubes that are not fully under the water, adding a new cube would always result in a bigger height increase, than when adding a cube when all others are already under the water. The idea is that not only does the new cube add new volume, but some of or all the parts of prior cubes previously over the water also add some new volume.

    Let’s consider all volume of the parts of the cube volume over the water as a reservoir of ‘residual volume’.

    1) From the question, placing one cube will add less height (< 12cm) than placing the second one (12cm), it is clear that the first cube is not fully under the water, as at least some residual volume must have been utilized when adding the second one.

    2) Let's assume that placing the second cube already resulted in all cubes being under the water. This means that when placing the third one, there is no more 'residual volume' to gain from, so the height increase should be smaller than when placing the second one. But it is said that adding the second and the third results in the same height increase (12cm).
    Therefore, we know that after placing the second cube, there are still some parts over the water.

    3) The challenge states that after placing the third one, all cubes are under the water.

    I think this can be solved by setting some equations with relations between the heights at various states. It is useful to use some variable a = (S/H**2), H being the dimension of the cubes, and S being the surface of the container.

  6. #6 Klaus Schmeh
    13. November 2021

    >The Blocks are not equal size.
    I checked Colin’s mail. According to his description, the cubes are identical.

  7. #7 Gerhard F. Strasser
    Hamburg
    13. November 2021

    A rather interesting proposition … . The problem reminds me (and this may be far-fetched) of the famous/infamous “Röhren-Aufgaben” that students at technical Gymnasien were pained in the 1960s … . If you have a tub and feed more than 1 water outlet into this container but also drain the tub at intervals–when will it overflow … . We had to solve such problems without recourse to anything other than pure math, of course–it can be done but it wasn’t easy …

  8. #8 LittleThing
    13. November 2021

    @Richard

    You miss a little thing.

    Every time a cube is put in the basin, it displaces a volume of water (not necessarily the entire volume of the cube, but definitely not more). The water level rises by that volume divided by the area of the water basin as viewed from above.

    However, you have to subtract the area of cube face, again as seen from above, from the water basin’s area…

    And if the first or second cubes weren’t completely submerged when they were put in the water, putting the second or third cube in may still submerge them. When a cube is fully submerged, the rising water again spreads out over the cube’s area.

    It appears to me that this puzzle cannot be solved with linear equations alone.

  9. #9 Falk
    Flensburg
    13. November 2021

    Richard is absolutely right. It is Archimedes who we need here.
    All cubes are identical.
    The second and third displace the same amount of water. This means the situation for both of them is the same. This can only happen when both are fully submerged.
    The first one displaces less than the other two. This can only happen if he is not fully submerged.
    That means the first one will raise the water level exactly up to its height.

  10. #10 frank
    13. November 2021

    @Klaus Schmeh

    Dieses “ballistische Hillclimbing” scheint identisch oder doch sehr ähnlich zu dem bereits seit fast 30 Jahren bekannten heuristischen Optimierungsverfahren “Threshold Acceptance” zu sein.

    Der Algorithmus funktioniert wirklich sehr gut, ist schnell, ist sehr einfach zu programmieren, und liefert normalerweise ganz gute Resultate. Man würde ihn für gewöhnlich von mehreren unterschiedlichen Startzuständen aus laufen lassen und dann das beste Endergebnis wählen.

    Auch sehr interessant ist der sehr ähnliche “Sintflutalgorithmus”. Er unterscheidet sich vom “Treshold Acceptance” nur dadurch, dass sich im gesamten Gebirge ein “Wasserspiegel” befindet, den man nicht unterschreiten darf, wenn man z.B. von einem lokalen Gipfel wieder herunter klettert. Dieser Wasserspiegel steigt dabei aber kontinuierlich an.

    Mit letzterem hab ich aber noch nicht gearbeitet und schon gar nicht in der Kryptoanalyse.

    Eine allgemeinverständliche Darstellung dieser beiden Verfahren findet man hier:

    https://www.spektrum.de/magazin/toleranzschwelle-und-sintflut-neue-ideen-zur-optimierung/820713

    Dort habe auch ich zum ersten Mal von diesen Verfahren gehört.

  11. #11 Thomas
    13. November 2021

    A long shot:

    Two times the cube’s volume divided by the pond’s surface S minus the cube’s edge length E:

    2 × E**3/S – E

  12. #12 Thomas
    13. November 2021

    Edit: I forgot to add the initial depth D of the pond, so: + D

  13. #13 TWO
    13. November 2021

    @6

    Cube size is 6 cm

  14. #14 HFde
    13. November 2021

    My guess: 24cm.

  15. #15 hwied
    in seinem chlorfreien Lieblingssessel
    13. November 2021

    Wasser
    Wenn das Wasservolumen of the pond nur geringfügig kleiner ist als die 3 Betonquader, dann gibt es eine einfache mathematische Lösung.
    Dabei hat der duckpond die gleichen Abmessungen wie 3 Quader nebeneinander.
    Und als Betonquader sagen wir einfach Wasserquader.
    wenn wir also die Betonquader hinzufügen, dann steigt der Wasserspiegel um 12 cm.
    Warum ? Weil 12 ³ = 1728
    1728 mal 3 = 5184
    Das ist das Volumen der 3 Betonquader.

    Als Wassermenge nehmen wir nur 5181 , warum ? Weil das Wasser kälter ist.
    Die dividiert durch 3 = 1727
    Daraus die 3. Wurzel = 11,99

    Am Anfang hat der Teich ein Volumen von 5181. Warum ? Weil das Wasser kälter ist als der Beton.
    Dazu kommt ein Betonquader mit 1728
    5181 + 1728 = 6909
    6909 / 4 = 1727,5
    3 Wurzel = 11,99 cm

    Das Wasser ist also nur um 11,99 gestiegen, weil das Gesamtvolumen nicht 6912 ist , sondern nur 6909.
    Wenn sich das Wasser erwärmt hat, dann beträgt das Volumen 6912 und die Steigerung beträgt dann wieder genau 12 cm.

  16. #16 Richard SantaColoma
    https://proto57.wordpress.com/
    13. November 2021

    George wrote, “The main idea is that when there are one or more cubes that are not fully under the water, adding a new cube would always result in a bigger height increase, than when adding a cube when all others are already under the water.”

    This may be so, but then the fact that the 2nd and 3rd cube raise the water an equal amount tell us that the first cube is either 1) exactly at the level of the water, or 2) completely submerged.

    These are the only two situations in which #2 and #3 could be equal, because of what you say. Otherwise #2 would raise the water higher than #3, but it does not.

    But we also know that cube #1 cannot be completely under the water after it was put in the container. If it were, it would have raised the water 12cm as #2 and #3 did. But we are told it raised it less than 12cm. This is because it must have needed to displace enough water to raise the water level to its top only, something #2 and #3 did not have to do.

  17. #17 hwied
    in seinem chlorfreien Lieblingssessel
    13. November 2021

    Correction,
    The Quader is colder then the duckpond.
    Therefore we have only 11,99 cm.
    When the temperature is the same as the water the increase is exactly 12 cm.

  18. #18 George Lasry
    14. November 2021

    Well, I used Wolfram Alpha to solve a set of equations and inequalities
    (to reproduce the result I got, open Wolfram Alpha just type this in the box, and press enter):

    solve b/(1-ab) < b + 12,
    b/(1-2ab)=b/(1-ab) + 12,
    b+3ac=b/(1-2ab) + 12,
    0<a0

    where:
    a is the ratio between the surface of a cube side (c**2) and the surface of the pond
    b is the initial height
    c is the dimension of the cube
    d is the required value (how deep the cubes are below the water)

    The resulting formulas are a little complex, so I am not posting them here, but b, c, and d can be computed from the variable a alone.

    For example, if we fix a = 1/3 with the pond surface being a rectangle of width c and length 3c (so that we can place 3 cubes side-by-side and those occupy the whole surface), we obtain:
    b≈1.35925 c≈25.126 d≈1.35925

  19. #19 George Lasry
    14. November 2021

    For some reason, the last equation (0<a0) is wrong (I entered the correct ones, but it is wrongly shown).

    replace with the following lines:

    a=1/3,
    d=b+3ac-c

  20. #20 George Lasry
    14. November 2021

    still wrong! trying again

    a 0

  21. #21 George Lasry
    14. November 2021

    Still wrong – ignore #19 and #20.

    I think that the browser is interpreting the less-or-equal sign as a tag. When you type into Wolfram Alpha, replace (less-or-equal) with the correct symbols (< followed by =).

    0 0

  22. #22 George Lasry
    14. November 2021

    #21 is also wrong.

    I give up – I can’t enter the correct last 2 equations/inequalities so that they are properly shown. The closest version is #19, but the variable a should be less than or equal to 1/3 (and not always equal to 1/3 as shown in #19).

  23. #23 Karl-Heinz
    Graz
    14. November 2021

    @George Lasry

    HTML-ENTITÄT &le; 😉

    ≤

    https://www.toptal.com/designers/htmlarrows/math/less-than-or-equal-to/

  24. #24 Karl-Heinz
    Graz
    14. November 2021

    Die Idee von George Lasry “Wolfram Alpha” zum Lösen der Gleichungen zu verwenden, ist Goldes Wert. Ich habe kein Problem damit die Gleichungen herzuleiten aber die Lösung dazu zu finden ist schon etwas schwieriger.

    Mein erster Schritt wird sein eine Lösung zu finden, wenn schon der erste Würfel versenkt wird. Ich weiß, dass es hierfür keine Lösung geben kann. Aber ich fange mal mit dem einfachsten Fall an und bin schon voll gespannt was für ein Ergebnis Wolfram Alpha für diesen speziellen Fall liefern wird. Wenn alles gut geht, werde ich anschließend den Fall betrachten, wo der erste Würfel noch etwas hinausragt, der zweite Würfel und damit der dritte auch unter Wasser ist. Der letzte Fall wird dann sein, erster und zweiter Würfel ragen noch aus der Wasseroberfläche raus, der dritte und damit alle anderen befinden sich ganz zum Schluß unter Wasser.

  25. #25 schnablo
    14. November 2021

    It is clear that the first cube is not fully submerged after it is put in. Otherwise it would raise the water level more than the other two. The same goes for the second. However, in order for the the third cube to raise the level by the same amount as the second (and not more), it has to become fully submerged. So we may conclude that that the level after putting in the second cube h is smaller than the cube edge length l. If we call the area of the pond S and the later changes in waterlevel d=12cm we can derive the following equations:

    For putting in the second cube:
    ( S – 2*l*l ) * d = ( h – d ) *l*l ,
    which simplifies to
    S*d – h*l*l – d*l*l = 0.

    For putting in the third cube:
    ( S – 3*l*l )*( l – h ) + S*( h + d – l ) = h*l*l
    or
    S*d + 2*h*l*l – 3*l*l*l = 0

    Subtracting both simplified equations and dividing by l*l yields
    3h +d – 3*l = 0
    or
    h – l = -d/3

    so that we can determine the water level above the cubes via
    h + d – l = d – d/3 = 2/3*d = 8cm.

  26. #26 Karl-Heinz
    Graz
    14. November 2021

    @all

    Bitte für die Lösung immer folgende Parameter angeben.
    h_0 … ursprünglich Wasserstandshöhe
    A … Grundfläche des Wasserbecken
    C … Kantenlänge des Würfel
    Δh = h_3 – C … Höhe Δh, von der Wasserobefläche bis zur Oberseiten der Würfel

  27. #27 George Lasry
    14. November 2021

    Could you explain the first equation (including whether h is the height with 0, 1, or 2 cubes, which is not clear)?

  28. #28 schnablo
    14. November 2021

    h is the water level after the second cube has been put in.
    The equations are derived in the following way: Imagine that a cube is put in but the water that it displaces is removed such that the water level does not change. This amount of water is on the right side: previous water level times area of the cube.
    Then the displaced water is put in again raising the level. This is what’s on the left side of the equations.

  29. #29 George Lasry
    14. November 2021

    Thx!

    I fully understand the first equation, but not this one:

    ( S – 3*l*l )*( l – h ) + S*( h + d – l ) = h*l*l

    what is the logic behind this equation?

  30. #30 George Lasry
    14. November 2021

    schnablo: Ignore #29

    I tested your computations, and they are fully correct. Well done!

    My own computations were most probably buggy

  31. #31 Karl-Heinz
    Graz
    14. November 2021

    Ich möchte jetzt zeigen, dass es kein Lösung gibt, wenn man den ersten ersten Würfel ins Becken stellt und die Wasseroberfläche gleich oder höher ist als die Würfeloberseite.

    Lösung des Gleichungssystem für diesen speziellen Fall

  32. #32 Thomas
    14. November 2021

    Since it appears the solution can exactly be found by solving equations, I’m wondering what the benefit of an optimization algorithm like hill climbing might be.

  33. #33 Karl-Heinz
    Graz
    14. November 2021

    Ich bin schon gespannt, ob es für den Fall Nr. 2 eine Lösung gibt.
    Beim erstmaligen reinsetzen des Würfel reicht das Wasser nicht bis zur Würfeloberseite.
    Beim zweiten reinsetzen des Würfel ist dieser vollständig oder höher von der Wasseroberfläche bedeckt.

  35. #35 Klaus Schmeh
    14. November 2021

    8 cm appears to be correct! Thanks to all for this great discussion.

  36. #36 Colin Wright
    UK
    14. November 2021

    It can be solved exactly, and there are several methods for doing so.
    In some sense the simplest is to use a constraint solver, and the reason
    I used an optimisation algorithm (specifically ballistic hill-climbing) was
    to test the algorithm in the setting of a constraint problem.

    It was interesting to see it converge to local optima that did *not* satisfy
    the constraints, so then the question is: How can we adapt the algorithm
    so it recognises when it has a local optimum (because the constraints
    are not satisfied) and perform a “re-start”.

    So this was an interesting problem to use as a test case, and knowing
    it has an exact solution that can be found by “clean reasoning” makes
    it doubly suitable.

  38. #38 Karl-Heinz
    Graz
    16. November 2021

    Finde ich echt cool.
    Es kommt sogar der Begriff Hillclimbing vor. 🙂

    https://de.m.wikipedia.org/wiki/George_Lasry

  39. #39 De1m0s
    Saarland
    26. November 2021

    Hier mal ne Beispielrechnung. Es gibt mehrere Lösungen.

    Die Würfel sind hxbxt 50x50x50 cm = 125.000 cm^3

    Das Becken hat eine Grundfläche von 50×208 cm.
    Wir betrachten den Fall, wo der 1. Würfel schon im Wasser ist, aber nicht voll bedeckt. Wasserhöhe ist nun 40 cm, d.h. der Würfel beansprucht ein Volumen von 50x50x40=100.000 cm^3
    Im ganzen Becken wären dann 50x208x40cm = 416.000cm^3.
    Grundfläche des Beckens ist also hier 10.400cm^2.
    Entferne ich den Würfel, sinkt das Volumen um 100.000cm^3 auf 316.000cm^3. Wasserhöhe wäre also nun 30,38 cm. Erste Bedingung ist also erfüllt, dass der 1.Würfel den Wasserspiegel um weniger als 12cm anhebt.
    Lege ich den 2. Würfel ins Wasser, befinden sich 416.000+125.000cm^3 im Becken, was einer neuen Höhe von 52 cm entspricht.
    2.Bedingung also auch erfüllt.
    Beim 3. Würfel habe ich ein Gesamtvolumen von 416.000+125.000+125.000, geteilt durch die Grundfläche wäre das eine Wasserhöhe von 64cm.

  40. #40 Narga
    26. November 2021

    @De1m0s: Ab deinem Satz “Lege ich den 2. Würfel ins Wasser…” ist nicht bedacht worden, dass jetzt auch der 1. Würfel komplett (und nicht nur zu 40 cm) im Wasser ist. Das Wasser hat ein Volumen von 316000 cm3, die beiden Würfel zusammen 250.000 cm3, daher ist das Wasser mit zwei Würfeln in deinem Beispiel eigentlich 54.42 cm tief.

  41. #41 De1m0s
    29. November 2021

    @Narga:
    ok, stimmt. Was aber am Wahrheitsgehalt der Rechnung wenig ändert, ausser das am Schluss die Wasserhöhe ca 66cm ist, statt 64.

  42. #42 De1m0s
    29. November 2021

    Stopp.
    Das letzte Posting war ne glatte Milchmädchenrechnung.
    Mein erster neuer Gedanke war, dass, wenn 2 Würfel im Becken sind, dürften beide noch nicht vollständig mit Wasser bedeckt sein; was aber auch unmöglich ist, da das Wasser dann beim 1. und 2. Würfel um den gleichen Wert steigen müsste. Jedenfalls könnte beim 3. Würfel das Wasser nicht um den gleichen Wert steigen wie beim 2.