Here is the riddle again:<\/p>\n
Man 1: 1 minute to cross<\/span> For example, if Man 1 and Man 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Man 4 returns with the flashlight, a total of 20 minutes have passed, and you have failed the mission.<\/span><\/p>\n <\/p>\n General Comment:<\/strong>\u00a0For this riddle, the major lesson is to learn how to carefully enumerate all possibilities. We need to find a good way to search through the space of possible moves, and find the sequence of moves that has the shortest time.<\/p>\n <\/p>\n First Thought:<\/strong>\u00a0How many possible first moves are there? There are four ways to move just one person over (send just 1, just 2, just 5 or just 10), and there are six ways to send two people over (send 1 and 2, send 1 and 5, send 1 and 10, send 2 and 5, or send 5 and 10). \u00a0Can we eliminate any of these possibilities?<\/p>\n <\/p>\n Second Thought:<\/strong>\u00a0It makes no sense to just send one person over, as\u00a0they’d have to return immediately. Thus two people go over in the first move. So our first move is either<\/p>\n (1,2) go over We have to figure out which of these moves we should make, and then who goes back. If (5, 10) go over that costs 10 minutes, and then even if 5 returns that’s still another 5 minutes, for 15 minutes total. A little work shows there is no way to get 1, 2 and 5 over in 2 minutes (we have to get 5 back!). Similarly we see that we can’t send 2 and 10 over together: that costs 10 minutes, and sending 2 back brings our total to 12 minutes. We would then have to get 1, 2 and 5 over in just 5 minutes, and we can’t do that.<\/p>\n We thus must send either (1,2) or (2,5). It seems reasonable to try to send 5 and 10 over together, as they are the slowest. Thus, we might want to try sending (1,2) over as our first move.<\/p>\n <\/p>\n Third Thought:<\/strong>\u00a0For problems like these, it helps to develop a good notation to keep track of who is where and when, and how much time has elapsed. This is a great skill to get — whenever you have a problem, try to distill the key parts of it and come up with a notation that emphasizes what matters. For this problem, we can have four columns. The first will be who is on the left, the next who is moving and in what direction, then who is on the right,\u00a0\u00a0and finally how much total time has elapsed.<\/p>\n Thus if we initially send (5,10) over, then 5 back, then (1,5) over, then 1 back, then (1,2) over we would write:<\/p>\n LEFT \u00a0 \u00a0 \u00a0 \u00a0 \u00a0MOVING \u00a0 \u00a0 RIGHT \u00a0 \u00a0 TIME<\/p>\n 1,2,5,10 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a00<\/p>\n 1,2 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 5,10 –> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a00<\/p>\n 1.2 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a05, 10 \u00a0 \u00a0 \u00a0 \u00a0 10<\/p>\n 1,2 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 <– 5 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 10 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 10<\/p>\n 1,2,5 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a010 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a015<\/p>\n 2 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a01,5 –> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 10 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a015<\/p>\n 2 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a01,5,10 \u00a0 \u00a0 \u00a020<\/p>\n 2 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<– 1 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 5,10 \u00a0 \u00a0 \u00a0 \u00a0 20<\/p>\n 1,2 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a05,10 \u00a0 \u00a0 \u00a0 \u00a0 \u00a021<\/p>\n 1,2 –> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a05,10 \u00a0 \u00a0 \u00a0 \u00a0 21<\/p>\n 1,2,5,10 \u00a023<\/p>\n Obviously this is NOT the solution, but a nice way to write odwn the sequence of moves.<\/p>\n <\/p>\n Fourth Thought:<\/strong>\u00a0We send (1,2) over and we can try sending back either 1 or 2. It turns out both choices work. If we send 1 back, we have (1,5,10) on the left, 2 on the right, and 3 minutes have passed.<\/p>\n <\/p>\n Final Thought:<\/strong>\u00a0The analysis above uses logical deductions to prune the possibilities. There is a way to attack this problem using graphs. What I like about this approach is it introduces us to another powerful technique, graph theory. A graph is a collection of vertices (or nodes) and edges connecting them. For this problem, we write the nodes as (x | y), where x represents the people on the left and y the people on the right. If no one is on a side we represent it by –. Thus our possible nodes are: (1 2 5 10 | — ), (1 2 5 | 10), (1 2 10 | 5), (1 5 10 | 2), (2 5 10 | 1), (1 2 | 5 10), … and so on until we reach (– | 1 2 5 10). We then draw an edge from any vertex to any other if we can go from one to another by a legal move. Thus we can go from (1 2 5 | 10) to (1 | 2 5 10) by sending 2 and 5 over, so we can draw an edge and label it with a 5 (to denote the time elapsed). We can’t move from (1 2 5 | 10) to (1 10 | 2 5) in one move, so there will be no edge connecting these. “All” we need to do is look at all paths from (1 2 5 10 | — ) to ( — | 1 2 5 10) \u00a0and see which takes 17 minutes.<\/p>\n Unfortunately, as we try to construct the graph we realize we need more information. We need to keep track of where the flashlight is, as we can’t send people without a flashlight. Thus (1 2 5 * | 10) means 1 2 5 and the flashlight are on the left and 10 is on the right, while (1 2 5 | 10 *) has the same distribution of people but the flashlight is on the right.<\/p>\n If we use this approach, it will be a long process, but we will get the solution. It’s important to know a method that will work, and then try to find an efficient one!<\/p>\n <\/p>\n Additional Comments:\u00a0The following comment is from my student\u00a0Anand Hemmady:\u00a0<\/strong>If we look at the problem, it is logical that two things are necessary for us to minimize the time spent:<\/p>\n 1) The individuals who take 5 and 10 minutes must only cross once.<\/p>\n 2) The individuals who take 5 and 10 minutes must cross at the same time.<\/p>\n The first of these criteria is easy to implement, but the second one is a little trickier. At first, I wasn’t sure how to go about implementing it, as it isn’t something that I thought of immediately. We must first have the individuals who take 1 and 2 minutes cross. Then, have one of them go back (it doesn’t matter which one, as the other one will also have to go back later). Next, have the individuals who take 5 and 10 minutes cross together. This way, we satisfy both of our criteria above; they only cross once and they cross together. Next, have the individual who remained on the other side come back. Last, have the individuals who take 1 and 2 minutes cross back together.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":" Here is the riddle again: Bridge Over Troubled Students There are four men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at…<\/p>\n","protected":false},"author":2861,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[27],"tags":[],"class_list":["post-745","post","type-post","status-publish","format-standard","hentry","category-restricted"],"acf":[],"_links":{"self":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts\/745","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/users\/2861"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/comments?post=745"}],"version-history":[{"count":2,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts\/745\/revisions"}],"predecessor-version":[{"id":1219,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts\/745\/revisions\/1219"}],"wp:attachment":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/media?parent=745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/categories?post=745"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/tags?post=745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n Man 2: 2 minutes to cross<\/span>
\n Man 3: 5 minutes to cross<\/span>
\n Man 4: 10 minutes to cross<\/span><\/p>\n
\n(1,5) go over
\n(1,10) go over
\n(2,5) go over
\n(2,10) go over
\n(5,10) go over<\/p>\n