The fish pond problem
British Professor Colin Wright has sent me an interesting puzzle. Can any reader solve it?
There will be another online talk at ICCH on Sunday. Cipherbrain reader Jerry McCarthy will be speaking on “A Simulator for the Welchman-Turing and US Navy Bombes”. Anyone who wants to watch, feel free to send me an email and I’ll forward the dial-up link. There is no charge to attend.
My last talk was on October 3. Together with Elonka Dunin I presented about solving old encryptions with modern methods. Among other things, it was about Hill Climbing and Simulated Annealing. The event was hosted by the National Museum of Computing in Bletchley Park. The event was moderated by the above mentioned Jerry McCarthy.
Ballistic Hill Climbing
Among the audience at my talk was Colin Wright, a mathematics professor from Liverpool. Colin has developed a mathematics of juggling which he presents in very entertaining talks. I had heard about this before. Cryptography lectures are also part of his repertoire. As I now know, Colin lives not far from Otterspool Park, but even he doesn’t know the significance of the sign there, which I blogged about recently.
After the talk, I struck up a conversation with Colin. He asked me if I had ever heard of Ballistic Hill Climbing. I had not. He explained to me that Ballistic Hill Climbing assumes that the climber has some inertia. When the climber has reached a summit, he does not simply stop there, but continues a bit further in the corresponding direction, even though it is going down again. By this inertia one reaches that the climber on a local maximum (thus with a false solution) does not necessarily stop, but has the chance to reach another maximum.
In addition, Colin pointed out to me that Hill Climbing can also be turned around by looking for a minimum (i.e., a valley bottom) rather than a maximum (i.e., a peak). This technique is called Valley Descending. This was also new to me.
Both ballistic hill climbing and valley descending can be used to solve ciphers, according to Colin. Has any reader had any experience with this? If so, Colin would appreciate a comment or contact. Maybe an exchange of experiences will come about.
The fishpond problem
As a follow-up Colin sent me a puzzle:
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?
Does a reader find the solution? There are certainly several methods for doing this. According to Colin, a combination of ballistic hill climbing and valley descending (quasi ballistic valley descending) can be used. Here’s what he wrote to me about it:
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.
Can this technique also be used to solve encryption? Colin writes:
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.
I would appreciate some appropriate comments.
If you want to add a comment, you need to add it to the German version here.
Follow @KlausSchmeh
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/
Letzte Kommentare