River Crossings (and Alcuin Numbers) – Numberphile

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.

100 thoughts on “River Crossings (and Alcuin Numbers) – Numberphile

  1. Why does American English conflate "bring" and "take"? Bring/take is like come/go, learn/teach and borrow/lend. "Bring that to me" v "Take that to him". You wouldn't say "Take that to me" or "Bring that to him".

  2. Poor Old Noah – He would need some boat as he had two of everything and no place to land and no cabbages. So here is the real point – if cabbages weren't saved from the flood by Noah, how is it we have cabbages?

  3. …holy crap, I found this video from the video featuring Charlie Turner, and I'm legit creeped out by the resemblance… I was sure this was her.

  4. I loved my NP-Completeness class for my last class of my Bachelor's Degree 🙂

  5. The real problem with this problem is that you need an entire spot on the boat for a mouse

  6. ur math is so flawed.

    what wolf doesn't want to eat a delicious cat?

  7. With 1 Wolf & 4 Goats, you wouldn't necessarily have to "take the wolf on every trip." You could: 1) Take the Wolf & return empty. 2) Take 2 Goats & return with the Wolf. 3) Take 2 remaining Goats & return empty. 4) Take the Wolf, again. Unfortunately, this requires the same number of trips. So, it's not as clever as I'd initially hoped.

  8. total possible connections – open connections (non-connections) = minimum vertex cover?

  9. Tie the goose to the boat and get an extra seat, train the wolf to swim and get another seat, put the rabbit and mouse in the same cage to save a seat, And now it's a LOT simpler. Think smarter, not harder, right?

  10. How about just doing "What has the most conflicts?" over and over until you've covered them all?

  11. And another thing is cabbage is so light you can just put it on your lap while you row!

  12. (The number of lines minus the number of points) minus 1 is equal to the lowest possible number of boat spaces

  13. Why can’t the farmer just pay the cabbage (broccoli) to a bridge architect. I mean, he can always eat the goat or wolf.

  14. I feel sorry for the wolf,  he's always the problem.  Blame the carrot, he feels nothing.

  15. Interesting question: What happens when you add something like say a sheep dog into the mix which will protect the goat from the wolf but will eat say the cat?

  16. I mean Goats will eat anything. Given the chance I don't think anything is safe from it.

  17. Now I wonder if you can calculate how many trios is the minimal amount of trips

  18. Do you really lack funding to the point of faking cabbage with broccoli?

  19. I'd really like a follow-up video that dug into how you DO check if a vertex cover is the minimum size

  20. If the problem can always be solved with a boat of minimum_vertex_cover + 1 places, why put in all the effort to try to save 1 place? Be a sport and just go with the bigger boat.

  21. the distinction between minimum vertex cover and minimum vertex cover + 1 cases seems simple enough. We must simply determine if any part of the minimum vertex cover is connected to more than one vertex outside the minimum cover. if so, it is a minimum vertex cover + 1 case, else minimum vertex cover case.

  22. That farmer must be very tough if he can stop all of these animals from reacting for interacting when he is nearby. 👁👁

  23. Would simply removing vertices of highest degree recursively not lead to a vertex cover?

  24. im sure im jumping the gun here. but cats eat rabbits… and would totally try to eat geese too….

  25. How about you feed all your livestock before going to the river so they don’t eat your produce… and also DON’T KEEP A WOLF AROUND. Seems way simpler 😂

  26. The last picture with 17 things in it includes a fish. In order to solve that problem, you must assume the fish cannot swim.

  27. Really cool stuff behind an apparently easy problem. Plus, I love how mathematicians write so neatly on thoes big paper sheets.

  28. i made business cards that read "Anglo-Saxon really smart dude" now. No regrets.

  29. there is a (maybe simpler) solution to the wolf + 4 others version.

    first you bring the wolf over

    then you go back alone

    you bring over two of the smaller animals

    and bring back the wolf

    take the other two small animals over

    and go back alone to finally

    bring the wolf over

    and you're done

  30. Why is that farmer in a business of transporting wolves?! Does he run a wolf farm?

  31. Alright, the goat stands at the top of the N-entagram… all lines are red, there is blood and of course it was all unintended :). I get it.

  32. 8:20 extrascary picture of living velociraptor's descendant

  33. when i see a rabbit in my yard, they're eating the grass in my lawn.

  34. 0'54"`
    Why don't Americans understand the difference between 'take' and 'bring'?
    I note some other Latin languages struggle with this concept.

  35. How can someone become a millionaire by solving this problem? The moment you published it, it is everyone's or common property.

  36. Exclusive number graphs. You can throw in numbers and find the graph. Relational database clutter graphs.

  37. I'd known the 3 item problem since I was about 10… I've never been so sure that a REALLY hungry wolf wouldn't eat the broccoli (or cabbage)

  38. 15:57 If that gray mess is the "best view", I'm comfortable behind my computer screen, thanks.

  39. I wanted to hear about a situation where say you couldn’t bring a wolf and a goat together on the same boat

  40. Conjecture: Define a measure for the nodes to belong to a vertex cover as: number of loops they are part of plus number edges they have. Remove the node that has the highest measure from the graph by zeroing the row and column that belongs to this node in the incidence matrix. Repeat the process until the rank of the incidence matrix is zero. This will give the minimum vertex cover. Measure = diag(a*a) + a*ones(nodecount,1), where a is the incidence matrix.

  41. I'd not come across of "NP hard" before today. My guess was that "NP" is cool mathematician slang for "very", but after looking it up I now know I was mistaken. However, I'm convinced "HP hard" would work well as slang for "very difficult" and much better (and way cooler) than the "incredibly challenging" one hears so often on the BBC these days.

Leave a Reply

Your email address will not be published. Required fields are marked *