Real Mathematics – Graphs #7

Serkan’s System

Serkan the math teacher, hands out a specific number of problems to his students. Kids who can solve 1 or more of those problems would get a certain prize. At the beginning of each semester, Serkan and his students sit down and agree on what kind of prize is going to be distributed. For the current semester, oreo is chosen as the prize:

If Serkan the math teacher hands out 10 problems:

  • 10 Oreos for the kids who solved 10, 9 or 8 of those problems,
  • 5 Oreos for the kids who solved 7, 6 or 5 of those problems,
  • 2 Oreos for the kids who solved 4, 3 or 2 of those problems,
  • 1 oreo for the kids who solved 1 problem,
  • Absolutely nothing for the students who solved… well… none of those problems.

If you take a careful look at the numbers, you can see that Serkan the math teacher selected those numbers with a kind of logic: 10, 5, 2 and 1.

These are the natural numbers that can divide the number of the problems (that is 10) without any remainder.

Prize Distribution Machine (P.D.M.)

One month later…

Serkan the math teacher had faced some problems 4 weeks into the semester. He realized that it took hours to distribute the prizes since he has 10 classes in total.

Serkan the math teacher had to use almost all his free time in school to distribute the Oreos. This led him to think about a machine that would help him with the distribution:

  • P.D.M. will have 4 different compartments. (Because of 10, 5, 2 and 1.)
  • The volumes of those compartments will be measured with Oreos. They will be 10, 5, 2 and 1 Oreo-sized.
  • Oreos will enter the machine from the 10-Oreo-sized compartment. From there, Oreos will move to the other compartments using the connections that will be established.
  • Golden Rule: To establish a connection between any two compartments, the size of those compartments must be factors of one another.

Connections of the compartments for 10 problems:

  • For 10-Oreo-sized: 5, 2 and 1.
  • For 5-Oreo-sized: 10 and 1.
  • For 2-Oreo-sized: 10 and 1.
  • For 1-Oreo-sized: 10, 5, and 2.

Then, the sketch of the P.D.M. would look like the following:

Is this another graph?!

If you are familiar with graph theory (or if you read the graph section of the blog) you can recognize that the sketch of Serkan the math teacher’s machine is a planar graph:

You should connect the numbers (dots) using lines (connections) according to the golden rule.

One wonders…

What if Serkan the math teacher asks 12 problems?

For 12 problems, the numbers of prizes are going to be: 12, 6, 4, 3, 2 and 1.

In such a situation, can Serkan build his machine? In other words; is it possible to connect the dots for 12-sized P.D.M.?

Hint: First, you should consider where the lines should be. Also, you can arrange the dots in any order you’d like.

M. Serkan Kalaycıoğlu

Real Mathematics – Algorithm #7

How to fail your math test algorithm (H.T.F.Y.M.T.A.)

The late 90s…

At last, there is a computer at home. Now a new battle emerged between Steve and his brothers: “whose turn it is for the computer?”. Thanks to his high grades at school, Steve won this battle easily. After his victory, Steve started to crush zombies in Carmageddon, won the Champions League in Fifa 98, and did such things in Duke Nukem which I can only tell you face to face over a cup of latte.

Steve’s computer game madness went berserk after he met with a football simulation game called Championship Manager. On top of all these games, at least a few days a week, Steve continued to play football&basketball with his friends. A disaster was waiting for him at the end of this road. How didn’t he foresee this?! He was about to fail all his tests in school!

The first warning was the math test. There was less than a day left for the test. Steve should have studied, but he developed some habits since he had a computer. Now, instead of studying, he had a various number of chances to waste time:

1.Staying at home

When Steve decided to stay home, he would get stuck to his computer. Anyone can guess that he was not using his pc for his school. He was just playing one of the following games:
a. Fifa
b. Carmageddon
c. Championship Manager

2.Going out

Whenever Steve went out, he was not going to the library to study:

a. Chase any ball (football or basketball)
b. Behave like a bum with your friends (a.k.a. meet with your friends and do absolutely nothing productive)

Graph of H.T.F.Y.M.T.A.

In the previous posts, I mentioned what graphs are and how they can be useful in certain situations. In Steve’s situation, using graphs can be very helpful to understand what is going on. Since Steve chooses not to study for his math test, his decisions will lead him to fail the test:

What does the graph tell us?

In the graph above, lines represent Steve’s choices, and dots represent at what state he is in after his choices. The graph tells us two certain things: Steve decides not to study and eventually he fails the math test.

This is why the lines that show Steve’s choices have directions.

During making choices, some steps cannot be skipped. For example, in order to play Fifa, Steve first should sit beside his computer, and to do that, he first should decide to stay home.

Let’s assume that Steve’s choices are like the following:

Stay home -> Turn on the pc -> Play Fifa.

In such a situation, since Steve has limited time before the test, he cannot play Fifa and then return and study for the test. After his decisions, there is no other country than “fail-town”.

Another thing the graph tells us is that Steve cannot go back after making a decision. Mathematicians call these kinds of graphs as “acyclic/chain digraphs”.


Some Information

Acyclic Digraphs

An acyclic digraph does not have a cycle. In other words, once you start moving on an acyclic digraph, you can never go back to the point you previously were at.

An acyclic (finite) digraph has at least one “source” and at least one “sink”.

A point is called “source” if it has no lines leading into it from any other point(s). A point is called “sink” if there are no edges from that point to any other point(s). In the graph of Steve, “don’t study” is the source, and “Result: F for fail” is the sink.


One wonders…

We all use acyclic digraphs during our daily lives. To show an example, I will use Steve’s life once again.

Every school day, Steve takes a shower as soon as he wakes up and gets ready for school. His steps are more or less like the following:

Wake up

Get into the shower

Brush teeth after shower

Get dressed

(Steve’s school uniform consists of pants, shirt, tie, and a vest.)

Q: Draw the graph that shows the way Steve gets ready for school.

Ps. After the shower, Steve must complete his tasks in the right direction. For example, he cannot put on his boxer before pants, can he?!

M. Serkan Kalaycıoğlu

Real Mathematics – What are the chances?! #8

Hooligans

This year’s cup final will be between two arc-rivals of the country; it is both a final and a derby game. Supporters of both sides are waiting anxiously for the game. Though, Steve has no interest in this game. His team was eliminated in the semi-finals.

Two of Steve’s close friends, Jack and Patrick, have been arguing over the final for the past two weeks. Jack thinks his team FC Ravens will be the winner as Patrick thinks his team AC Bolognese will be victorious. Meanwhile, Steve is thinking about what to eat at supper.

Jack

“We haven’t lost to them in years. The cup is 90% ours. But, this is football; anything is possible. Well, that makes 10% anyway. Yeah, I am pretty sure of my team. If you want, let’s bet on it!”

Patrick

“We are the best team of the season. Plus, our striker scored 69 goals in 27 games. The cup is 75% ours. But, we have been unlucky against them. Which is why I am giving them 25%. Steve, I can bet on it right this second!”

Smart Steve

Steve is aware of the fact that either of these teams will be victorious as this is a cup final and there is no chance for a tie.

He would like to take advantage of his friends’ blindness. Steve would like to set such conditions for the bets such that he would profit whatever the result is.

What would you do if you were in Steve’s situation?

M. Serkan Kalaycıoğlu

Real Mathematics – Strange Worlds #17

Topology On Your Head

Often you see me writing about changing our perspective. For example, when you encounter a baby first thing you do is to make baby sounds and try to make the baby laugh. Whereas if you’d looked carefully at baby’s hair, you could have seen a very valuable mathematical knowledge hidden on the baby’s head:

As shown above, there is a point on each baby’s head. You can see that the hair besides that point is growing in different directions. Can you tell me which direction the hair grows at that exact point?

Hairy ball theorem can give us the answer.

Hairy Ball Theorem

Hairy ball theorem asks you to comb a hairy ball towards a specific direction. The theorem states that there is always at least one point (or one hair) that doesn’t move into that direction.

You can try yourself and see it: Each time at least one hair stands high. This hair (or point) is a sort of singularity. That hair is too stubborn to bend.

Baby’s hair is some kind of a hairy ball example. (I use the expression “some kind of”because the hairy ball has hair all over its surface. Though the baby’s head is not covered with hair completely.) This is why the point on the baby’s head is a singularity. It is the hair that gives a cowlick no matter how hard you comb the baby’s hair.

Torus

Hairy ball theorem doesn’t work on a torus that is covered with hair. In other words, it is possible to comb the hair on a torus towards a single direction.

No Wind

Hairy ball theorem can be used in meteorology. The theorem states that there is a point on earth where there is no wind whatsoever.

To prove that, you can use a hairy ball. Let’s assume that there is wind all over the earth from east to west. If you comb the ball like that, you will realize that north and south poles will have no wind at all.

On Maps

The hairy ball theorem is a kind of a fixed point theorem. Actually, it is also proven by L. E. J. Brouwer in 1912.

One of the real-life examples of the fixed point theorem uses maps. For example, print the map of the country you live in, and place it on the ground:

You could use a smaller map though.

There is a point on the printed map that is exactly the same as the map’s geographical location.

“You are here” maps in malls or bus stops can be seen as an example of this fact.

One wonders…

Assume that all the objects below are covered with hair. Which one(s) can be combed towards the same direction at all its points? Why is that?

M. Serkan Kalaycıoğlu

Real Mathematics – Strange Worlds #16

The Walk

  • Select two points in the classroom.
  • Draw a line between them.
  • Send a student to one of those points.
  • Once the student starts his/her walk, he/she should arrive at the other point exactly 10 seconds later.
  • Everybody in the classroom would count to 10 to help the walker.
    Ask the student to do the same walk twice while recording the walk using a camera.

The goal of the experiment

After the experiment is done, the following question is asked to the classroom:
“Is there a moment during both walks when the student stands at the exact point?”
In other words, the student walks the same distance in the same amount of time at different speeds. The goal is to find if there is a moment in both walks when the student passes the exact point on the line.
First of all, we should give time to the students for them to think and brainstorm on the problem. Then, using the video shots, the answer is given.
The most important question comes at last: Why so?

Weeding out the stone

In my childhood, one of my duties involved weeding out the stones inside a pile of rice. To be honest, I loved weeding out. Because I was having fun with the rice as I was making different shapes with it.

Years later when I was an undergrad mathematics student I heard of a theorem that made me think of my weed out days. This theorem stated that after I finish the weed out, there should be at least one rice particle that sits in the exact point where it was before the weed out started. (Assuming that the rice particles are covering the surface completely.) In other words; no matter how hard to stir the rice particles, there should be at least one rice particle that has the exact spot where it was before stirring.

This astonishing situation was explained by a Dutch mathematician named L.E.J. Brouwer. Brouwer’s fixed point theorem is a topology subject and it is known as one of the most important theorems in mathematics.

The answer to the walking problem,

The walking problem is an example of Brouwer’s fixed point theorem. This is why the answer to the question is “yes”: There is a moment in both walks when the student stands at the exact point on the line.

I will be talking about Brouwer’s fixed point in the next article.

One wonders…

A man leaves his home at 08:00 and arrives at another city at 14:00. Next morning at 08:00 he leaves that city and arrives at his home at 14:00, using the exact roads.

Conditions

  • Starting and finishing points are the same, as well as the time intervals of both trips.
  • The first condition means that the man could travel in his choice of speed as long as he sticks to the first condition.

Is there a point on these trips where the man passes at the exact time during both trips?

Hint: You could assume that the distance is 600 km and the man must finish that in 6 hours. For instance, he could have been traveling 100 km/h the first day, and the next day 80 km/h in the first 2 hours; 100 km/h in the next 2 hours, and 120 km/h in the last 2 hours of the trip.

M. Serkan Kalaycıoğlu

Real MATHEMATICS – Geometry #20

Escape From Alcatraz

Imagine a classroom that has 5 meters between its walls in length. Tie a 6-meter long rope between these walls. Let the rope be 2 cm high off the ground. Since the rope strained to its limits, its 1-meter long part hangs from either side of the rope.

The ultimate goal is to escape from the classroom from under this rope, without touching the rope.

Rules

  • Escape should be from the middle point of the rope.
  • One should use the extra part of the rope to extend it.
  • One of the students will help you during the escape. He/she will strain the rope for you so that you can avoid touching the rope.
  • Each student has exactly one try for his/her escape.

Winning Condition: Using the least amount of rope for your escape.

Football Field

Legal-size for a football field is between 90 and 120 meters in length. Assume that we strain a rope on a football field that is 100 meters long. We fixed this rope right in the middle of both goals while the rope is touching the pitch.

The middle of the rope sits right on the starting point of the field. This is also known as the kick-off point.

Let us add 1 meter to the existing rope. Now, the rope sits flexed, not strained, on the field.

Question: If we try to pick the rope up at the kick-off point, how high will the rope go?

Solution

We can express the question also as follows:

“Two ropes which have length 100m and 101m are tied between two points sitting 100m apart from each other. One picks the 101m-long rope up from its middle point. How high the rope can go?”

If we examine the situation carefully, we can realize that there are two equal right-angled triangles in the drawing:

Using Pythagorean Theorem, we can find the length h:

(50,5)2 = 502 + h2

h ≈ 7,089 meters.

Conclusion

Adding only 1 meter to a 100-meter long rope helps the rope to go as high as 7 meters in its middle point. This means that a 1-meter addition could let an 18-wheeler truck pass under the rope with ease.

M. Serkan Kalaycıoğlu

Real MATHEMATICS – Puzzle #4

Naughty Students

Among all friendships, being classmates has a special part. Inside every classroom, each student has a friend who would cause trouble if they sit adjacent (side to side, front-back and diagonal) to each other. This is why teachers change the sitting-order to find the optimal situation for each classroom.

Steve the teacher and his problem

Teacher Steve realizes in one of his classes that in total 8 students cause trouble during lessons whenever they sit adjacent (from now on I will refer to being adjacent as “being neighbor”).

The Situation

  • Neighbor students are the students who sit either side to side, front and back or diagonal to each other.
  • If two students cause trouble whenever they are neighbors, there is a <–> sign between their names.
  • Deniz <–> Ali <–> Kirk <–> Jane <–> Poseidon <–> Rebecca <–> Lucreita <–> Bran
  • Sitting plan for these 8 students is shown in the following:

sekiz

Steve the teacher doesn’t want to change other students’ sitting plan. Hence his problem becomes as follows:

“How can I find an order for these 8 students so that there won’t be neighbor students who will become naughty?”

Hint: Assign numbers to the students.

I will explain the answer in the next post.

 M. Serkan Kalaycıoğlu

Real MATHEMATICS – Strange Worlds #14

In my youth, I would never step outside without my cassette player. Though, I had two knotting problems with my cassette player: the First one was about the cassette itself. Rewinding cassettes was a big issue as sometimes the tape knotted itself. Whenever I was lucky, sticking a pencil would solve the whole problem.

person holding black cassette tape

The second knotting problem was about the headphone. Its cable would get knotted so bad, it would take me 10 minutes to untangle it. Most of the time I would bump into a friend of mine and the whole plan about listening to music would go down the drain.

20190730_143315.jpg

The funny thing is I would get frustrated and chuck the headphone into my bag which would guarantee another frustration for the following day.

A similar tangling thing happens in our body, inside our cells, almost all the time.

DNA: A self-replicating material that is present in nearly all living organisms as the main constituent of chromosomes. It is the carrier of genetic information.

dna_main_001

DNA has a spiral curve shape called “helix”. Inside the cell, the DNA spiral sits at almost 2-meters. Let me give another sight so that you can easily picture this length in your mind: If a cell’s nucleus was at the size of a basketball, the length of the DNA spiral would be up to 200 km!

You know what happens when you chuck one-meter long headphones into your bags. Trying to squeeze a 200 km long spiral into a basketball?! Lord; knots everywhere!

Knot Theory

This chaos itself was the reason why mathematicians got involved with knots. Although, knot-mathematics relationships existed way before DNA researches started. In the 19th century, a Scottish scientist named William Thomson (a.k.a. Lord Kelvin) suggested that all atoms are shaped like knots. Though soon enough Lord Kelvin’s idea was faulted and knot theory was put aside for nearly 100 years. (At the beginning of the 20th century, Kurt Reidemeister’s work was important in knot theory. I will get back to Reidemeister in the next post.)

Is there a difference between knots and mathematical knots?

maxresdefault (4)

For instance the knot we do with our shoelaces is not mathematical. Because both ends of the shoelace are open. Nevertheless a knot is mathematical if only ends are connected.

180px-Example_of_Knots.svg

The left one is a knot, but not mathematically. The one on the right is mathematical though.

Unknot and Trefoil

In the knot theory we call different knots different names with using the number of crosses on the knot. A knot that has zero crossing is called “unknot”, and it looks like a circle:

20190730_135245.jpg
A rubber band is an example of an unknot.

Check out the knots below:

They look different from each other, don’t they? The one on the left has 1 crossing as the one on the right has 2:

lanaa

But, we can use manipulations on the knot without cutting (with turning aside and such) and turn one of the knots look exactly like the other one!

This means that these two knots are equivalent to each other. If you take a good look you will see that they are both unknots. For example, if you push the left side of the left knot, you will get an unknot:

Is there a knot that has 1 crossing but can’t be turned into an unknot?

The answer is: No! In fact, there are no such knots with 2 crossiongs either.

How about 3 crossings?

We call knots that have 3 crossings and that can’t be turned into unknots a “trefoil”.

Blue_Trefoil_Knot
Trefoil knot.

Even though in the first glance you would think that a trefoil could be turned into an unknot, it is in fact impossible to do so. Trefoil is a special knot because (if you don’t count unknot) it has the least number of crossings (3). This is why trefoil is the basis knot for the knot theory.

trefoilandmirror

One of the most important things about trefoils is that their mirror images are different knots. In the picture, knot a and knot b are not equivalent to each other: In other words, they can’t be turned into one another.

Möbius Strip and Trefoil

I talked about Möbius strips and its properties in an old post. Just to summarize what it is; take a strip of paper and tape their ends together. You will get a circle. But if you do it with twisting one of the end 180 degrees, you will get a Möbius band.

Let’s twist one end 3 times:

Then cut from the middle of the strip parallel to its length:

20190730_131333.jpg

We will get a shape like the following:

20190730_134158-1.jpg

After fixing the strip, you can see that it is a trefoil knot:

To be continued…

One wonders…

1. In order to make a trefoil knot out of a paper strip, we twist one end 3 times. Is there a difference between twisting inwards and outwards? Try and observe what you end up with.
2. If you twist the end 5 times instead of 3, what would you get? (Answer is in the next post.)

M. Serkan Kalaycıoğlu

Real MATHEMATICS – Geometry #19

How Much Chocolate?

It is midnight and my stomach is talking to me. I hope to find something to eat in the kitchen and I see a chocolate bar:

20190701_131610

Immediately made myself a cup of coffee and broke a piece of the chocolate bar:

20190701_131715

After I “killed” the broken piece I started having second thoughts about my decision: Oh God; Did I eat too much chocolate?

I placed the leftover on a grid. This way I found where both whole and the broken piece lies on the grid:

çiko1

The broken piece is shaped like a simple polygon. My goal is to calculate the area of that piece. There are several ways I could calculate the area. Although, the first thing comes to my mind is a theorem called “Gauss’ shoelace theorem”.

Gauss’ Shoelace Theorem

The shoelace theorem can only be applied to simple polygons. In order to use the theorem, I have to find where the edges of the simple polygon lie on the grid:

çiko2

Theorem uses these points just like shoelaces. But first we have to define the edges and make a list of them:

çiko3

lak1

 

 

Do not forget to add the first edge to the bottom of the list.

Now you can multiply the numbers diagonally; from right to left and left to right. Then add left to right and subtract it from right to left ones:

This slideshow requires JavaScript.

{(0*0) + (5*1) + (4*3) + (5*3) + (0*0)} – {(0*5) + (0*4) + (1*5) + (3*0) + (3*0)}

{32} – {5}

27.

The area of that simple polygon can be found by dividing the result above:

27/2

13,5

M. Serkan Kalaycıoğlu

Real MATHEMATICS – LIfe vs. Maths #7

Game of H&G

I selected this name for the game as it reminds me of the story of Hansel and Gretel. (If you haven’t already, pretty please with sugar on top, read it!)

In H&G there is only one goal: Finding the shortest path. Though this game is not a board game; you have got to participate physically. You can find the answer if and only if you analyze your experience.

I have to mention it now: We learned this game from bugs, ants in particular. I will get back to that inside the article.

What is H&G? How can you play it?

  • Players walk between two places.
  • Start and finish are the same locations for all players.
  • There is more than one path for the walk.
  • Goal is to find the shortest one among those paths.
  • During the game it is forbidden to use any technological device. Yes, including watches and phones.
  • Only tool allowed is a pen.
  • Each player draws a line every time he/she hits the starting and finishing ends of the path.
  • In order to maintain same (or at least similar) speed for all players, it is forbidden to run.

Game #1

Assume that there are two paths for H&G as follows:

20190425_134042.jpg

In the beginning players on paths A and B walk the same distance. But as walks progress players using the path A arrives to the finishing point way before than the players on path B:

20190425_134109.jpg

When the players on path B arrive to the finishing point, they see a mark that is left from the players who use path A. This means that the path A is shorter than the path B. Most of the players from B would prefer path A for return. Some of them (stubborn ones) would follow B and see that they were behind of everyone else.

After some time everyone chooses the path A.

Game #2

Let’s say that we add obstacle on the path A:

20190425_134136.jpg

After a decent amount of time some of the players will try the path B in order to see if it is the shortest path now:

20190425_134159.jpg
There is a small but significant difference between B and A.

Careful players will realize that the numbers of lines on path B are increasing faster than the path A which would only mean that path B had become the shortest path.

In time all of the players will realize the fact that path B became the shortest path after the obstacle.

Game #3

Let’s add a third path; we’ll call it path C, to the existing game:

20190425_134223.jpg

At least one player will be curious and try the path C. Just like the previous games, within time players will realize that the lines from path C increase faster than the other two. Hence players slowly understand that the path C is the shortest one among those three.

Best H&G Players: Ants

In the beginning I mentioned that ants taught us how to find the shortest paths. Back in 1992 a scientist named Marco Dorigo was researching the behaviors of ants. Dorigo soon discovered that ants choose particular paths from their nests to the food supplies.

Assume the map of a nest and a food supply looks like the following:

20190425_134722.jpg

And assume that ants start using the following path:

20190425_134732.jpg

Pheromone: A chemical secreted by an animal that shapes its social behavior. For instance ants leave this chemical with their footprints which can be traced by other ants.

Ants are in the search of pheromone when they decide their paths between their nest and food supply. If there are more ants on a path, there will be more pheromone. This will cause more ants to use that particular path. Here, pheromones are just like our pen marks:

20190425_134741.jpg

Let’s add an obstacle to the path:

20190425_134803.jpg

At first some of the ants will use the path I as others use the path II:

20190425_134821.jpg

Since path I is shorter than the path II, after some time there will be more pheromone on path I. This is why ants will abondone path II will choose to use path I in the long run:

20190425_134832.jpg

Ant Colony Optimization Algorithm (ACOA)

Modern people are impatient: They need to run their things in the fastest way, in the shortest time. Ant Colony Optimization Algorithms help people a lot for this cause. And this algorithm’s logic comes from the method ants use in order to find the shortest path.

Quicktron-Alibaba-warehouse
A warehouse of Alibaba where robots share a workspace.

For instance ACOA is crucial for robotic moves. Robots imitate ants when they learn how to move from one place to another. If there are a decent number of robots in a workspace, ACOA helps robots to avoid collisions.

M. Serkan Kalaycıoğlu