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 – Algorithm #6

The year 2600…

Finally, we discovered a planet where we can live besides Earth. Scientists named this planet as T-489. The living conditions in T-489 seems very much like the Earth’s. Satellite views show that there is water on this planet. And scientists discovered that the atmosphere on this planet is almost the same as Earth’s atmosphere.

T-489 and its system.

Space agencies of the world’s biggest countries gathered a team to discover T-489. According to the plan, the first team that lands on T-489 will secure the landing point and build a headquarter. This point is set beforehand with the use of the satellite photos.

After the completion of the headquarters, three separate teams will be sent to T-489 to discover certain points on the planet that was set beforehand. These teams will be searching for the possible existence of life forms as well as testing the life conditions on each location.

The map: Headquarters is at the yellow point. Other points must be discovered by the teams. In an emergency, teams can use the roads and return to the headquarters.

The headquarter of T-489 should develop a map for those three teams which will be scouting the planet. This map is crucial since it will show how those teams should travel on the planet, and it will also explain how a team can return to the headquarters in case of an emergency.

In certain situations such as not knowing where a team is at a given time, headquarters must add an algorithm to the map. This way, in an emergency, any team can use this algorithm and return to the headquarters safely.

Road Coloring Problem

In 1970, Roy Adler suggested the road coloring problem. After almost 40 years, an Israeli mathematician called Trahtman solved this problem.

Yellow point the headquarters. Select a point and use the roads that in this order three times: blue-red-red. You will always end up at the yellow point.

Trahtman thought of the map as a graph shown above; each road had a direction and a distinct color. Trahtman created these directions and colors such that, following a certain algorithm, your travel would always end up on a specific point. In this example, the algorithm is following blue-red-red roads three times and always ending up at the yellow point. You can try at any point and see by yourself.

Chaos on T-489

You must develop a map for the teams that will be scouting the planet. Headquarters and the locations to visit are shown as follows:

M is the headquarters. A, B and C are the points to be discovered by the teams.

You should prepare for the worst possible scenario. If the connection breaks between the headquarters and the scouting teams, and if those teams can’t access to the map, your algorithm might save their lives.

The idea is: Place a sign on the entry of each point. These signs will have only two pieces of information: The color and the direction of the roads. (Why don’t you just hang the map on these signs? Because you are not sure if there is an alien life form on the planet. And in case they exist, such maps might put the headquarters and the whole mission at danger.)

Let’s say you created a map as follows:

Such a map would have an algorithm like this: Follow red-blue twice, and you will always return to the headquarters.

One wonders…

Create a map and an algorithm that will let you arrive at the point M in each time.

Let’s say that there is one more point added to the discovery. Create a map and an algorithm such that, whenever you use the algorithm you will end up at the headquarters.

(Try to use the least number of roads on your map.)

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

Real Mathematics – Algorithm #3

Card Games

I remember vividly; at least once a week I was dragged to family meetings. All I wanted was to stay home and play Duke Nukem. But I had to go to those meetings and keep score of a card game which dads play. There were rumors about my high mathematics grades, and I really wanted to fail mathematics just because I might have escaped this responsibility. And game had absurd scores too: “300 to us, 4250 to them, did you write 20 points to us?”

maxresdefault (1)

Everyone who had experienced campus life knows that living in a dorm meant both misery and lots of fun. Personally my favorites were the times when I sat down with three other guys and played card games for hours. After four years I became addicted to the very thing I despised as a child.

I love playing competitive games but if a game has algorithms on the background then I get addicted to that game. In some card games players develop algorithms in their heads. And in a group of close friends, everyone is aware of his/her opponents’ algorithms. This is why making simultaneous adjustments on your algorithm might win you the game.

Pico

Pico is a German card game that shows how mathematics can be used in card games perfectly. Even though Pico is a simple game it has astonishing mathematics that lies behind it.

pic1144912

  • In this multiplayer game there are eleven cards which have 2, 3, 4, 5, 6, 7, 8, 9, 10, 13 and 16 written on them.
    pic170001
  • Cards are shuffled and dealt. Each player gets five cards.
  • The only card left gets turned over so that both players know which cards his/her opponent has.
  • In every hand players select a card simultaneously.
  • The card that has the highest number on it wins the hand unless it is more than twice of the other card.
  • The winning card is placed next to the player who won the hand. The number on that card is the score he/she gets.
  • Losing card goes back to its owner.
  • Game continues until either one of the players holds exactly one card.

    pic1873967
    In case there is a deck of cards in your home, you could assign K to 13 and J to 16 so that you can play Pico.

Seko

I thought about writing a new game which I called Seko:

IMG_6628

  • Seko is a multiplayer game just like Pico. There are numbers from 2 to 50. Each player selects six numbers at once. Players roll a dice in order to determine who starts selecting first.
  • Twelve selected numbers are written on a paper.
  • Out of these twelve numbers, each player selects six numbers but this time one by one. Again they roll a dice in order to determine who starts selecting first.
  • In the first hand players select a number simultaneously.
    IMG_6633
  • If the difference of those numbers is odd, bigger number wins. If the difference is even and less than 20, smallest number wins.
  • The winning number is written in front of the winner. Loser gets his/her number back.
  • Game continues until a player has exactly one number left.

One wonders…

Instead of finding the difference in Seko, add the numbers. If the addition is odd, biggest number wins. If addition is even and less than 50, smallest number wins.

Can you find an algorithm to use in every game of Seko?

M. Serkan Kalaycıoğlu