Placeholder Image

字幕表 動画を再生する

  • I want to tell you about a generalization of a problem

  • that was first popularized by Al Cohen of York, who was an anglo-saxon

  • really smart dude. The problem is: you have a farmer who comes to your river and with him he has a wolf,

  • a bundle of cabbages and a goat; and there's a boat,

  • that's there and it carry-- it can carry him, and

  • one of his charges. Obviously the farmer has to be there because he has to be rowing,

  • and he wants to bring everything to the other shore safely. So that means that he cannot leave

  • the cabbage with the goat, because the goat would be eating the cabbage,

  • and he cannot leave the wolf with the goat because then the

  • wolf would eat the goat. So how can he do it?

  • And so of course we're assuming that the wolf cannot swim

  • which is a question I get all the time, when I'm speaking

  • to kids. So the wolf cannot swim neither can a goat or the cabbage.

  • So the only thing you can do at first is to

  • bring the goat.

  • Okay, so then, okay, the farmer goes back,

  • and he--

  • takes, let's say, the wolf; but now he cannot leave the wolf with the cat--

  • with the goat. Otherwise the wolf would eat the goat back. So what if he brown the cabbage instead?

  • Well, same thing if he brings the cabbage now,

  • the goat would eat the cabbage. So the only way it can be done

  • is you have to have this clever moment of saying "Oh, I can bring back the goat". So, okay,

  • he brown the cabbage over

  • and now he brings back the goat, and now takes the wolf, brings it to the other side as well,

  • and now he goes back just to get his goat. So...

  • Then you can generalize, you can say "Well, Let's say that this farmer had more things

  • that he wanted to carry across the river".

  • So let's say that I added a rabbit, so

  • What can I do first?

  • Brady Haran: What does a rabbit day with what?

  • Oh.

  • Brady Haran: Who is in danger from who here?

  • Yeah good question right, so the wolf would eat the rabbit,

  • and...

  • Ah well the rabbit would eat the cabbage.

  • We assume that the rabbit and a goat together are fine.

  • There won't be too much violence there. The boat can hold the farmer and

  • one of these guys. That's it, the farmer still has to be there.

  • We're still assuming also that the revit cannot swim. So what can I bring first?

  • Can I bring the wolf? Well, no obviously the rabbit and the goat would eat the cabbage.

  • Can I bring the rabbit?

  • Well, no again the goat would eat the cabbage, if the wolf doesn't catch the gold first.

  • Okay, can I bring the goat? Well,

  • no, the rabbit will eat the cabbage again,

  • if the wolf doesn't catch the rabbit first.

  • And can I bring the cabbage? No, because the wolf would eat the rabbit and the goat.

  • Brady Haran: Carnage.

  • Carnage, yes. Blood everywhere no matter what we do

  • or shreds of cabbage, one or the other. So the question becomes: Okay,

  • How big of a boat do I need? So if I'm given

  • different things, and I know there's certain conflicts how big does my boat have to be? So here if I have space for

  • my farmer plus two other things, I'll be fine. I could just say fine, I'll bring the wolf and cabbage first

  • I'll leave them on the other side, come back, and get my rabbit and goat

  • and I will be done.

  • Super easy!

  • So the question is how big does it have to be? Well, now we kind of want to start doing math, right?

  • So how do we bring math in there? So we want to think about the conflicts as making a graph. So I have my--

  • wolf, and I have my goat; and so I cannot leave my wolf with my goat

  • so I'll put an edge, the line, between these two points which are really

  • normally called "vertices".

  • Brady Haran: So edge represents bad news.

  • Yeah conflict, that these two things cannot be left alone unsupervised.

  • The wolf can also not be left

  • with the rabbit. The goat cannot be left with the cabbage and the rabbit cannot be left

  • with the cabbage either.

  • But the wolf can be left with a cabbage so I don't draw an edge there,

  • and I don't draw an edge between my goat and my rabbit because it can be left together.

  • Okay, the point that we see is that let's say that I first took my rabbit, well,

  • there's still some lines remaining, right? I am left with a

  • graph with the wolf, goat and cabbage and there's still some lines that are remaining.

  • And that's tree firing remove any of the corners.

  • So what I want to do is

  • take a set of my things, that will remove all of the lines, and that's actually a really important math concept.

  • It's called a "vertex cover".

  • So, maybe let's write down, what is the vertex cover. "A vertex cover and

  • a graph G is a set of vertices such that any edge is

  • adjacent to at least

  • one

  • of these services". Okay,

  • so what does that mean? That means that

  • if I want to take a set of points, where

  • every line is touching at least one of these points, my goal is that by taking the vertex cover,

  • I'm removing all the lines so maybe we can just draw a simple example.

  • So, let's say that I have this graph.

  • So, this is a graph so a graph is really just a set of points and set of lines called vertices and edges,

  • and so I might ask myself "What is a vertex cover?" So I could start building one. So I could say "Okay

  • I'll take this vertex within my

  • vertex cover".

  • But that's not enough, right? So these five edges now are covered by this vertex right they're touching...

  • this vertex, but the other ones aren't yet.

  • Now so I could ask "I could add this vertex to my vertex cover, and so I'm getting closer".

  • But I still have this line that is not covered yet.

  • So I could add this one now. And so these three vertices from a vertex cover

  • every single line is adjacent to one of these vertices.

  • Brady Haran: It's almost like how many hands did you need to cover the right number of spots?

  • Yeah exactly, exactly.

  • So here in a vertex cover...

  • What was it? Well, yeah one is not sufficient, right?

  • A single vertex is not a vertex cover. If I cover the rabbit and the goat,

  • then they're covering all of the

  • edges. There's no edges remaining so this forms a vertex cover.

  • So that's why I need to have at least

  • two seats, because the minimum size of a vertex cover in there is 2. So there's no way that I can do it if I

  • don't have at least two extra places besides the place for the-- farmer. So in general

  • I know that my boat has to have at least the minimum size of a vertex cover.

  • Right? Otherwise

  • I won't be able to make my first trip, because there will be some lines remaining in my graph,

  • And lines represent conflict.

  • Brady Haran: I imagine you could do overkill though,

  • there must be as these things get more complicated. There must be--

  • vertex covers that cover too many vertices.

  • Oh yeah, that's a really good point, right? So in this graph for example--

  • So if I add this vertex, this is still a vertex cover,

  • right? So, I really want the minimum one. So I want to say that the

  • "number of

  • extra places

  • needed in my boat is at least the

  • size of the minimum vertex cover". So in this graph here that was three.

  • I needed to have at least three--

  • Brady Haran: Because that final the smallest possible.

  • Yeah, you don't want to overkill as you said. So that's nice, but now you might ask yourself: Will that always be enough?

  • Right? Like-- Sure you can do the first trip across the river,

  • but will you be able to do all of them? And so now you could check with some examples.

  • So, I mean, we could try with a big example and see if it works out,

  • and then...

  • Try with some other examples. Does that sound good? Okay,

  • so maybe we need another piece of paper. Okay

  • so now we have way more things. And so now we need to think for a second, what is actually going to eat what.

  • And we might disagree on some of these. I am NOT a farm girl

  • So I would go with what I think. The wolf would eat the goose.

  • Potentially, the mouse if it's really hungry. Told eat grass.

  • It... won't eat the cat either, I don't think so. Carrot or cabbage

  • It's not a vegetarian. It's a carnivore so set a goat and the rabbit; and the goose will eat

  • Ahhh... the grass, I see geese eating grass all the time. I don't think it's gonna eat carrot or

  • cabbage because it doesn't really have-- does it have teeth?

  • Does I don't think... I mean certainly if it's not cut up,

  • you know, like it will have trouble it doesn't have hands to--

  • Brady Haran: Maybe this does not the taste of cabbage.

  • Fine. I think the mouse will eat carrot,

  • and...

  • the cabbage and...

  • the cat will eat the mouse, certainly.

  • The grass will probably be eaten by the goat. I know that you can use them as long Moore's. The rabbit might eat some grass?

  • Cat I think it will just eat the mouse and nothing else will eat it

  • Brady Haran: The rabbits gonna eat the carrot

  • Yes, so the cabbage yeah, that's true.

  • So the rabbit will eat the carrot and the goat will probably eat the carrot too,

  • and the rabbit will also eat the cabbage, and so will the goat,

  • and then the goat and a rabbit are fine. I think that's that looks reasonable to me.

  • Brady Haran: Okay that will be air I guess...

  • Do you agree? Okay, so let's say that I have a river

  • How big it boat we need, and will the minimum vertex cover be enough? The first point

  • I really want to make is that finding the minimum vertex cover is not easy.

  • Right. So, here we only have nine things. right? It's not that much, and to figure out

  • what it is, well since this graph has some meaning,

  • I'm going to use the meaning to help me. So I basically have like my carnivores, my herbivores,

  • and then I have the poor vegetables and herbs. And so these three categories

  • kind of help me determine that oh, maybe

  • the

  • goat rabbit

  • goose and mouse. So my herbivores might form a vertex cover, and I think if I look at it,

  • carefully, like if I were to really look at every single

  • line, so actually yes, the mouse the goose the rabbit and a goat do form a vertex cover

  • It's unclear if that is actually the smallest, I claim it is.

  • It's not an actually such an easy thing to check, so let's just assume that I'm right. So what I'll do is

  • I'll say: Okay for my first trip, I will take my minimum vertex cover.

  • Right? So if I remove my goat, rabbit, boots and mouse;

  • and bring them to the other side. I am left. I removed all of the lines, here,

  • and so, okay, that's fine.

  • So then my farmer will come back.

  • We can only take four things, it will leave a thing behind. Let say it leaves the cat behind

  • And so he brings these guys.

  • But certainly the wolf will attack these guys, and these guys will eat all of the vegetables and grass.

  • So I'll bring them back

  • So it's the same trick as we've seen before. I'll carry my cat over so that it doesn't eat my mouse just itself, right?

  • It's just four places, but you can just bring one thing. That's completely fine.

  • And then I will finally go back, so there's no conflict here. All right this was the

  • original things that I had left at first so no problem there, and then I'll bring my four leftover...

  • herbivores and leave them there.

  • And I'm done!

  • So I succeeded in this case, right? But that's not a proof, right? Maybe...

  • Maybe I wouldn't need more, and certainly We've just seen okay finding your minimum vertex Cover is not necessarily so easy

  • So maybe let's do one other example.

  • So let's say that I had just--

  • my wolf

  • and--

  • my--

  • four herbivores that would get eaten by my wolf.

  • If he has a chance. So my wolf would eat all of these,

  • and none of these would attack each other, right? So I have my river

  • So, I know that I need to have at least... The number of extra places should be at least the size of

  • my minimum vertex cover, which here is easy to calculate. What is it Brady? Do you know?

  • Brady Haran: It's one.

  • It's one...

  • Brady Haran: You should ... the wolf

  • I'm very impressed. Okay, so my wolf is my minimum vertex cover, so I need to bring my well first, right?

  • That's the only thing I can do if I bring anything else. I'll be left with some conflict. So I bring my wolf over.

  • I Come back as I can only take one thing

  • So let's say that I take the mouse.

  • But they all really look the same, like the graph all looks the same for all of them,

  • and these are cold different things, but it could have been called--

  • you know goat one, goat two, goat three and goat four. Really, so I bring my mouse over

  • So now I have no choice, but to bring the wolf back, right? Otherwise my wolf would eat my mouse

  • So... I bring the wolf back...

  • and then, well, I'm kind of stuck, right? So either I bring one of these guys.

  • But then my wolf would eat the two remaining guys.

  • Or I bring the wolf again, and I keep going like this, and I'm stuck.

  • Okay--

  • Brady Haran: Minimum vertix cover doesn't work.

  • It doesn't work. It doesn't work.

  • So how much do you need how much bigger does it have to be?

  • And the amazing thing is, you just need one more! at

  • Whatever the graph of conflicts is

  • You will only need at most one more than your minimum vertex cover. And so the way to do it, is very simple

  • You have these

  • conflictual things that, you know, like, like your wolf here.

  • So you just put all these conflictual indivi-- individuals in the boat with you at all times.

  • So you can watch them, and then one by one you carry everything else. So here

  • Okay, my minimum...

  • Brady Haran: So the wolf does every trip?

  • Yeah the wolf is with you the whole time. It does every trip back and forth.

  • So, now let's say that I have the minimum

  • vertex cover plus 1 seat extra, so I have 2 seats plus a farmer's seat. So I'll take my

  • wolf in my mouse first,

  • I'll leave the mouse there, bring back my wolf, take, now my goose with my wall leave my goose.

  • Come back with my wolf. Take my goat in my wolf.

  • But my go there, come back with my wolf,

  • and then carry finally the last 8. And this will work no matter how big your vertex cover is, right?

  • So, no matter how big it is you just keep it with you in your boat, and then one by one you carry everything else.

  • That's pretty amazing, so you know that you need at least a minimum vertex cover,

  • and you need at most the minimum vertex cover plus one to be able to do it.

  • And the amazing thing is that distinguishing between both,

  • knowing one you need one and not the other, is actually really hard. It's NP-hard. So this is a recent result by

  • three Mathematicians:

  • Csobra , Woegunger and Hurkens.

  • And Yes, it's an amazing thing, this small difference of one

  • is hard to determine.

  • Brady Haran: So sometimes minimum vertex cover will do the trick.

  • Yeah, just like in the previous example.

  • Yeah.

  • Sometimes you need to go plus, one and to know which is which, just by looking at the graph.

  • It's hard. So for certain classes of graphs we do know it, but for a general graph, we don't. And it's very hard.

  • Hard problem, actually if you can solve it so you'll not be a millionaire. So you know.

  • Something to try at home.

  • Brady Haran: What's this problem ?

  • So this is the alkene number of the graph?

  • But so it relates because it's NP-hard to determine whether you need a minimum vertex cover our--

  • the minimum vertex cover plus one, if you were able to come up with a polynomial time algorithm to determine for any graph,

  • what it is. Then you would prove that P is equal to NP.

  • So

  • big problem.

  • This video was brought to you by the

  • Mathematical sciences Research Institute, one of the top places for mathematics in all the world.

  • And whatever you think about the mathematics they do there...

  • they must have the best of you of any maths Institute in the world.

  • San Francisco Bay, Berkeley--

  • unbelievable. If you'd like to find out more about MSRI, I'll put some links in the description under the video. It's worth a look.

I want to tell you about a generalization of a problem

字幕と単語

ワンタップで英和辞典検索 単語をクリックすると、意味が表示されます

B1 中級

川の渡り(とアルクインナンバーズ) - Numberphile (River Crossings (and Alcuin Numbers) - Numberphile)

  • 1 0
    林宜悉 に公開 2021 年 01 月 14 日
動画の中の単語