[MUSIC] Hello, everybody. Welcome to our open online course on discrete mathematics. I'm Dominik Scheder, I'm an assistant professor here at Shanghai Jiaotong University. And it is my great pleasure and honor to introduce you to this exciting topic. So, this is our first lecture of this course. And I will use it to tell you a little bit what discrete mathematics is, how it differs from other parts of mathematics you might have seen before. And also why we study it. What its applications are. First, instead of giving you an abstract explanation of what discrete mathematics is. I want to show you a concrete example that nicely illustrates certain key concepts. My example is a puzzle that some of you might already know. So in this puzzle we have a board, which is divided into eight times eight squares. Now suppose you take a saw and you saw off two opposing corners. Like here and here. So, now we have this chess board with 64 squares, but two are sawed off, so we have 62 squares. Now we have these domino tiles, and using these domino tiles, we want to cover the whole board. But, of course, every tile must be put on the board orderly, covering exactly two squares. So we could do it like this. We continue and sometimes we have a choice, sometimes we don't. So we can place them vertically and horizontally. And now towards the end, you see we run into a problem and we cannot completely tile the board. So now there are two possibilities. First, maybe we made a mistake. We should go back and do something different. Or it could be that it's simply impossible to cover the whole chess board with domino tiles. Okay how do we find this out? Well, we live in the age of computers. We could program a computer to try all possibilities. And simply exhaustively search for a perfect tiling or tell us that the computer didn't find any. All right, so if we do that, maybe it's a wise thing to think about how long the computer would take to compute this. Computers are fast, but still their speed is finite. So how many possibilities will the computer have to check? Well this is difficult to comput. Let's take some close approximations. Let's put the two corners back in and let's ask ourselves, how many different ways are there to tile the complete chess board? And this is maybe a good approximation to how many things our computer program would have to try out to find a tiling. Okay, so this actually already a great example of discreet math. You have a fairly simple problem. You have a fairly simple question. How many ways are there to tile the chessboard using these domino stones? And these questions can become very difficult pretty quickly. For this question for example, we will not solve in the course, we will solve easier ones. Anyway for now let's cheat a little bit and lets go online and check with Wikipedia. Wikipedia has a page about domino tilings. This is exactly what you want and thankfully it has also has a link to a great website which is called The On-line Encyclopedia of Integer Sequences. So whenever you run over a sequence of natural numbers you think it might have some significance. It is probably in this encyclopedia and it tells you what it is about. So here, we look at it and now we can find out the number of tilings for 8 times 8chess board, it is roughly 13 million. All right, 13 million is a large number. It's certainly too large for us to check all these possibilities. But for a computer it should be kind of okay. For a fast computer it should be okay. But then again, we are mathematicians. We are not only interested in 8 times 6, we are interested in the problem in its generality. We want to understand it. So even if the computer can solve this problem, what about a bigger chess board, 16 times 16? Can the computer iterate all possibilities here? Well, again, let's go to The On-line Encyclopedia of Integer Sequences. And there we also find the number for 16 times 16 and it is this. That's a huge number. It's so huge, I don't even know how to say this number in English. There is a better way to get a feeling how huge this number is. So suppose our computer needs one second. To go through all combinations, to go through all tilings of the eight handed chess board, one second. How long would the some computer program need to go through all tilings of 16 times 16? Many, actual it would take 400,000 times the age of the universe. So you can see here even with very fast computers, this approach of just letting the computer try everything is completely hopeless, so let's not do it. There is only one way that is viable, we have to start thinking. So often in math, if you're faced with a problem it's smart to put a business structure to it. So, for example, here we have this chess board. And as the name actually suggests, if it's a chess board we should color it in black and white. So now we have 32 black squares and 32 white squares. And what happens if we put a tile here? Well the tile covers exactly one white square and a black square, no matter where we put it. So after we have put one tile, we have that many black and white squares. And we go on and on and in the end we have two black squares left and no white square. That means, whatever we do, we always get stuck because there will always be two more black squares then white squares. All right. So now it should be obvious to you, basically obvious to everybody, that this is an explanation why we cannot tile this chunk of chessboard. This little riddle, illustrates something that is very important in math, in discrete math in particular. And that's the notion of a proof. The notion of a proof is central to mathematics, and it's also the whole fun of mathematics. Math without proof is simply boring. So what is a proof? If you go to a lexicon, you look up the definition of a proof, you will probably see something like. A proof is a sequence of mathematical statements where each statement follows from the preceding ones by some agreed upon logical rule. Well, that's true but in real life a proof is something more. A proof is a formal explanation why something is true. Just as I told you here with the black white coloring, it's an explanation that makes it completely clear why this holds, why you cannot tile the chess board. So maybe you have got a little bit feeling how discrete math feels, and how it differs from other parts of mathematics. And I want to elaborate on this a little bit. So here are four areas of mathematics, and many of them were actually motivated by applications from outside math. For example, geometry is one of the oldest parts of mathematics. It's roughly, 2,000 years maybe two or 3,000 years old. And why that people started studying math? So, here for example you see a page from a Chinese book from roughly third century. And as you can see, they probably used geometry to measure distances on land. They wanted to measure their land, they wanted to measure areas of their plot. They needed geometry to build houses. You probably cannot build the pyramids without some knowledge of geometry. How about calculus? This is a much younger subject. So calculus, you remember from high school, it's about functions with real numbers. It's about derivatives, integrals. And it really got going in the 17th, 18th century with Newton and Leibniz. And also they started to study calculus because of some application. So in the case of Newton, he developed calculus because he wanted to understand how objects, physical objects, move. First and foremost, for example, the planets. All the planets move around the sun. And for this, in order to understand this, he needed to develop this new area of mathematics. So out of here, it came from a concrete application. Number theory is a little bit different. It is one of the oldest parts of math, but for 2,000 years it was basically just a beautiful game. Very beautiful one, but without any application. Until in the 70s, two mathematicians, Diffie and Hellman, used some number theoretic concepts to start something that is called public heat topography. So here on the right hand side, you see a scheme how two partners, Ellis and Bob. Can agree upon a common secret, a shared key without ever meeting in private. And to understand how this works, you need to understand some basic number theory, you need to understand prime numbers and so on. So since then, number theory has found a lot of applications, mostly in cryptography. Finally, discrete math. Discrete math really got going in the second half of the 20th century. And the technology that motivated people to study it was, of course, the computer. And why is this? Well, if you think about how the Earth revolves around the sun. It's a continuous motion. That's why we need calculus. On the other hand, computers are not continuous, they move in discrete steps, they do a step then a second step then a third step. So, to understand how computers process information, how information is structured, you need discrete math. And this is why discrete math became big since the second half of the 20th century. All right, so, I want to conclude this session with yet another example from discrete math. It is actually something that we will talk about towards the end of this course. Its called network connectivity. This is one of the most beautiful, in my opinion. One of the most beautiful results in basic discrete math in this course. Here you see a network. You have a start vertex and a target vertex. And this represents something. It could, for example, represent a computer network where you want to route data from the start vertex to the target vertex. It could symbolize a rail network. When you want to route train traffic. It could be a pipeline network. Where you want to wrote oil from the well to the refinery. But, which resource you want route I tell you does not matter. So, lets extract from this and this consider this network. So for example, here I can route goods along the red path, the blue path, and the green path. All right, so note that this node here, we use it twice actually. While that's fine, we just must make sure that every link is used at most once. Because the links have, again, a limited capacity. So, here you see you can route three units of goods, whatever you want to route from the start to the target. This is what I define to be the capacity of a network, it's the maximum number of paths you can find from s to t that don't share any link. Now put yourself in the shoes of a bad guy. Maybe of a guerilla warrior, of a terrorist, I don't know, an adversary who wants to destroy the network. So now suppose we want to disconnect the start from the target. What we could do, we could place four bombs at these crucial links. And if we blow up these links, the network is disconnected. That's what I call the vulnerability. It's the minimum number of edges you have to remove in order to disconnect the start from the target. And if you look at it, it's pretty clear that the capacity is at most a vulnerability. Because every path has to pair through one of these crucial edges. But now look at this example, we can actually move the green path up here, and we make space for another path, an orange path. And now we see, actually that the capacity and the vulnerability both afford for this net worth. And this is not coincidence. There is actually a theorem we are going to prove. Towards the end of this course, it's called the max-flow min-cut theorem, it tells you this identity holds in every network. So, this is the first session we have to talk a little bit about the practicalities of this course. As you might have noticed, it's a video course. So this means you can take advantage of the fact during our video lectures, you can hit pause whenever you want. If I'm going too fast, you can rewind to listen again. If I'm going to prove something, you should hit pause. You should try to think about yourself. You should try to solve it. Maybe you succeed, maybe you fail, it doesn't matter. Then you can go back and then we are going to do the proof together. We also have a textbook, which is this, an Invitation to Discrete Mathematics. We will roughly follow this textbook in this course. But always discrete mathematics, it's a little bit an arbitrary choice of topics, because it's such a big field. And there is no clear order in which one should talk about these fields. So there are several textbooks and I can for now recommend these two. We'll also provide links on our webpage so I highly recommend you to buy at least one of them. And finally, there are exercises, the exercises are really important. In my experience, you cannot learn math without doing it. So really, do it yourself, look at the exercises, try to solve them, do some hard work, invest time in them. It's really helpful. That's basically it for today. As a little goodbye present, I want to give you yet another riddle. That's one of my favorites. In this rhythm, we have four points on the table, and we can move them around. We can take this coin. By the way, this coin is, I think I have one here. This is the one unit coin. That's the base unit of currency in China. So, you can take a coin. You can jump over another coin. And for example, you can take this coin and jump over this, and you land here. You can also take coins that are a little bit further apart, like this. And you land back here. So you can just take a coin, jump over another coin, and you land behind it on the same line at the same distance, but behind it. And now the question is can you just take these four coins in a small square at the beginning? Can you move around so that you end up at some point in a larger square? So try to solve this riddle. If it's too difficult for you, try the same with three coins. So they are in an equilateral triangle. Can you make the equilateral triangle bigger? If it is still too difficult for you, try with two coins. All right, good luck. Have fun with this riddle and I'll see you next time. Thanks. [MUSIC]
