Become a Creator today!Start creating today - Share your story with the world!
Start for free
00:00:00
00:00:01
35: Please Be Discrete (Discrete Math)
712 Plays6 years ago
Centuries ago, there began something of a curiosity between mathematicians that didn't really amount to much but some interesting thoughts and cool mathematical theorems. This form of math had to do with strictly integer quantities; theorems about whole numbers. Things started to change in the 19th century with some breakthroughs in decrypting intelligence through examining the frequency of letters. In the fervor that followed to increase the security of existing avenues of communication, and to speed up the newfound media of telegraphy, came a field of mathematics called discrete math. It is now an essential part of our world today, with technologies such as online banking being essentially impossible without it. So what have we learned from discrete math? What are some essential methods used within it? And how is it applied today?
Recommended
Transcript
Origins and Historical Insights of Discrete Math
00:00:00
Speaker
Centuries ago, there began something of a curiosity between mathematicians that didn't really amount to much, but some interesting thoughts and some cool mathematical theorems. This form of math had to do with strictly integer quantities, theorems about whole numbers. Things started to change in the 19th century with some breakthroughs in decrypting intelligence through examining the frequency of letters.
00:00:21
Speaker
In the fervor that led to the increase of security, of existing avenues of communication, and to speed up the newfound media of telegraphy, came a field of mathematics called discrete math. It is now an essential part of our world today, with technologies such as online banking being essentially impossible without it. So what have we learned from discrete math? What are some essential methods used within it? And how is it applied today? All this and more on this episode of Breaking Math.
Introduction to the Episode 'Please Be Discrete'
00:00:46
Speaker
Episode 35, please be discrete.
00:00:54
Speaker
I'm Jonathan. And I'm Gabriel. And this is, how do we start the show? And this is, I don't know. Ask our listeners. Listeners, if you want us to start the show differently. All right.
Programming and the Practicality of Discrete Math
00:01:07
Speaker
We're doing an episode on discrete math today, which is a topic. It's one of my favorite topics because I'm a programmer. I have to use it all the time.
00:01:15
Speaker
Any thoughts on discrete math? Yes, definitely. Actually, as we were talking about doing this topic, the first thought that came to mind is why do discrete math? You mentioned something during the introduction that I think is interesting. You had said that the field of discrete math came out more or less from some curiosities. I'm very curious about more on that. Even if there wasn't a practical purpose at the time, what can you tell us from your research about where this field first started and what were the influences?
Exploration of Mathematical Theorems and Equations
00:01:42
Speaker
Well, it goes all the way back to Euclid and in the Diophantine equations of Diophantes, I think. I'm less familiar. Who is Diophantes? Let me look him up. So Diophantes, he was called, apparently, according to Wikipedia, the father of algebra. So Diophantes, he had these equations that were polynomial equations. So you have like x squared plus y squared equals z squared. But
00:02:10
Speaker
If you have X squared plus Y squared equals Z squared, it usually describes the right triangle, right? And that right triangle can be any configuration. So if you have like 10, 11, you could figure out the other edge and so forth. Awesome. But what's interesting about, um, diaphragm equation is that it restricts it to just, uh, Pythagorean triples, which is like a three, four, five triangles where you have exact integer solutions, which are much harder to solve.
00:02:38
Speaker
Interesting. The reason why I brought that up is I'm always curious about with the relationship between mathematics and nature and other sciences, we've said this before that there will be a curious discovery that will have no practical application and then years down the road it will have an application. So many things fit in that category and obviously this whole episode is about discrete math.
00:02:59
Speaker
That's something that fascinates me. So it's almost like curiosity for its own sake. And that only becomes apparent for people like, I'm sorry, I'm going to slaughter the pronunciation. Say it again. I think Founties or something. Okay, so with respect to discrete math, obviously, you know,
00:03:19
Speaker
We credit him with being the founder of discrete math, but I think the definition is in the name itself, discrete math. It's math that focuses on the countable. So that kind of excludes some fields, obviously calculus, mathematics of the infinities.
Interrelation of Discrete Math and Geometry
00:03:36
Speaker
I think it's less concerned perhaps with geometry as a whole. Well, not really.
00:03:43
Speaker
The discrete math and geometry have a huge amount to do with one another. In fact, one of the big discoveries of the last 30 years was Andrew Wiles' discovery of a proof of Fermat's Last Theorem, which we'll talk about when we talk more about diaphragm equations later in the episode.
00:04:02
Speaker
Yeah. Now, obviously, it's huge nowadays because of computing and digital technologies. All of that is nothing but what can be modeled through discrete integers, ones and zeros. All of that is discrete math. Even the real numbers, the way that they're represented in a computer, it uses a finite number of bits, so it's just an approximation to the real numbers. Basically, our whole world right now is digital and
00:04:29
Speaker
So it's cool that we did some work on this before the digital revolution. So I'm trying to think of other applications before the digital revolution, before computers, before electric computers that strictly involved discrete math. Like if you go to ancient China, I imagine some of their board games perhaps.
00:04:46
Speaker
Well, they did a lot of research on discrete math. In fact, there's this theorem called the Chinese Remainder Theorem that we're going to be talking about. It was discovered by the Chinese mathematician Sun Zi in some book called Sun Zi Swan Jing. I don't know how to pronounce that. Again, again, for those who have a better pronunciation, if you can correct us, we would be very gracious. So why don't we talk about some of the things that we'll be talking about on this particular episode?
Tools and Principles in Discrete Math
00:05:10
Speaker
Sure, we'll be talking about the Euclidean algorithm for finding the least common denominator of two numbers, which is one of the first algorithms ever to be invented. Then we're going to talk a little bit about diaphragm equations, why they're hard to solve, and the differences between working with integers and real quantities.
00:05:28
Speaker
Then we're going to be talking about modulus and the Puritan hole principle just to kind of show you some of the tools that discrete mathematicians use. Finally, we're going to end with the exponential modulus and how it relates to RSA cryptography.
00:05:41
Speaker
Very good. Yeah, and I've heard of some of those. In my experience as a math teacher, we'd go into modulus also in my limited experiences as a programmer. I know programmers will be much more familiar with the term modulus, but for non-programmers, we look forward to giving a great explanation of what it is, also the applications of a modulus in math involving. Spoiler alert, it just means remainder. Indeed, indeed.
00:06:05
Speaker
All right, so Euclidean algorithm is really cool. What do you know about this? OK, so let's do a quick Euclid. We've talked about him many, many times. We know that he wrote the elements, that he is the father, father, grandfather. He's basically considered the person who brought mathematical proofs and geometry. He popularized it. He was the first person to create the book elements that we are aware of.
00:06:34
Speaker
So yeah, he definitely graded it. Okay. Yeah. Yeah. Yeah. And I'm curious who inspired him, you know, that's always a continuing argument, but he is the founder of a 2D geometry as we know it. And also some theorems about discrete math. One of the cool ones that we just do real quick is the proof that there's an infinite amount of primes. And this is when Euclid's proofs.
00:06:58
Speaker
Fascinating. I'm less familiar with it. No, I've read about it, but I'm less familiar with it. So basically, let's say you have all the primes like two, three, five, and let's pretend you had a finite number of primes, right? If you had a finite number of primes, you could multiply them all together, right? Yes. And if you did that and then added one, it would be divisible by none of the numbers.
00:07:17
Speaker
Oh, that's fascinating. So it's a new prime. I love that. I love that. So that's a very quick proof that you can just explain. I've seen a Facebook group called Mathematical Proofs with Pictures, and hopefully we did a good job of mathematical proofs with just audio. That's fantastic.
00:07:39
Speaker
So yeah, I'll say it again. So you've got a group of primes, assume that you have all the primes. And then you said you multiply all of them together and then add one. And then that, uh, that's a new, is it a new prime or? Yeah, that would be a new prime because none of the primes so far, uh, would divisible by it as indistinguishable proof of an infinite primes. Cause like think about two, we can, it's not divisible by two anymore because now it's odd. It's not divisible by three anymore because it's three times something plus one. So there, et cetera. Wow.
00:08:09
Speaker
Now, I assume that that's related to some of Euclid's other ideas, like I know on our outline here we've
Modern Applications of Ancient Math
00:08:14
Speaker
got his algorithm for finding the least common denominator of two numbers. Yeah, and that one's really cool because it's still used in RSA cryptography today. Wow. So that term, for those who may not have had a great experience growing up with math, LCD, the last time you probably heard that was in middle school math, perhaps, or pre-algebra.
00:08:34
Speaker
And it's not always fun. It might be a routine task, but it has a lot of applications. As you said, Jonathan, it's for what was it? The what kind of cryptography? RSA cryptography is one of the steps, one of the many steps. But what's cool about this, I think, is kind of unfair that they don't teach you this algorithm in like elementary school because it's really easy. All you do is you take your two prime. So let's say you want to find the least common denominator of, let's say, twenty five and ten. OK.
00:09:03
Speaker
So you divide 25 by 10, and what do you get? 2.5? Yeah, so 2 remainder 5, right? Yes. So then what you do is you throw away the 25, you put the 10 in the box, and you put the 5 on the outside. So you divide 10 by 5. OK. 2? Remain to 0, right? Yes. So therefore, 5 is the least common denominator, because it was the last thing we divided by. Oh, cool. So basically, it's identifying something as a remainder, and then using that as your LCD.
00:09:32
Speaker
Yeah. It's like, uh, so, so it's like you take the, uh, remainder and you keep putting that, you keep dividing by the remainder and you keep dividing what you were dividing by, by with the remainder. That's fine. You know what? It's just in terms of mental math. So during our, our first season, we, we, we talked a lot about all the episodes that we could do. And in our planning, we even talked about the idea of doing a mental math episode. We never did. It's a fantastic idea.
00:09:57
Speaker
You know, we could actually have people send us emails or letters hint hint or or even call us. Do we have a phone number? No, we don't. We are too poor to have a phone number, right? Oh, yeah. No, it's getting we get folks contact us any way that they can, you know, breaking math podcast at Gmail dot com and send us your mental math ideas, things that you may have heard about through the grapevine or, you know, other great mental math techniques. I think that is one way to really garner an appreciation for mathematics and something I wish we all had more of.
00:10:25
Speaker
Oh yeah. And you could find us too on Twitter at breaking math pod. Yeah. Yeah. Send us your mental math. We'll do a whole episode on it and you will get credit. You'll get a shout out. But yeah, so that's, that's Euclid's contributions to discrete math. Um, those are all of them. I don't think they were, but, uh, yeah, they, let's continue. So our next section is on diophantine equations.
00:10:48
Speaker
Oh yeah. And, um, those are like, uh, we talked about him in the introduction a little bit, uh, things like finding, uh, X squared plus Y squared equals Z squared, you know, like three, four, five triangles. Yeah. I think one of the characteristics of them is that they are harder to find. They're hard equations to solve involving integer quantities. Essentially that that's kind of a description of them.
00:11:08
Speaker
Yeah, like, and one of the famous ones is Fermat's Last Theorem. Fermat's Last Theorem, he came up with it in 1637, and he basically said that if you have x to the n, so x multiplied by itself n times plus y to the n equals z to the n, it's impossible to solve for n greater than or equal to 3.
00:11:27
Speaker
That's right. And his last theorem, apparently he proved it in, according to him, he proved it in the margins or rather he said he did the proof, but it couldn't fit in the margins of a book. Is that right? Yeah. We have the quote here in Latin and in English.
00:11:43
Speaker
Kubum outem en duos kubos, out quadro quadratum en duos quadro quadratos, et guenarliter nulam en infinitum utra quadratum, potestatum en duos eus dem, no minis fas est dibirire quius, rei demonstrationem, mirabilem, sane, the taxi, hank marganilis, exiguitas, non caperet.
00:12:08
Speaker
It is impossible to separate a cube into two cubes or a fourth power into two fourth powers, or in general, any power higher than the second into two like powers. I have discovered a truly marvelous proof of this, which this margin is too narrow to contain. That is, is that what we call nowadays as trolling? I don't think it's trolling. I think he was just kind of full of himself. A lot of mathematicians are.
00:12:33
Speaker
Now, now. Okay. So, so, so are you, are we saying it's, it's possible that he didn't actually write the proofs? Because I mean, a proof that beautiful, you would think he would have kept track of it. Oh yeah, definitely. He was probably like, he thought he did it. And then he won. And when you went to, I've done this before when I thought, I think I solve a homework problem. And then I'm like,
00:12:49
Speaker
Go to write it down. It's like this is not a solution at all. This is just so so at one point we talked about Doing a show on Facebook called talking heads where we do like little comics of the old mathematicians We actually talked about doing a format talking head where he do a Twitter where I basically says I've discovered a marvelous proof But the proof will not fit in this tweet or something like that. Oh, yeah
00:13:11
Speaker
And his lack of proof was sustained for 357 years until 1994, not 1991, as I said earlier. It was solved by Andrew Wiles using elliptic curves, which I have only begun to understand. Oh, wow. What can you tell us about elliptic curves so far for those of us who have not done any research into them? Basically, they're equations of the form. I think they're like
00:13:35
Speaker
It's like x cubed plus x y squared z. I think they're like cubic or less curves Usually set up like polynomials. I'm kind of I'm put on the spot. Like I barely started looking these up. Okay. Interesting Yeah, I'd be really curious to dive more dive more into this and hopefully get some more of a grasp of how this proof did it How how big was the proof that finally how long was wilds proof? It was like 200 pages Oh Wow, and did he do it all by hand? Did he have the help of a computer? Oh
00:14:04
Speaker
Um, he, I think he did. I think it's a by hand proof. Um, I mean, 200 pages is definitely a very long proof. And, uh, there's, uh, one point where he made a mistake, um, and he had to redo a chapter and reprove it a different way. So that's always, it's always interesting that mathematics can be done like that. Wow. Yeah. That's, that's, that's dramatic where you're so close to a solution and then, you know, have to redo all of it. It's, it's, you know, uh,
00:14:28
Speaker
Well, he only had to redo one chapter that was only link that was wait week Wow now one other question then after after he did this and again I realized this is as simple as me looking it up But how soon after he submitted the proof was it accepted? I'm not sure. I mean, I think 1994 was kind of like the date of acceptance I think everything is kind of like that, but I don't really know
00:14:50
Speaker
Well, I don't know publication standards. That makes me think that there's certainly a lot of murky things where you have something where you may have approved, but you don't know yet. And you think that mathematics could potentially be infinitely complex. So just from that angle, there's things that we will never know just because it's in the span of a human lifetime, you'll never get that far. Oh yeah, for sure. That's actually, you know what, there's actually a really good blog. We've talked about it before. It's the Star Codex. What was it called again? I don't remember. I will find out real quick.
00:15:21
Speaker
Star Slate Codex. There's a blog on the very popular Star Slate Codex that is all about the absolute limits of human knowledge and it's a fantastic blog. They essentially talk about people who spend their entire life researching and then you've got other people who spend their entire life teaching people to research so that they can hopefully, you know, do it better
00:15:43
Speaker
And there's only so many improvements that you can make that there's this asymptotic limit, it seems, to human knowledge. It's a really great read. If you haven't had a chance, I would suggest go check out Star Slate or Slate Star Codex. So one of the tools that you use a lot in discrete math is modulus, which is just remainder. So 7 modulus 3 would be what?
00:16:09
Speaker
Oh, okay. So, so, so one, right? Cause yeah. And the way that you could say that is seven is equivalent to one modulo three. And I don't know why that's the notation, but that's what everybody settled on. And it really annoys me. I think it should just, it should just be like in a computer programming. You use it, usually use a percent sign. And to me, that makes more sense to keep it as an operator, but that's just my own personal politics.
00:16:32
Speaker
So that's what Immodula does. And I know that this became a thing I just said earlier with ancient Greek mathematicians. Oh, ancient Chinese do. Oh, really? Yeah, there's this thing that you can actually do with modulus called the Chinese Remainder Theorem. Okay.
00:16:48
Speaker
And so let's say I give you a certain number of coins and you have a jar that each holds a certain number. Like let's say each jar holds three coins and you put these coins into these jars and you have two coins left over.
00:17:04
Speaker
Now you do another one, but with the coins where the jars hold five coins and you have three left over. And if you do it with seven, then you have two left over. And with the Chinese remainder theorem, it is possible to reconstruct the original number, which is 23 different coins.
00:17:19
Speaker
Oh, okay. Interesting. Wow. This is fascinating. So I'm actually very curious. This is an area, again, this is probably more history than it is math, but you certainly inspire me to suddenly research parallel developments in ancient China and other parts of the world. I think China was kind of unparalleled in number theory. Unparalleled, huh? Yeah. The Chinese and the ancient Indian mathematicians were really good at that. Fascinating. Fascinating.
00:17:45
Speaker
So what's older, the mathematics that you're quoting or the mathematics of Euclid? I think Euclid was a little earlier. And then obviously with respect to one culture influencing the other, a lot of the things that were in China, India and Greece were fairly independent. Is that right? I'm not sure. I think there's a lot of debate about how much cross pollination there was through trade.
00:18:06
Speaker
Yeah. Yeah. I also know that there's a lot of things that are ascribed to things like Archimedes that were actually could be described possibly as ancient Egyptian. Again, I am not an expert in this area, so I could be completely wrong on this one. But it is an interesting topic to talk about the actual origins of things, you know, or it could be like where Rome conquered ancient Greece and just took their ideas and renamed them.
00:18:29
Speaker
Oh yeah, and there's also, yeah, there's a lot of factors. But what's cool about the Chinese remainder theorem is that it's used to this day in RSA cryptography. It's used to solve a problem which we'll be talking about in a second where, let's say, actually we could just do this now. Let's say I wanted you to multiply 9 by itself a hundred times. So 9 to the hundredth power. Yes.
00:18:51
Speaker
And tell me the last digit of that real quick. Oh, wow. Okay. I've got no idea. I mean, I have to, I mean, nine's a funky number. It's one of my favorite numbers. Well, here's the thing to notice. Yes. Nine to the 100, nine to the 100th is nine squared to the 50th, right? Yes.
00:19:07
Speaker
nine squared is 81. Okay. The last digit of 81 is the last digit of any number is that number modulo 10, you divide by 10 and take the remainder. Oh, wow. So, and the cool thing about modulo is that like, like 12 times 13.
00:19:24
Speaker
12 times 13 is going to be 6 modulo 10 because 12 is 2 and 13 is 3. So you can multiply with modulo. That's, you could do a lot of like arithmetic with modulo. You could add and subtract. You just have to keep track of it on both sides. Wow. So essentially what you're saying is this comes down to a mathematical do-si-do. Basically. Like it's a, it's a barnyard dance, but with numbers and you end up with like, you know, grab your partner, swing around and you end up with like, you know, the last number. Yeah, definitely.
00:19:53
Speaker
And, and that's actually a pretty good analogy because, uh, because nine squared is 81. So last digit is one and what's one multiplied by itself? 50 times one. Yeah. So the last digit of nine to the 100th is one. Oh wow. Okay. Odd man out. Interesting. Okay. Very cool. Very cool. And you could do the same thing with like, and with a lot of numbers and that's actually why the, um, and you could.
00:20:14
Speaker
I want you to solve this at home. If you have a number and you add up the digits, and you keep adding up the digits until you have one digit left, if that digit is divisible by three, then the original number was two. And you can figure that out using Modulo.
00:20:27
Speaker
Fascinating. Wow. That's right. We are now assigning our breaking metal listeners math homework Yes You can't listen to breaking math unless you do the math homework in future episodes we're gonna have to submit it by email We're gonna have to grade it if you get an A you get to listen to the whole episode Sorry guys, if you get a B you listen to 45 minutes if you get a C you get half an hour
00:20:53
Speaker
Oh, gosh, dude, we're going to lose our listeners so fast. You know, because I think a business practice, the worst thing, the worst thing to do is to tell someone what they have to do. So raise your customers. Yes. Oh, boy, that that's not a great business practice here. So how are you going to keep that in? Are you going to edit that out? No. Oh, man. OK.
00:21:13
Speaker
Yeah, now the whole idea that I said earlier is I was trying to imagine this whole modulus do-si-do thing is bringing me back to our episode on Math Factory where we're talking about our favorite algorithms in general. Essentially, that's what it is. You've got a problem to solve and you've got all these different algorithms that basically are kind of a song and a dance where you end up with something. That's the brilliance of mathematics and that's the brilliance of algorithms.
00:21:37
Speaker
And sometimes I feel like it does have the same feeling as dancing, at least certain types of dancing, like definitely the do-si-do type of dancing, because it's about steps. You have quantized steps in discrete math versus like infinitesimal calculus is a different story.
00:21:53
Speaker
Yeah, you've got like um, you know, you talk about like things that are understandable with respect to information theory Well, there's a pattern and what you just described that dose you do with mathematical systems That's you know, it's very easy to describe how it works and it always produces an end result, you know Um, so it's exactly like a dance. Uh, it's wow. That's that's cool. That's cool
00:22:16
Speaker
Yeah. And the cool thing about like modulo is the way that I visualize it in my head is a ring of like of beads. So like, you know, like a hundred modulo seven is just, you just, you have a ring with seven beads on it and you just go around it until you pass a hundred beads.
Foundational Role of Math Across Cultures
00:22:34
Speaker
Pervert example of discrete math using beads is, you know, counting. In fact, that all brings you back to math, you know, how it began with calendars and counting and all that stuff.
00:22:42
Speaker
Yeah, it's very earthy math in my opinion. It's like you can't get away from math, man. No matter what you do, you could try to run away and get away from it all, but you never ever will. Math always finds you. And sometimes you find math or math finds you. That's mystical. Mystical math. That'd be a good episode, wouldn't it?
00:23:02
Speaker
Yeah, I would. But we could do Tesla. But one cool thing about the exponential modulus is that it's used in RSA cryptography. And the way it's calculated is actually, we can't go into it because it's really complicated. Well, not really complicated, but we don't have time to really go into it. But it's used in the Chinese, it uses the Chinese remainder theorem. But you could use exponential modulus the same way. And so like, let's say I have something that encrypted with my public key.
00:23:31
Speaker
That's to say, if I have a public key, just a quick rundown of that, I can use it to, anybody can use it to encrypt messages, but only I can use my private key to decrypt them, right? Yes. So usually you have a cipher text into, into make cipher text in RSA. You take the message, you take it to the exponent of the public key, which is usually a few hundred bits. And then you divide that and then you take that modulo N.
00:24:00
Speaker
And it's just a pre-agreed upon number. So there's a lot of terminology here and I understand that our audience, our listeners right now who have computer science and math backgrounds, they're probably following right along. But for those who are listening in the background who may not have any background whatsoever, how would we say just what you said using just pure analogies? I think one possible way of doing it. You mentioned cipher. A cipher is a way of decoding something.
00:24:26
Speaker
Yeah. And also, okay. So like what's, um, when you, when you multiply something by itself, modulo N, essentially what you're doing is you're just kind of scrambling the number over and over again. Okay. Um, it's kind of a way of scrambling the number and you can actually create some really cool diagrams. If you had some information, you know, an order of something, um, um, you could scramble it like, gosh, I'm, I'm trying to think of some example involving like baskets or, or like a lottery spinner or something. You know what I mean? Like, um,
00:24:52
Speaker
Yeah, it's kind of like that, but where it's predictable every single time. And so anyway, you just scramble it by multiplying it by itself. If you followed the algorithm to the letter, you'd have to keep doing this for literally more time than the universes existed, multiplying it by itself over and over and over again. Because these are like hundreds of binary digits long. These are gigantic numbers that we're dealing with.
00:25:18
Speaker
but we can actually but there's a trick is that we multiply by itself over and over again and like the reason why this is as fast as two times two is four times two is what eight times two is 16 times two is 32 so in five steps we got to 32 but two squared is four four squared is 16 16 squared is i 256 and 256 squared is a very big number and in five steps we've gotten to like a way big number
00:25:45
Speaker
And so that's why the squaring trick works. We just square and multiply it by itself. Real quick question. This is something I should have asked you earlier. You said the name of this encryption is R. I'm sorry, what is it? RSA. RSA. What does RSA stand for?
00:25:58
Speaker
It stands for the three inventors of the algorithm, Ron Rivest, Avi Shamir, and Leonardo Adelman. Okay, and when did they come up with this way? 1978. There's an equivalent system that was developed in 1973 by an English mathematician, but it wasn't RSA, but that wasn't declassified until 1997.
00:26:15
Speaker
Interesting. Okay. And then, wow, wow. Okay. Huh. And, uh, yeah, so these require like, to like four kilobits of information, uh, to basically scramble everything up. And so, so basically, so when you take your message, raise it to the exponent of, uh, the public key and take it modulo N, you're just scrambling up that information. But what's cool is that to de-scramble it, you use the same algorithm, but you,
00:26:43
Speaker
but the exponent is even bigger. It's your private key. Interesting. Okay. Okay.
Cryptography Concepts Explained with Analogies
00:26:48
Speaker
Public key, private key. And I'm trying to think of like, what are some other analogies for the whole public key, private key thing? Uh, like a mailbox or like a good way to think of it is like, let's say I want to, I want you to send me a, uh, uh, something secure. So I give you a, uh, I give you a box that is pre-locked that you put messages in. That's like encrypting it with my public key.
00:27:12
Speaker
And then when the box gets back to me, I have my key in my pocket and that's opening it up with my private key. Got it. Got it. Okay. Okay.
Pigeonhole Principle and its Applications
00:27:20
Speaker
One of the last things I think we're going to talk about is the pigeonhole principle. And it's a really simple principle. And it's like, if you have more pigeons and you have pigeonholes, then there's at least one pigeonhole with more than one pigeon. And that's, that's how simple it is.
00:27:35
Speaker
Oh, yeah, yeah, yeah. Sorry, I was visualizing that for me. Yeah, because it's a remainder problem. You gotta stick two pigeons, at least two, in at least one of the holes. And there's an extended pigeonhole principle which says that if you have like three times as many pigeons as pigeonholes, then there's at least one pigeonhole with at least three pigeons. Oh, wow, that's interesting. Yeah, it's one of those things where I feel like I'd have to count it out to start to convince me of that.
00:27:59
Speaker
Yeah, or at least four. I mean, and three, the way reason why is because like, let's say you have like 10 pigeons and three pigeonholes. You put three pigeons in each hole and then you have one left over. So you have to have one pigeon hole with at least four pigeons. Okay. Okay. Got it. And, uh, if you, but in, in the, it still holds. If you have, uh, one pigeon and pigeon hole, one, one pigeon pigeon hole two, and then eight pigeons and pigeon hole three, cause that's at least three and at least one. Interesting.
00:28:28
Speaker
And it's cool because you could use this to prove that there's at least two people in England with the exact same number of hairs on their head. And the way that you could do that is this. So there's about a million, and this is a fact, there's about a million, or no more than like a million,
00:28:45
Speaker
uh, hairs on the head, even like generously, whatever. Okay. Which means that there's about a million pigeonholes, uh, the people with one hair on their head, two hairs on their head, all the way to a million hairs on their head. Okay. And if there's more than a million people in England, which it's true, it means that there's at least two people with the same number of hairs on their head.
00:29:05
Speaker
Oh, got it. In fact, because let me see how many people are in England. Oh, that's crazy. That's so simple. It's deceptive, dude, deceptive mathematics. How about a whole podcast called that?
00:29:18
Speaker
And there's about 66 million people in England, which means that there's at least 67 people walking around with the same number of hairs on their head. That's extremely convincing. Fascinating. And it relates to the birthday paradox too. And this shows the difference between probability and the pigeonhole principle. Because if you have 23 people in a room, as we've covered, I think on the podcast before, there's at least a 50% chance that two people will have the same birthday.
00:29:42
Speaker
That's great. So in this case, if we talk about this in terms of the pigeonhole principle, you know, of course there are, if you're not counting leap year, there's 365.25, whatever, days in a year. Let's just round to 365. Okay. So yeah, for the sake of this discussion, then we'll just say 365. But we're not using the days of the year as pigeonholes, right?
00:30:05
Speaker
Yeah, we are. Okay. And which means that even though there's a 50% chance with 23 for there to be a hundred percent chance that two people have the same birthday, you have to have at least 366 people.
00:30:16
Speaker
Okay. Interesting. Okay. Wow. Wow. And, and then what was the logic of that one again? Like how do you prove so a hundred percent chance you have to have the exact amount of pigeonholes? Oh, you have to have at least as many because there's only a certain amount of birthdays. So at some point you have to start repeating birthdays. So, uh, there, if there's 366 people in a room, there's a hundred percent chance that two of them have the same birthday.
00:30:42
Speaker
And if you want a description of why that's not the case or rather why it's unintuitive that you only need, what was it? 23? 23 for 50%. Yeah, we answered that in our previous episode. I think it was a minisode six, I believe. I think so. Yeah, you could go back and listen to that.
00:31:00
Speaker
That's a, that's a great discussion. Very unintuitive. Are there any more applications of the pigeonhole principle? Cause I mean, like we did some of them, but like, um, I mean, there's like, it's just used all the time in like little proofs. Um, it's, it's a tool, you know, it's a tool to be used all the time.
00:31:17
Speaker
And it's just useful because like, like, let's say you have, uh, people shaking hands in together. Uh, you can prove that at least two people shook the same number of hands. Um, use it using a hand, using the number of handshakes as pigeonholes. So it's like, if you make more abstract pigeonholes and you can prove cooler things. Okay. Very cool.
00:31:38
Speaker
Discrete mathematics has shaped the way in which we relate to the world through the process of not only digitization, but encryption through digitization. As we continue on to the sister episode to this one, which will be about mental and recreational mathematics, let us remember that our world today is defined by sharp definitions in between numbers.
00:31:56
Speaker
I'm Jonathan. And I'm Gabriel. And this has been Breaking Math. Uh, if you want a poster, where can you get that? Oh, if you go to our Patreon and that is www.patreon.com slash breaking math, not breaking math podcast, just breaking math. Yeah. And, uh, you can find us on Twitter at breaking math pod. You could find us on a Gmail at breaking math podcast. And, uh, yeah, I think that's all I have.
00:32:22
Speaker
Yeah, I have a few things. First, I want to say the posters are now shipping much, much faster. We were with the revenues from our original, not to get too into details, but with the revenues from the first posters, we were able to finally order a medium sized bulk order. So we've got a whole bunch of them. So this is right in time for Christmas. So until we run out of this amount, which is, I think it's four times our original order. Yeah. Okay. We're hoping that this, I'm sure it'll last.
00:32:50
Speaker
But they're shipping much, much faster now. So from the day you order it, assuming that the day you order it is the day that I go down to the UPS store and mail it, in the United States, it's arriving in probably three days, three or four days. That's it.
00:33:05
Speaker
And aside from that, we mentioned earlier, please send us your favorite mental math. We love talking about it. That's great discussion. That gets us excited. And if you want to send us your favorite mental math or your favorite recreational math, we will make sure to include it. Well, I can't say that for sure. It's a guarantee that I can't. We'll think about it. We'll think about it. If you're not terrible.
00:33:28
Speaker
Please send us your stuff. Talk to us about your favorite math games and your favorite mental math. It'll be a great discussion next time. I know we joked about it earlier in the episode, but we actually are going to move to a grading-based subscription format.
00:33:43
Speaker
Yeah. Oh, and lastly, if you guys want to follow me, I'm actually going to start making YouTube videos that reflect on podcasting in general. I've been listening a lot to almost everything from Gimlet Studios. They're an inspiration in terms of how they created the company.
00:34:00
Speaker
Not everything they've done has been well received by the audience, but I've been obsessed by Gimlet, especially the podcast startup. I'm just plugging it because I am. I'm going to start making YouTube, I'm sorry, Facebook videos that I release where I talk about my favorite podcast as well as what I want to do with breaking math. So if you'd like to feel free to friend me on Facebook, just go to Gabrielle Hesh and you'll see a few of those. That's also another way to interact with me. So yeah.