What is discrete math?

Now, before I go talking about how impactful discrete math is, it is important to understand what it is. And believe me, I know that in CS and mathematics, just like in business, there tends to be a certain lingo that might be intimidating. So I understand that people might take one look at 'discrete' mathematics and immediately shy away because it sounds like a really tough topic.

In reality, it's pretty tough, but, by no means is it as hard as it sounds. If you're a logical thinker and you like solving puzzles, and breaking down problems, I think you can catch on pretty quickly. So... What is discrete math?

Defined by Brilliant.org, discrete mathematics is the study of mathematical structures that are countable or otherwise distinct and separable.

Pretty broad right? I'll get into a specific problem in a second, but, first, let me explain why discrete math is so important.

Thinking like a mathematician

The one thing that I have seen improve after studying discrete mathematics is something that I never knew was so important: thinking mathematically.

What does that mean?

Simply put: When I approach a problem (in a real world or an academic setting), I look to strip an overlying issue down to its fundamental issues, and look for patterns or emerging structures that can be applied to the larger issue at hand.

This is a lot easier said than done, and it truly is a skill that can be improved upon - and by no means am I saying that I am some expert mathematician either. However, I am extremely excited about improving upon this skill.

Now, I get that what I said might be really confusing but, for now, just understand that my approach to problem solving is different and is a new skill that I look to improve upon.

Perhaps, an example will help.

The friendship problem

The following problem is one that I was asked in class, and, I think, is an incredible example of discrete math, mathematical thinking, and mathematical applications at work:

*You create a general AI (artificial intelligence) and want to teach him “friendship” as a relation on a set of people. You define some rules for this friendship relation.

These are your four laws of robotic friendships:

1. “Everyone is friend of him or herself”.
2. “Not everyone is friend with everyone”.
3. “The enemy of my enemy is my friend” (here “enemy” just means “not friend”).
4. “The enemy of my friend is my enemy.”

Draw a directed graph for the defined “friendship” relation on a set of five people.*

So, essentially, what this problem is asking us to do is to create a graph where all of the above rules are satisfied with 5 people.

Now, let's say we have a person called Alice and a person called Bob, in our graph we can show that Alice is a friend of Bob by drawing an arrow from Alice to Bob. If Bob is also friends with Alice, then Bob has an arrow pointing at Alice. Pretty simple right?

Let's take a look at this picture and see it in action:

So, we see that Alice is a friend of herself, Bob is a friend of himself, and Alice and Bob are friends of each other. Awesome!

Now, let's ask.. does this graph satisfy all the rules? Let's see.

No - The second rule is broken, everyone in the graph (Alice and Bob) is friends with everyone (Alice and Bob are friends with each other.)

Ok, now I think you're prepared to attack the problem, try and make a graph that works for 5 people and follows all the rules!

The solution

So, as you might've seen this is a pretty difficult problem. We can use mathematical thinking here to figure it out - but there's a catch.

Just trying to attack the problem head on would be pretty tough as you would have to try and make all these rules fit in a set of 5 people. The four rules would sneak up on you real quick and you would think that you found a solution - just to find that everyone is friends with everyone. Believe me - I tried!

So, this problem is too complex to just solve head on. Now, thinking mathematically, you might think to take the smallest set of people - say two - and see if there is a pattern that we could apply to a set of 5 people.

This is a great thought and we should pursue it, however - and here's where the catch is - the puzzle is not possible to solve on a set of two people.

So, when I was doing this problem, I was sitting there thinking to myself that this problem is impossible. It's too hard to workout on a large scale and seems to break down in the smallest scales as well (sounds kinda like the theory of relativity right? hahaha).

Eventually, I decided to take a shot at it with a set of 3 people and I found that if two people are friends with each other and one person is only a friend of themselves, then the relationship is satisfied. And then I saw that this pattern can be applied to the rest of the puzzle. In a set of 3 or more people, the puzzle can be satisfied as long as one person is only a friend with themselves, and the rest are friends with everyone else.

The solution:

What this means

So, this problem is a prime example of improving upon my mathematical thinking. Before this problem I only knew to strip down a problem and find a pattern to apply to rest of the puzzle. However, as we saw, this problem breaks down at the smallest levels so that method doesn't work.

So what did I learn?

I learned that sometimes problems are too complex to be solved at large scales, and break down at the smallest scales, so you need to 'work up from the bottom' and find the first situation where a pattern emerges and see if that applies to the overall issue.

And just like that - a new tool was added to my mathematical mind. All thanks to discrete math.

That's why discrete math is awesome.

• Richard Buehling