2694: Königsberg

|< < Prev Comic #2694 (November 4, 2022) Next > >|

Königsberg

Title text: At first I thought I would need some gold or something to pay him, but then I realized that it was the 18th century and I could just bring a roll of aluminum foil.

Explanation

Königsberg, Prussia in Euler's time, showing the Pregel river and its seven bridges. Two of the original seven bridges no longer exist,[1] although there are three new bridges. The Baltic port city is now Kaliningrad, a Russian exclave.

This comic is about the Seven Bridges of Königsberg, a seminal graph theory problem solved by the famous mathematician Leonhard Euler.[2] The problem was whether a path through the city crossing each of the seven bridges just once exists, without crossing the river forks any other way. In 1736, Euler proved that no such path exists. This result is considered to be the first theorem of graph theory and the first proof in the theory of networks[3] — a subject now generally regarded as a branch of combinatorics — and presaged the development of topology. Combinatorial problems of other types had been considered since antiquity. Graphs are a data structure common in many algorithmic problems in computer science.

Cueball attempts to cheat on the final exam in his algorithms class by traveling back in time to commission the construction of an eighth bridge before Euler could learn of the problem, allowing a trivial solution that would remove the rationale for further analysis. He hopes that this would alter his present-day timeline in such a way that the test becomes easier because graph theory might never have been developed. The use of the word "tried" implies failure, which is probably a good thing since his success would create a paradox. Time travel is a recurring topic on xkcd and examples where attempts to change the past fails has also been used before like in 1063: Kill Hitler.

With the addition of the eighth bridge, it becomes possible to cross each bridge exactly once, starting at the north bank and ending on the larger eastern island, or vice-versa. However, there is still no way to traverse each bridge exactly once and return to the starting point, because the altered graph would have an Euler trail but not an Euler cycle. Thus the problem might still have been interesting to Euler.^{[citation needed]} (Adding a ninth bridge connecting the north bank to the east island would render the problem completely trivial.) We can't say whether Euler or others would have developed graph theory anyway, or whether Cueball's exam would have been any easier or more difficult.

An alternative modification allowing an easy solution is to remove bridges. During World War II, two bridges to the central island connecting it to the north and south banks were destroyed by bombing, so today there is an Eulerian trail across the five remaining bridges.

The title text alludes to the fact that ordinary aluminum foil, which was not commercially available until 1911, would have been a tremendously valuable curiosity in the 18th century, which didn't even have tin foil (the inferior pre-World War Two version of aluminium foil, but the name still persisting to refer to its successor). Aluminum was a highly priced metal before the 1880s when inexpensive methods were developed to refine it. The Washington Monument was constructed with a tip made of pure aluminum due to its value and conductive capacity (this turned out to be a bad idea, because it attracted lightning, which melted some of the aluminum). Aluminum had not been extracted in its pure form at the time of Euler, and was known only in compounds such as alum, so the metal would have been unique and exotic. The value of aluminum and the use of it as the tip of the Washington Monument was also mentioned in 1608: Hoverboard where a heist to steal the tip is depicted.

Transcript

[Cueball, standing next to two men wearing wigs, pointing with a pointer at a map showing the seven bridges problem, with an extra bridge added in dashed lines]

Cueball: Lord Mayor of Königsberg, I will reward you handsomely if you construct this bridge before my friend Leonhard arrives.

[Caption below the panel:]

I tried to use a time machine to cheat on my algorithms final by preventing graph theory from being invented.

 add a comment! ⋅  add a topic (use sparingly)! ⋅  refresh comments!

Discussion

Why would aluminum foil be valuable? I can see how it would be hard to produce at the time. But how would it be used and why would people of the time see a lot of value in it? 172.71.146.65 03:42, 5 November 2022 (UTC)

Good question, but I'm persuaded the novelty and scarcity of metallic aluminium would have made it plenty valuable among those already wealthy enough to recognize what it was. Prussia was wealthy and Königsberg was its largest port city back then, so probably the mayor would have been able. 172.70.206.205 03:49, 5 November 2022 (UTC)

Aluminium was very valuable - methods for its extraction from ore didn't exist in any useful form until much later. 172.68.146.80 03:55, 5 November 2022 (UTC)

Would scarcity be enough to make it valuable? Since nobody had this material back then, there wouldn't be any known applications for it. Compared to bringing e.g. a simple pocket calculator, a flashlight, a solar-powered e-book reader, etc. If an alien landed in my house and brought me some weird, shiny material that would be unable to build on earth, I wouldn't be too interested. But if they had some cool gadget or books full of alien information, I would immediately see its value. 172.71.142.88 04:05, 5 November 2022 (UTC)

At the time, there were few chemists who could have recognized what it was, but the Mayor of Königsberg would plausibly have been able to commission one. It likely would have taken months if not years, though. I guess if you have a time machine such details don't matter. 162.158.166.173 04:11, 5 November 2022 (UTC)

Bear in mind that platinum was once 'an inferior substance that got in the way of accumulating silver', and cobalt was the stuff that the underground spirits mischievously put in the way of those seeking copper. To different degrees, their attractiveness has increased since those times they were considered less than desirable.

But, for aluminium foil, I suspect it would have been like pineapples in English(/European?) stately circles... Not to be used for anything practical, but shown off (as long as it did not deteriote beyond a certain point), possibly there'd be money to be made in 'hiring it out' to decorate tables at fancy dinners (in carefully handled fragments, after the first few tearing incidents). L

“Not to be used for anything practical”: Well they could wrap their leftovers in it…

Before they put them in the fridge?  ;o)

Perhaps BBQing vegitables? 172.69.33.162 20:37, 5 November 2022 (UTC)

No doubt a natural philosopher or somesuch would give his eyeteeth to analyse the substance, but being so far beyond the ability to recreate (assuming they discovered what they might even need to do) it would take the bankrolling of an extremely rich patron to obtain permanent posession of some without obligation to return it to the social circuit situations. So easily destructed (I wonder if they'd discover thermite a hundred and more years early, before they ran out of potentially finely shredded aluminium?) or at least aesthetically denatured.

I suppose a screwed up ball of foil (carefully glued together internally, of all fragments still reobtainable) could be the end-game for the original roll, and a wonder it could still be (again, taking the "pineapple place" on the tables of the high and mighty, relatively untarnishing as it would be and gingerly some lucky few would be allowed to hold it and marvel at its sharp fragility and metallic lightness.

...or, in another destiny, perhaps it would be given to a master tailor, in order to (try to?) create some sartorial masterpiece for one or other monarch of the age. Not that I'm sure they'd be able to accomplish that properly (limited pre-offcut trials on how to attach it to underfelts/whatever and to somehow exploit its flexibility without exceeding its very low tolerance for shear-force damage). It'd be a story and a half, whatever happened to it! 172.70.86.12 05:38, 5 November 2022 (UTC)

"Aim for brevity while avoiding jargon." —Edsger Dijkstra 172.69.33.210 06:33, 5 November 2022 (UTC)

Re: wealth signaling via aluminum - When aluminum was first extracted, one of its main early uses was in jewelry. Victorian examples are still around and are not terribly rare. Miamiclay (talk) 20:33, 5 November 2022 (UTC)

Noting that "the citizens' old coffeehouse problem" (c.f. linked reference), originally of how to cross the bridges was never solved but instead proven by Euler to be insoluble. He did give a proof to satisfy those who had henceforth decided there perhaps could be no solution, but that necessarily postdates the initial issue that could not originally be solved, and which Euler (in turn) also did not solve. But how to rewrite this to everyone's satisfaction? I see a bit of a tussle of interpretation in the edit history over this. 172.71.178.187 13:50, 5 November 2022 (UTC)

Proving that a problem has no solution is still called solving it in math and logic. 172.70.211.126 15:34, 5 November 2022 (UTC)

That's solving the issue of the solution (if you've proved there is none), at the meta- level. It is described as a "negative resolution" in the primary wikilink, which adds another semantic complexity but at least points to what was proven. Right in its first paragraph. For the everyday reader that hasn't yet burrowed into the wikilink, and without in-depth knowledge of terminological scope, they shouldn't be given the wrong idea about what question was actually answered. And "We've solved it: there's no solution!" is not a particularly helpful reduction of this kind of outcome. 172.71.178.207 16:53, 5 November 2022 (UTC)

Ordinary usage by mathematicians and laypersons alike is that e.g. Wiles "solved" Fermat's last theorem, by proving no solutions exist. The AMS source has the same usage. 172.71.154.40 22:56, 5 November 2022 (UTC)

...ok, so looking at it myself, maybe this change removes both parties' objections. (Probably not, but perhaps a way towards a final rapprochement.) 172.70.85.24 17:02, 5 November 2022 (UTC)

Sure. That's fine. 172.71.154.40 22:56, 5 November 2022 (UTC)

I read somewhere (maybe some Martin Gardner book?) that nowadays in Koenigsberg (or Kaliningrad as it is called today) there IS an eight bridge. But I couldn't confirm it.--162.158.129.49 17:26, 5 November 2022 (UTC)

There's a link to the Google Maps aerial view in the map caption. 172.70.210.242 20:31, 5 November 2022 (UTC)

As the comic at face value is about city planning of Königsberg and features the Mayor of Königsberg and a map of Königsberg, I very much think that an explanation of what Königsberg is should be a part of an explanation of the comic. So I disagree with this edit and its summary. Also, what I have been taught about image captions is that they should explain what is seen in the image. The information that two bridges has been destroyed is already present in the comic explanation. —While False (museum | talk | contributions | logs | rights | printable version | page information | what links there | related changes | Google search | current time: 09:24) 17:46, 7 November 2022 (UTC)

(While you were writing that, I was writing this. Copied up from the "my text" bit of an edit-conflict verbatim as it definitely is stil relevent.)

About that... I agree with some editors that the caption isn't really where 'current status' geopolitical and infrastructure information should be. I also agree with other editors that it isn't nececessary for the Explanation (of which the image and its caption is technically part). So, how about... a Trivia section? Can be less cramped as well as heing auxiliarily informative about these things in a few (relatively) short points.

• "Today, K. is known as ..., and is located in the modern-day...", plus
• "Since that time <x> bridges were destroyed/removed, <detailed thus>, and <y> bridges have been built, <also detailed>", and maybe also
• "Currently <...pedestrians can do this, vehicles can (only?) do that...>"..?

...but perhaps leave the map-link and add a tiny bit more, "...also see <maplink> or <Trivia-anchor>", in the caption itself.

For consideration, anyway. 172.70.162.47 18:02, 7 November 2022 (UTC)

Sure —While False (museum | talk | contributions | logs | rights | printable version | page information | what links there | related changes | Google search | current time: 09:24) 18:37, 7 November 2022 (UTC)