Is it possible? Simple questions, not so simple solutions

this video is sponsored by curiosity stream holding over 2,500 documentaries and nonfiction titles for curious minds is it possible to connect these 9 dots assuming the rules are one you must use for straight line segments and 2 you cannot take your pencil off the paper this is probably one of the most famous connect the dots puzzles that people rarely get at first if at all they'll try things like this which doesn't work because you missed the one in the middle or they'll try this which also doesn't work they'll conclude it must be impossible and then they're surprised to find it is possible with this configuration here it just involves some out-of-the-box thinking no pun intended or here's another puzzle is it possible to cover this entire 10 by 10 grid with 4 by 1 tiles assume you can only place the tiles vertically or horizontally and there can't be any overlap or anything like that now you could just start trying combinations but again try to look at this in a different way if we were to write down the number 1 on the top corner and then twos down the first diagonal then threes fours once again twos and so on we can find something interesting no matter where you put the tile assuming only vertical horizontal orientations it will cover the numbers 1 2 3 & 4 every time since there are a hundred squares here that means we need twenty-five tiles to cover everything those 25 ones 25 to 25 3 s and 25 fours would need to be covered but if we count everything up there's not 25 of each number for example there are 26 to s and that would require 26 tiles which would be too much to fit on the screen thus the original problem is impossible see for some of these problems use it to take on a new perspective all of the questions are simple and the math isn't that advanced solutions to these aren't always obvious so let's see another example imagine a classroom of 25 students arranged in a 5x5 grid where each student occupies a single one of these spaces it has a quick definition I need to add that two students are adjacent if they share an edge as in diagonals do not count as adjacent so these two students are adjacent since they share an edge and goes for these two but these two are not there just agonal now let's say some of these students become infected with a disease and on top of this every minute the disease spreads according to the following two rules one if you're already infected you'll remain infected and two if your adjacent to at least two infected students you become infected as well that means in the next minute this person will become infected since they were adjacent to two infected students sharing both those edges same goes for this person here since they're adjacent to three infected people and here all the rest by the way I'm just writing the subscript two here to visually show you like this is the next round of people who got infected so we don't lose track it doesn't mean anything else though then after another minute the same thing would happen now all these students would become infected after another round these x4 squares will become infected and eventually everyone becomes infected so here comes the math problem the question is for this five by five grid is it possible to start with four or fewer infected students and get to a point where the entire class aka every square is infected if you want to give this some thought pause the video now because I'm just going to say the answer and that is no this is impossible but the tough part is to prove why this is actually question three from problem set two of an MIT course called mathematics for computer science which by the way is really interesting class that's available totally for free online like textbook lectures and everything included so I'll link that below for those who are interested but anyway the question as stated is actually more general than what I said it asks for a proof that for any n by n grid if fewer than n students are initially infected then the whole class will never be completely infected I'm just going more specific for simplicity now even though this question is found here in a college-level math class the underlying math is extremely simplistic just not obvious at first so let's go back again I'll deal with a five by five board and the goal is to show that if we start with four infected students or fewer that the entire class will never become infected as with several math questions that seem tough at first sometimes it can be helpful just play around with it like let's see what happens here first these students become infected as they're all adjacent to at least two already infected students then next these students become infected and lastly this one does but that's it all these other squares are adjacent to only one infected student like this one here shares only one of those edges and thus the disease does not spread to them in this case it looks like we couldn't quite get the boundaries so okay let's try again but use these four spots instead now the first round leads to these students being infected followed by these and then one more remains and the ends here still we can't get everyone in fact you'll notice that even if we were to start with more than five infected students like this right here that may not lead to the entire class being infected but that's not our goal so in order to figure this out we'll start with this grid and the first thing we're going to do is count how many edges border a single infected student like this edge borders a single infected student and same with all these four around them and the same applies to this one here and all these around the perimeter we don't count this one for example because it borders two infected students so right now we've highlighted twelve edges and that will be considered the boundary or perimeter of the infected region the thing to know is that if everyone becomes infected then the boundary would have to have a length of 20 so now let's see how the boundary evolves if two infected students are jacent to a healthy one then the boundary length is not going to change right now the boundary has the length of eight then after the student gets infected we remove these two edges but add one to the top and one to the bottom thus keeping the total number of edges at eight same goes for the situation here right now the perimeter is eight and after the spread the perimeter is still eight nothing changes with the preneur length when two infected students are adjacent to a healthy one but what about three infected students surrounding a healthy one well in this case the perimeter is twelve to begin once that middle student becomes infected we would remove three of the edges and add in one so the perimeter goes to ten meaning it decreased by two now I know these two students become infected as well but those squares are only adjacent to two infected students each which as we just saw doesn't change anything as then when we create the new boundary it will still have a length of 10 it decreased by 2 but that only happened cuz of this student here becoming infected and lastly what if four infected students border a healthy one well now the perimeter starts at 16 and after the spread these four edges in the middle just go away decreasing the perimeter by four again yes these ones become infected as well but due to what we've already discussed the overall boundary still goes down by four remaining at 12 due to that one student in the middle so we can finally put this all together if a healthy person is adjacent to two infected people the perimeter does not change if adjacent to three infected students the perimeter goes down by two and have adjacent to four infected students the perimeter goes down by four as we can see the perimeter cannot go up so when four people start out as infected the perimeter is that most sixteen and it could be less but for everyone to be infected the perimeter would need to go to twenty that's that we need to increase which we just saw is impossible what we just found was an invariance or something that doesn't change the system evolves and in math sometimes finding that invariant can be the toughest part compared that's like an introductory physics class we're often told the thing that stays constant like momentum is conserved or energy is conserved or to analyze the system overall with that information in this case it can be harder to find the thing that stays constant but once you do it allows you to really understand how the system will evolve over time because we know what's not changing now this next puzzle doesn't involve an invariant in the same way that the last one did but it does require you to analyze the system for what may or may not change as a system evolves in this game we're going to try to catch a thief imagine a network of cities connected as shown where someone has just stolen some money from a bank in this city you are located here I've been assigned to catch the person but the rule is you have to take turns moving and you can only move along one edge at a time same goes for them if you have to move first the question is is it possible to catch the thief well if you try it kind of seems impossible if you move up they could move down and this cycle could continue which of course leads nowhere you could chase in a circle which does nothing and even if you guys venture out to other cities it seems like there's no way for you to land in the same city as them at the same time but in fact there is a way to catch them and the secret lies in this city here first thing we can do with this network is label all the nodes either red or blue so it's that any two connected cities have different colors the only exception is this city here which cannot be blue or red otherwise it would connect to its own color so we'll leave that one neutral now when we start to chase both players are on the same color but when you have to make a move you have to change to the other color and this will always be the case thus you can't catch them because you'll always land on a different color and thus a different City which is why the chase seems pointless but this city here changes that because now after you go by it your next move will land you on the same color as the thief it seems strange but that neutral City is like a portal you go through that completely flips the state of the game to one you can win and now since you'll always land on their color you can just kind of pin them into a corner which forces them to make a move that allows you to capture them now on this topic of graph theory let's see another puzzle that's pretty famous let's say there's a house that consists of five rooms plus an outside area now on every single wall there's a door linking the two adjacent rooms and yes outside counts as a room meaning there are sixteen doors in total now assume that when you walk through a door it closes behind you and you can never reopen it the question is simple can you close every single door assuming you can start wherever you want and yes the only way to close the door by the way is walking through it again this would be a pretty tough question to just brute force so we got to find some way to cleverly represent the system now I'm just gonna get to the answer pause if you don't want to know it but the answer is no you cannot walk through every door as you can see in this example we still have two open that we just can't get to now the reason this is impossible to do is directly related to why we cannot draw this shape without taking our pencil off the paper or going over the same edge twice you can try it if you want but it is impossible to do and we'll see why to understand this let's first start by trying to draw the shape if I start with a vertex and draw an edge to make another one we find that both vertices are of course connected to one edge thus they both have a degree of one now if we keep going and make another edge then this vertex here now has a degree of two while the others have a degree of one if we had another edge then two nodes have a degree of two while the others are one if we connect back to an already made vertex then these are the degrees notice that in every case two of the degrees are odd and the rest are even and on top of that the odd degrees are at the first node we started with and the one we end at this happens because when you trace to a new node it will have a degree of one automatically but then when you leave it it will have a degree of two for those two edges so these all come in even pairs the only exception is this last node since you haven't left it yet and the first one because you only left it so far however it's when you connect to the starting node that everything will have an even degree but once you keep drawing you get those two odd degrees again at the starting and ending points all the rest are even this is all that can happen notice my attempt to draw the shape on the Left failed because now I can't connect these vertices with this edge since I left my pencil here and I can't pick it up or retrace over an already made edge so in general in order to draw a shape again without taking your pencil off the paper or going over the same edge twice either every vertex must have an even degree or exactly two vertices have an odd degree while the rest are even but in the second case you must start and end at the two nodes with odd degrees and this is all assuming the graph is connected by the way so this explains why that shape on the left is impossible to draw on the way that we want since these are the degree values of each vertex we see there's more than two odd degrees which goes against both of these rules at the bottom now going back to the original problem what we can do is treat all the rooms as nodes and this includes outdoors being one node then the doors can be thought of as edges that connect them like you can see here so the question of can I walk through every door is the same as saying can I draw this shape without going over the same edge twice and without taking my pencil off the paper and you'll note that going over the same edge twice would be like going through a door twice which isn't allowed and taking your pencil off the paper would be like teleporting which we can't do but anyway if we find the degree of each node these come out to be the values and since there's more than two odd degrees then this is impossible to draw given our conditions thus no you cannot walk through every single door if you want another challenge though we can add a twist where we introduce a hole in this room that connects to the outside area as in now you can go from that room to outside or vice versa whenever you want although you still have to close all the doors now is this possible to do the answer to this one is yes and here's why if I start in the room on the top left and walk to the right we close that door which if you look at the graph above is like removing that edge and being faced with a totally new puzzle were those degrees that were each five go down to four so now we see there are exactly two notes with an odd degree so our goal is possible if we were starting in one of those rooms with the odd degree remember that second rule from before but since we're not we still have an issue however now we can walk through the top door which closes it and removes that edge from the graph above then we're able to go through the hole back into the top room which doesn't change the graph at all now the graph has exactly two odd degree nodes but we're starting at one of them meaning there is a solution and it will for sure have us end in this room here with the degree of five and I'll just have them trace out the path where you will see that is exactly what happens so really we found that this five room puzzle cannot be accomplished on a flat plane but it can be accomplished on a torus or donut because the hole in the middle would be in one room and that would be a link to the outside area which this website has a good graphic showing now in that last example we were most concerned about the degree of each node but now I'm going to make a graph where we keep track of how many nodes or vertices and edges there are like here we have two vertices and a single edge that connects them with the next trace that adds one node and one edge to the graph and same with the next but once we connect the two already existing nodes we add one edge but now we also add a face which I'll add a column for and something to realize here is that in every case the vertices minus edges plus faces is always 1 however if we were to call this outer section of face as well and that increases the number of faces and every case by one changing the total to two this relationship of vertices minus edges plus faces is one of the most famous invariants in mathematics known as Euler's characteristic some mathematicians put this near the top of their list of the most beautiful equations out there due to its simplicity but also it's surprising applications so instead of just trying to throw in one example of this video I'm gonna do an entire dedicated one just for that but for those who want to continue learning about math science technology and more I recommend checking out curiosity stream the sponsor of today's video curiosity stream is a streaming service that hosts thousands of documentaries and nonfiction titles spanning history physics and the universe technology nature and plenty more if you want to learn more about groundbreaking physics and the search for a theory of everything they have series like the ultimate formula that will take you through the discovery of the Higgs boson all the way to our understanding of what happens at the center of a black hole or they have series just on illusions that I'll explain why our brains don't always see things for what they truly are curiosity shame is an extremely affordable streaming service but only $2.99 a month they'll satisfy anyone with a strong desire to learn explore and just understand the world and universe around us the service is available on a variety of platforms worldwide including Roku Android Xbox one Amazon fire Apple TV and more then if you go to curiosity stream comm slash major prep or click the link below and use the promo code major prep you'll get your first month's membership completely free this gives you unlimited access to top documentaries a nonfiction series I know many of you will find very interesting so again links are below and with that I'm going to end that video there if you guys enjoyed be sure to LIKE and subscribe don't forget to follow me on Twitter and join the major Facebook for updates on everything hit the bell if you're not being notified and I'll see you all in the next video

Channel: Zach Star

Views: 2,019,273

Keywords: majorprep, major prep, is it possible, math puzzles, math questions, challenging math questions, simple math questions, math solutions, graph theory, mit course, cops and robbers, connect the dots, impossible puzzle, impossible, proofs, mathematics, applied mathematics, five room puzzle

Id: PbJaOaXthhk

Length: 18min 17sec (1097 seconds)

Published: Wed Sep 04 2019