Placeholder Image

Subtitles section Play video

  • People living innigsberg,

  • in what is now Russia or Poland...

  • Hard to say which.

  • They had seven bridges across

  • two shores of the Pregel River and

  • there's [sic] two islands!

  • One island here...

  • An island over here...

  • Bluh

  • Bank over here,

  • bank over here.

  • And they've got it set up

  • so that there's seven bridges.

  • One, two... So you could go, you know,

  • you'll wanna walk over this way.

  • You could take a horse and bug over to that side,

  • cross over here,

  • cross over here,

  • and cross over here.

  • One, two, three,

  • four, five, six, seven bridges!

  • People argued: "Can you take a Sunday walk and just cross every bridge once?"

  • So, I wanna go out someday

  • and just walk across this bridge,

  • walk across this bridge,

  • walk this bridge...

  • Ah, I'll go this way this time!

  • Walk across here,

  • walk across here... Oops!

  • I can't do it, 'cause I've already crossed those

  • and I've left one.

  • I don't care where I start and where I stop.

  • But can I cross every bridge one time?

  • People argued about it.

  • Nobody was able to do it.

  • Euler's at Saint Petersburg, working for the tsars,

  • and he hears about this problem.

  • And up until then people had said:

  • "Well, we have to make a list"

  • "of all possible ways to do this."

  • "We have to try here, go there..."

  • [sound of a series of choices]

  • And in this wonderful paper that Euler writes,

  • he says,

  • Trying to solve it, one at a time,

  • doesn't tell us anything new.

  • It's today what we would call a numerical solution.

  • That might give you an answer, but

  • it doesn't give you understanding.

  • He's saying, "Hm, how do I do this, ahn?"

  • And then, he says,

  • "Think about ordinary bridges."

  • Every time I walk across a bridge onto an island,

  • I go from Blue to Polka Dot Land...

  • Oh, Blue to Polka Dot Land,

  • Polka Dot Land to Red,

  • the Red Shore over to Polka Dot Land...

  • Oh, okay.

  • Euler resigned concentrating on the bridges,

  • starts saying,

  • "Look at the islands, look at the landmasses."

  • "Let's label those and think about that."

  • So he goes over and says,

  • "I'll label them."

  • Oh, okay.

  • I'll label, what I call Polka Dot Ville,

  • I'll call that A.

  • I'll reach my pocket and call that B over here.

  • Over here, this side, let's call it C.

  • And, oh! Look at this!

  • There's D.

  • I shouldn't be walking in the water.

  • I should just stay on the b...

  • In fact, I can't do that.

  • I ought to just stay on the bridges the whole time.

  • Keep me honest, you, Brady. Ahn...

  • [Brady]: Oh, you stepped on the water.

  • Oh! Opa pa pa!

  • Let's make it real simple.

  • If I have nothing but

  • a bridge going from

  • C to D to B.

  • Let's start from C to D.

  • Po po popopo...

  • Ok, that's legal.

  • So I have C -> D.

  • Then I go from D to B.

  • Oh, it's D -> B.

  • Every time I get from one to another,

  • from one landmass to another landmass,

  • I can make a list -- of -- my -- travels.

  • Oh! Oops, stay out of the water!

  • Euler says, "This means that"

  • "if I have even number of bridges,"

  • "one-one,"

  • "going into and out of an island,"

  • "that's completely legal."

  • I can go right through the island

  • if I have two or

  • if I have four bridges...

  • Oh, you can come across here, come across here,

  • back, over, and back.

  • But an *odd* number of bridges...

  • Okay...

  • I can come across here,

  • and come across here...

  • But I'm stuck!

  • Go this way, turn around,

  • but I haven't crossed this one.

  • Alternatively, I could start on yellow... on D,

  • walk this way, come back here,

  • and then walk out here.

  • Euler says, "Oh!"

  • "If I have an odd number of bridges"

  • "to any or from any island, I have to either"

  • "start my walk at that location"

  • "or end my walk at that location."

  • Right now,

  • island A has two bridges going to it.

  • That means, oh, if I do not start on this island,

  • I can just traverse it.

  • You know, Euler goes on and says,

  • "And if I start in that island,"

  • "I can go around -- blah, blah, blah"

  • "Vu vu vuf -- and return to it."

  • Even numbered islands,

  • islands that have an even number of bridges going to 'em.

  • I've got it made!

  • This makes it possible for me to -- to -- to--

  • almost eliminate them from my thought process.

  • And it works whether it's

  • two, four, or even...

  • Or even six.

  • Ok, got that one.

  • Any landmasses, any place that has a

  • bridge connected to it,

  • if it has an even number of bridges -- oh!

  • Easy! Piece of cake.

  • If it has an odd number of bridges,

  • then it's a special case.

  • Clearly, if there is just one landmass

  • that has an odd number of bridges,

  • I can start on it,

  • but I won't be able to get back to it to stop on it.

  • But if I have two islands that have an odd number of bridges leading to them,

  • I can start on one, traverse around,

  • and then end on the other one.

  • Now, let's go back to what was really happening innigsberg around 1725.

  • Seven bridges, remember?

  • Wasn't arranged like this.

  • It was...

  • One, two, three, four, five, six, seven. Ok.

  • Let me see...

  • [splashing water sound]

  • Let me see how I'm doing.

  • This section, the Red Shore,

  • what he calls C,

  • I have -- one, two -- three bridges from.

  • [Brady]: Odd.

  • Oh, it's and odd number!

  • Odd number!

  • Okay.

  • How about D?

  • Let go over D, island D.

  • One, two -- three bridges.

  • Oh, this is odd.

  • How about... The North Shore, B?

  • One, two, three -- odd number.

  • What about island A?

  • One, two, three, four -- five!

  • An odd number.

  • All of this landmasses have an odd number of bridges leading to 'em.

  • Euler says, "Nuh-uh,"

  • "none of them have an even number of bridges."

  • "All are odd."

  • No matter where you start,

  • you cannot traverse all those bridges. ∎

  • Along, comes World War II: bomber attacks.

  • Horrible! Just a desperately horrible situation.

  • Two of these bridges get destroyed.

  • The town is devastated,

  • but at the end of the war,

  • there's five bridges left.

  • So, in a sense, today

  • there's no Seven Bridges ofnigsberg anymore.

  • Not only there are not seven bridges,

  • the city ofnigsberg doesn't exist.

  • It's been renamed to Kaliningrad.

  • It's a part of Russia today.

  • Or I think the Baltic Fleet works out of there.

  • And there's five bridges.

  • Well...

  • Suppose you're sitting around in today's city.

  • Could you do this?

  • Well, before even trying, let's just note:

  • C over here, node C,

  • this landmass of C, has two bridges today.

  • An even number.

  • Over there, the landmass B, the blue one,

  • has one, two bridges from it.

  • What about island A?

  • One, two, three bridges, an odd number.

  • Island D -- one, two -- three bridges.

  • Oh! Thus, today there is no problem!

  • From what Euler said, we could start on either of the odd-bridged islands.

  • So I can start here,

  • and I'll end there.

  • I have to choose a path that takes me from here to there.

  • Ok. I'll go like this:

  • (Po po po po)

  • Crossed one bridge.

  • Crossed two bridge.

  • I'll walk across my third bridge backwards.

  • Walk across the fourth bridge forwards,

  • back to where I started, but wait!

  • There's one more bridge.

  • (Po po po po)

  • I've traversed the entire path.

  • Started there, ended there.

  • Euler has told us that, if there are exactly

  • two islands that have an odd number of bridges,

  • you have to start on one of them and end on the other one.

  • If there were three islands that had, each had an odd number of bridges,

  • no way!

  • You couldn't solve the problem.

  • However, if each island had an even number of bridges...

  • Suppose next week there's an earthquake.

  • At the Baltic Sea, it knocks down one bridge.

  • Now, every landmass has two bridges going to it.

  • And even I can figure it out,

  • oh, yeah, I can traverse them all.

  • Here's the first one, here's the second one,

  • here's the third one, here's the fourth one.

  • I traversed them all without any problem at all.

  • Ok, suppose we only have three bridges today.

  • [Brady]: Another earthquake.

  • Another earthquake happens!

  • Ahh! Another bridge falls down!

  • Now, Island A has one bridge leading to it: an odd number.

  • North Shore B has two bridges leading to it: even.

  • D over here, Island D has two bridges

  • and C, where I'm standing, has only one bridge on it.

  • In this case, Euler tells us, yes, we can still make a circuit

  • that crosses all three bridges

  • but we have to start on an odd-numbered place

  • and end on an odd number. So,

  • I'm on the odd-numbered C,

  • there's only one bridge, one is an odd number.

  • Okay -- (po po po po!)

  • Got to D.

  • D is an even one. Oh, ok.

  • I'll walk across this one.

  • (Pop pa!)

  • And then I get to B and, oh,

  • I can walk across this.

  • I end up on an odd-bridged island

  • and have completed traversed it.

  • If all the islands have an even number of bridges,

  • even everywhere!

  • Then, we're even-Steven, piece of cake.

  • You can make this traverse and everybody in the saloon,

  • in their Sunday walks, they're happy!

  • What if there's only one odd-numbered island?

  • Turns out you can't make such a thing.

  • If I have...