Real Mathematics – Game #13

Crossing the bridge

Years and years ago, there was a village known as Togan. It was located in Mesopotamia’s fertile lands, next to rivers and beautiful waterfalls. There were only a few hundred people who lived in Togan. All of the Togan were farmers, except one: Berkut.

Berkut

Berkut was the oldest man in the village. He had a long white beard. His story had become a kind of a legend within time. According to the people of Togan, whoever entered his property would never be seen again. This is why Berkut’s house was the only house that stayed on the other side of the river of Togan.

Berkut’s home.

For kids, Berkut was a mystery. Whenever Berkut was out on his garden, kids would gather and watch him from the other side of the river.

People of Togan were hardworking farmers. They would be working on their farms starting from their childhood. Like the rest of the Togan, Ali starting helping his family at an early age. Ali would work from sunrise to the sunset.

For Ali and his friends, Berkut’s situation was one of the hot topics. One day, these four friends decided that they would skip working and go across the river to investigate Berkut’s house. This legend had to be questioned!

The next day, while he was out on his garden, Berkut realized that four kids were about to cross the river, using the old bridge. He watched them crossing the bridge in pairs, as the old bridge was not strong enough to carry more than 2 of them at the same time.

He, then, went inside his house as Ali and his friends were approaching the house. When kids were inside the garden, they saw that a jar of cookies and a steamy teapot was waiting for them. While they were checking the table, Berkut went outside and greeted them. Kids, dumbfounded, started screaming as they all dispersed out of the garden in different ways.

They found each other only after it was dark. Now, kids, who had only one lamp with themselves, had to cross the bridge as fast as they can. But they couldn’t risk crossing the old bridge at once. Each time, only two of them could cross the bridge.

Crossing Times:
Jane: 1 minute
Ali: 2 minutes
Tom: 6 minutes
Jenny: 10 minutes

Since they had to cross the bridge in pairs while sharing a lamp, their speed would be at the rate of the slowest of the pair.

Now, you must solve this problem:

What is the fastest route to the other side of the river?

M. Serkan Kalaycıoğlu

Real Mathematics – Numbers #11

A very long time ago in Mesopotamia, a few hundreds of people lived together in the village of Badaks. Badaks were very hard-working people, and they were among the first farmer communities. Their lives depended on two things more than anything: Their farms and sheep.

Monday syndrome in Badaks village…

There was a lot of sheep in the village of Badaks. Thanks to them, people of Badaks were able to protect themselves from cold weather. Their milk and meat were also important to Badaks as food sources. Because of their importance, the person in charge of the sheep had to be wise and trustworthy.

Zaylin a.k.a. the protector of sheep!

Zaylin, head of Badaks, was in charge of this crucial duty.

Every day, with the first sunlight, Zaylin took the sheep out of their pens for them to explore the hills and graze the green grass of the village of Badaks. Before the sun is gone, Zaylin had to gather the sheep and be sure that every sheep returned to the pens.

Omg! Where are the rest of you?!

Even though Badaks were one of the most progressive communities of their time, they didn’t know the use of numbers like the rest of humanity.

At this point, Zaylin had a bit of a problem: How did he know that he returned with the same number of sheep as left in the morning? Don’t get me wrong; Zaylin was an intelligent person for his time. But like everybody else, he didn’t know how to count.

One wonders…

Put yourself in Zaylin’s shoes: Is it possible to detect if you lost any sheep or not when you finish a day without counting or any use of numbers?

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 – 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 – Game #12

Triangle Invasion

Invasion is a multiplayer game which needs only a pencil and a pen. To start the game one should draw a big triangle on a paper whilst assigning the corners with 1-2-3:

20190530_145646.jpg

Then the big triangle should be triangulated (without any rules):

20190531_125538.jpg

Once the construction is over, we can start labeling the triangle corners with the direction of the following rules:

  1. One can label 1-2 side with either of 1 or 2.
  2. One can label 1-3 side with either of 1 or 3.
  3. One can label 2-3 side with either of 2 or 3.
  4. One can label the inside of the original triangle with any of 1, 2 or 3.

Progress of the Game

  • Assign the corners according to the rules.
  • In order to invade a triangle, player must assign the final unattached corner of that specific triangle.
  • Goal is to avoid invading a triangle that has corners 1-2-3. Winner is the player who invaded least number of such triangles.

Sperner’s Triangle

Idea of the invasion game comes from the Sperner’s triangle which is discovered by Emanuel Sperner in the 20th century. Triangulated shape in the invasion game is an example of Sperner’s triangle.

After labeling the corners a Sperner triangle will always give a small triangle that has corners 1-2-3:

20190531_125917.jpg

Actually, Sperner’s triangle always has odd-numbered 1-2-3 triangles.

This is why invasion game never ends with draw.

Dead End

Sperner’s triangle can be used to construct many games. For example, let’s say in a Sperner’s triangle all the sides of the little triangles that are connected between 1 and 2 are doors. And all the other sides are walls:

If one tries to walk through these doors, that person will end up in two situations:

  1. The person will end up inside a 1-2-3 triangle:
  2. The person will find him/herself outside of the triangle:

    M. Serkan Kalaycıoğlu

Real MATHEMATICS – AlgorIthm #5

Optimum Pizza Slice

Three friends will be sharing three slices of pizza.

Pizza Slices:

68591

Pizza 1: Four cheese.

20665-white-chicken-pizza-600X600

Pizza 2: Chicken.

pineapple pizza

Pizza 3: Pineapple.

Three friends could share the slices in six possible ways:

20190514_170727.jpg
P1:Pizza 1, P2:Pizza 2, P3:Pizza 3.

Eventually answer is one of those possibilities.

How much do you want it?

Choosing a slice of pizza seems like a very basic procedure. Though, there are many factors behind this simple decision. First of all finance is involved. And obviously “preferences” is an important factor: Not everybody has the same taste for food.

Let’s add these factors to our pizza slice situation. I will assume that 6 dollars is paid in total for the pizza slices, and three friends Ali, Steve and Jane have preferences as follows:

  1. Ali’s first choice is four cheese. If he can’t get that, his second and third choices are chicken and pineapple in order.
  2. Steve’s first choice is chicken. His second and third choices are pineapple and four cheese in order.
  3. Jane’s first choice is also chicken. Her second and third choices are four cheese and pineapple respectively.

In such situation, how can these friends decide fairly who gets which slice for how much?

Rental Harmony Problem

Two (or more) friends decide to rent an apartment. Rooms of the apartment are different in sizes and in some other factors (getting sunlight, having its own bathroom and such). For years mathematicians showed great interest towards the problematic of this situation: How can the rent and rooms be divided?

In 2004, three Turkish scientists Atila Abdulkadiroglu, Tayfun Sönmez and Utku Ünver published a paper that had a solution for the rental harmony problem. This paper shows an ingenious auction algorithm for the solution. (In fact, a famous website that is created to solve rental harmony problems named Spliddit had used this algorithm for almost a decade.)

The Algorithm

  • Roommates write their offers for every room in a closed envelope. For each roommate, total of the offers must be equal to the total rent of the apartment. (For instance, if the rent is 3000 dollars and total of the offers for each person must be equal to 3000 dollars.)
  • Envelopes are opened in front of everyone. A room goes to its highest bidder.
  • In the end, all the winner bids are added together. If it is equal to the rent, then winning bids are the amounts that are going to be paid. If it is exceeds or falls under the total rent, each offer gets to be corrected proportionally.

Answer to the Pizza Slices

We can use the auction algorithm in order to find a solution to the pizza slices problem. Assume that we have offers from Ali, Steve and Jane as follows:

20190514_170542.jpg

Highest bids:

For the pizza 1 is Ali with 4 dollars.

For the pizza 2 is Steve with 4 dollars.

For the pizza 3 is Jane with 2 dollars.

Total of the winning bids is

4 + 4 + 2 = 10

which is higher than 6 dollars. Hence we have to correct the amounts that need to be paid for each of the friends:

20190514_170425.jpg

In conclusion Steve and Ali would pay 2,4 dollars which is less than their offers. Jane would pay 1,2 dollars and it is also less than her offer. Auction algorithm helped these friends to select their pizza slices. The algorithm also helped them to pay less than what they were willing to. Hence, everyone is happy and envy-free with the conclusion.

M. Serkan Kalaycıoğlu

Real MATHEMATICS – AlgorIthm #4

Fair Cake Division

Is there a bullet-proof method for cutting a cake fairly?

This became a legitimate problem in mathematics back in 1944. A mathematician named Hugo Steinhaus published a paper for fair cake-cutting. According to him solution is trivial for two people. Method for two people is today commonly known as “one cuts, other picks”:

 

First person cuts the cake in half (on his/her point of view) and other person gets to pick any piece he/she wants. In this method both of them are happy and envy-free as first person believes the pieces are equal and second person picks the biggest piece on his/her view. Steinhaus’ answer is the first envy-free answer for fair cake division.

What if there are three people? Is there an envy-free method for cutting a cake for three people?

Incredible but answer wasn’t that obvious. Only 18 years after Steinhaus’ work (1962) J. H. Conway and J. Selfridge (independently) found an answer.

Ali, Steve and Jane

General method:

  1. Ali cuts the cake into three equal (that he considers equal) pieces.
  2. Steve evaluates the pieces. If he decides to do nothing Jane takes the turn.
  3. Jane selects any piece she wants. Steve picks as second, Ali gets the last piece.

Obviously things are never this easy. Let’s examine the method in details and show how ingenious it is:

Step #1: What should Ali do?

First step is easy: Ali cuts the cake into three equal pieces. Since he cuts them, he will be pleased to receive any of the pieces.

 

Step #2: What should Steve do?

Steve checks the pieces. Here, there is more than one possibility depending on how Steve sees Ali’s cuts:

  1. If Steve decides that at least two of the pieces are the best ones (best as in biggest) he does nothing and process continues with Jane selecting her piece.
    a. In case Steve thinks that all three pieces are equal, whichever Jane selects, he will get the best piece according to him:

20190502_152944.jpg
Steve will select his piece as second and he will be pleased to get whichever piece as he thinks they are all equal in sizes.

b. In case Steve thinks that two of the pieces are equal and best, even if Jane selects one of them, he will get to select the other best piece. He will be happy in either case.

  • If Steve thinks one piece is bigger than the other two, he needs to do something. Otherwise Jane would get the biggest piece:

    20190502_153002.jpg
    If Steve does nothing here, Jane will get the middle piece for sure.

    In such situation Steve trimmers the biggest piece which will result in a trimmed piece and a leftover:

     

    This way trimmed piece will be equal to at least one of the two remaining pieces which means at least two (trimmed and one of the other two) of the cake pieces are the best ones. Now Steve is ready to let Jane select her piece.

 

Step #3: What should Jane do?

Here, Jane is free to choose whichever piece she’d like to:

  1. If Steve did nothing, Jane will select any of the pieces. Steve goes after her and Ali will get whatever is left. Everyone will be content with his/her choice.
  2. (Steve trimmed a piece.) In such situation Jane is still free to choose. But now her choice determines the rest of the game. There are two possibilities at this state:
    a. Jane selects the trimmed piece. Then Steve and Ali will get their pieces in that order. In this situation Steve gets to cut the leftover into 3 equal pieces. Then Jane, Ali and Steve each select a piece of the leftover in that order:
     

    b. Jane selects any of the untrimmed piece. In that case Steve must select the trimmed piece and Jane gets to cut the leftover into 3 equal pieces. Then Steve, Ali and Jane each select a piece of the leftover in that order.

One wonders…

Is this really envy-free?

(Give yourself some time to think before you read the answer.)

*

*

*

Answers

For Ali: Yes, because Ali cuts the cake in three equal pieces on his view. He will be content with any of the pieces. Also he will not mind getting a part of the leftover.

For Steve: Yes, because Steve decides that there are at least two best pieces and he will be content with any of them. Also he will get to cut the leftover into 3 equal pieces which means he knows that he can get any of the leftover pieces.

For Jane: Yes, because she gets to select first for the original and leftover cake.

M. Serkan Kalaycıoğlu